[자료구조] 연결리스트로 구현한 큐(Linked Queue) - C/C++

<큐>

- 선형구조로 자료를 차례대로 저장하고, 가장 먼저 들어간 자료가 가장 먼저 나오는 FIFO(First In First Out, 선입선출)의 특성을 지닌다.

- 자료 반환은 큐의 제일 앞(front)에서만 가능하고 자료 추가는 큐의 제일 끝(rear)에서만 가능하다.

 

<큐 자료> * 본 게시물에서의 큐는 연결리스트(Linked List)로 구현하였다.

 

1. 노드 : 자료구조에 저장할 데이터를 가진 각각의 원소들을 구조체 Node로 선언한다.  

- 기존 연결리스트와 동일한 형태로 구성된다.

typedef struct Node
{
	Node *next;
	void *data;
} Node;

 

2. 큐 : 구조체 Queue을 선언한다.

- front(자료를 반환하는 큐의 제일 앞), rear(자료를 추가하는 큐의 제일 끝) 이라는 노드 포인터가 있다.

typedef struct Queue
{
	Node *front;
	Node *rear;
	int datasize;
	int length;
} Queue;

 

< 큐 연산 >

1. CreateQueue: 원하는 자료형의 데이터를 담은 노드를 저장할 수 있는 큐를 생성

-  빈 노드를 하나 생성하고 front와 rear가 빈 노드를 가리키도록 한다..

  1-1. LinkedQueue.c  

void CreateQueue(Queue *queue, int datasize)
{
	Node *newNode = makeNode(datasize);
	queue->front = newNode;
	queue->rear = newNode;
	queue->datasize = datasize;
	queue->length = 0;

	queue->Enqueue = Enqueue;
	queue->Dequeue = Dequeue;
	queue->isEmpty = isEmpty;
	queue->DeleteQueue = DeleteQueue;
}

Node *makeNode(int datasize)
{
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->data = malloc(datasize);
	newNode->next = newNode;
	return newNode;
}

 

2. Enqueue : 큐의 제일 뒤 rear 위치에 새로운 노드를 추가

- 현재 rear 위치에 데이터 영역을 복사한 후, 

- rear 노드의 next가 가리키는 곳에 빈 노드를 생성하여 새로 rear로 지정한다.

  2-1. LinkedQueue.c

void Enqueue(Queue *queue, void *endata)
{
	Node *newNode = makeNode(queue->datasize);
	memcpy(queue->rear->data, endata, queue->datasize);

	queue->rear->next = newNode;
	queue->rear = newNode;
	queue->length++;
}

 

3. isEmpty : 공백 큐인지를 전달

- 공백 상태의 큐일 때, 즉 front와 rear가 같을 때 TRUE를 반환

  3-1. LinkedQueue.c

int isEmpty(Queue *queue)
{
	if (queue->front == queue->rear)
		return TRUE;
	else
		return FALSE;
}

 

4. Dequeue : 큐의 맨 앞 front 위치에 있는 노드를 제거한 뒤 데이터를 인자에 복사. 성공 여부를 반환

- Dequeue연산이 실행되면 TRUE, 

  Underflow가 발생하면(=isEmpty가 true일 때=공백 상태의 큐일 때=front와 rear가 같을 때) FALSE를 반환

- Dequeue 연산이 이루어지면 dedata에 데이터의 메모리 영역이 복사된다.

  4-1. LinkedQueue.c

int Dequeue(Queue *queue, void *dedata)
{
	if (queue->isEmpty(queue))
		return FALSE;
	else
	{
		Node *deNode = queue->front;

		memcpy(dedata, deNode->data, queue->datasize);
		queue->front = deNode->next;
		free(deNode->data);
		free(deNode);
		queue->length--;
		return TRUE;
	}
}

 

5. deleteQueue : 큐를 제거(메모리 해제)

- 큐 내의 모든 노드들을 Dequeue 연산으로 제거한 뒤, front/rear가 가리키는 빈 노드와 queue 구조체까지 제거한다.

 5-1. LinkedQueue.c

void DeleteQueue(Queue *queue)
{
	void *dedata = malloc(sizeof(char));
	while (queue->Dequeue(queue, dedata))
		;
	free(dedata);
	free(queue->rear->data);
	free(queue->rear);
	free(queue);
}

 

※ 전체 소스 GitHub : https://github.com/waves123/LinkedQueue

 

자료구조 더보기

2017/07/23 - [자료구조] - [자료구조] 배열로 구현한 원형 큐(Circular Queue) - C/C++

2017/07/20 - [자료구조] - [자료구조] 연결리스트로 구현한 큐(Linked Queue) - C/C++

2017/07/15 - [자료구조] - [자료구조] 스택(Stack) - C/C++

2017/07/02 - [자료구조] - [자료구조] 연결리스트(Linked List) - C언어