(자료구조) 리스트 기반 큐 구현 -2

● 큐의 ADT  (이전 배열기반 리스트의 ADT와 동일)

○ void QueueInit(Queue * pq);
 - 큐의 초기화를 진행한다.
 - 큐 생성 후 제일 먼저 호출되는 함수이다.

○  int QIsEmpty(Queue *pq);
 - 큐가 빈 경우 TRUE 그렇지 않은 경우 FALSE 를 반환한다. 

○  void Enqueue(Queue * pq, Data data);
 - 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

○  Data Dequeue(Queue *pq);
 - 저장순서가 앞선 데이터를 삭제한다.
 - 삭제된 데이터는 반환된다.
 - 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

○  Data QPeek(Queue *pq);
 - 저장순서가 가장 앞선 데이터를 반한하되 삭제하지 않는다.
 - 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.


● 큐의 리스트 기반 구현 논리 

 

- 1. 필요한 멤버 

배열 기반 구현과 동일하게 큐는 Front(앞)  와 Rear(뒤)  멤버를 가진다. 

선입 선출의 구조이므로 큐의 Front 에서 삭제가 이루어지며 Rear 에서 삽입이 이루어진다. 

 

※ 배열기반의 경우 선언한 배열길이의 낭비를 방지하기 위해 원형 큐 (Circular Queue) 형태의 방식을 사용하지만, 

    리스트의 경우 메모리 동적 할당을 통해 신규 데이터가 삽입될때 마다 노드를 생성하므로 직선 큐를 그대로 구현한다.

 

리스트 기반 큐(Queue) 구조체 정의 

// 리스트의 노드 구조체 
typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

// 큐 구조체
typedef struct _lQueue
{
	Node * front;
	Node * rear;
} LQueue;

 

헤더파일

#ifndef __LB_QUEUE_H__
#define __LB_QUEUE_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _lQueue
{
	Node * front;
	Node * rear;
} LQueue;

typedef LQueue Queue;

void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);

void Enqueue(Queue * pq, Data data);
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);

#endif

 

 

Circular Queue  전체 소스(구현실습) 

#include <stdio.h>
#include <stdlib.h>
#include "ListBaseQueue.h"

void QueueInit(Queue * pq){
	pq->front = 0;
	pq->rear = 0;
}
int QIsEmpty(Queue * pq){
	if(pq->front == pq->rear) return TRUE;
	
	return FALSE;
}

void Enqueue(Queue * pq, Data data){
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->data = data; 
	// 예외처리 추가 구문 if 문 누락함..  
	if(QIsEmpty(pq)) { // 최초 삽입시, 
		pq->front = newNode; 
		pq->rear = newNode;  
	}else{
	pq-rear->next = newNode;
	pq-rear = newNode;
}	
}
Data Dequeue(Queue * pq){
	if(QIsEmpty(pq)) {
		printf("Queue is Empty!");
		exit(-1);
	}
	Node * delQue = (Node*)malloc(sizeof(Node));
	delQue = pq->front;
	Data delDt = delQue->data;
	pq->front = pq->front->next;
	free(delQue);
	return delDt;
}
Data QPeek(Queue * pq){
	if(QIsEmpty(pq)){ // if 구문 누락 (추가)  삽입된 데이터가 없는 경우
	 printf("Queue is Empty"); 
	 exit(-1);
	}
	return pq->front->data;
}