Chapter 07. 큐의 연결 리스트 기반 구현

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

이번에는 연결 리스트를 기반으로 하는 큐를 구현해 보겠습니다. 큐는 데이터를 저장하는 위치와 데이터를 가져오는 위치가 다르다는 특징을 가지고 있습니다. 이를 연결 리스트 기반으로 구현하면, 꼬리로 데이터를 저장하면서, 머리로 데이터를 가져올 것이라는 것을 쉽게 생각해 볼 수 있습니다.

그럼 바로 연결 리스트 기반 큐의 헤더 파일을 정의해 보겠습니다. 앞서 정의했던 큐의 ADT를 바탕으로 직접 헤더 파일을 정의해 보는 것도 좋습니다.

//LBQueue.h 헤더 파일로 저장
#ifndef LB_QUEUE_H
#define LB_QUEUE_H

#define TRUE 1
#define FALSE 0

typedef int Data;

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

typedef struct LBQueue
{
	Node* front;
	Node* rear;
} LBQueue;

typedef LBQueue Queue;

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

#endif

이제 위 헤더 파일을 기반으로 각각의 함수들을 구현해 보겠습니다.

//LBQueue.c 소스 파일로 저장
#include "LBQueue.h"
#include <stdlib.h>
#include <stdio.h>

void QueueInit(Queue* pq)
{
	pq->front = NULL;
	pq->rear = NULL;
}

void Enqueue(Queue* pq, Data data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL)                          
	{
		printf("메모리 공간이 부족합니다. \n");    
		exit(1);                                  
	}

	newNode->data = data;
	newNode->next = NULL;

	if (pq->front == NULL) pq->front = newNode;
	else pq->rear->next = newNode;

	pq->rear = newNode;
}

Data Dequeue(Queue* pq)
{
	if (pq->front == NULL)
	{
		printf("큐에 저장된 데이터가 없습니다. \n");
		exit(1);
	}

	Node* delNode = pq->front;
	Data delData = delNode->data;

	pq->front = pq->front->next;

	free(delNode);
	return delData;
}

Data QPeek(Queue* pq)
{
	if (pq->front == NULL)
	{
		printf("큐에 저장된 데이터가 없습니다. \n");
		exit(1);
	}

	return pq->front->data;
}

int QIsEmpty(Queue* pq)
{
	return (pq->front == NULL) ? TRUE : FALSE;
}

함수를 구현하는 게 어렵지는 않기 때문에 하나하나 자세한 설명은 하지 않겠습니다. 코드만 보아도 쉽게 이해가 갈 것입니다. 여기서 구현한 큐는 꼬리로 데이터를 입력하고 머리로 데이터를 출력합니다. 반대로 머리로 데이터를 입력하고, 꼬리로 출력하는 방식도 생각해 볼 수 있는데 왜 꼬리로 데이터를 입력하는지 궁금할 수 있습니다.

 

머리로 데이터를 입력하고, 꼬리로 출력하는 방식은 구현할 수는 있지만 일단은 before 포인터가 필요하게 됩니다. 왜냐하면 꼬리의 데이터를 출력하면 꼬리 포인터를 새로 지정해야 하는데, 노드는 next 방향으로만 연결이 되어 있기 때문에 새로운 꼬리를 지정할 수가 없기 때문입니다. 그래서 before 포인터를 사용하여 현재 꼬리의 앞에 있는 노드를 가리키게 해야 합니다. 그런데 이것 만으로는 해결할 수 없습니다. 꼬리에서 데이터를 출력하고, before 위치를 새로운 꼬리로 지정하면, 이번에는 before 포인터를 다시 지정해야 하는데 이 역시 노드의 연결 방향이 next 밖에 없기 때문에 before를 새로 지정하는 것이 불가능하게 됩니다.

즉, 연결 리스트 기반 큐에서는 머리로 데이터를 입력하고 꼬리로 출력하는 방식이 불가능합니다. 만약 양방향 연결 리스트 기반이라면 어느 쪽으로 입력하고 출력하든 상관없습니다.

 

이제 연결 리스트 기반 큐의 구현이 완성되었습니다. 이제 이를 테스트할 수 있는 main 함수를 정의하여 그 실행결과를 확인해 보겠습니다.

//main.c 소스 파일로 저장
#include "LBQueue.h"
#include <stdio.h>

int main(void)
{
	//Queue의 생성 및 초기화
	Queue q;
	QueueInit(&q);

	//데이터 넣기
	Enqueue(&q, 1);
	Enqueue(&q, 2);
	Enqueue(&q, 3);
	Enqueue(&q, 4);
	Enqueue(&q, 5);

	//데이터 꺼내기
	while (!QIsEmpty(&q))
	{
		printf("%d ", Dequeue(&q));
	}

	return 0;
}

/*
실행결과

1 2 3 4 5

*/

위 main 함수는 배열 기반 큐를 구현하고 이를 테스트할 때 사용했던 것과 동일합니다.

---

책에서 설명하는 내용은 위 내용까지입니다. 지금부터는 개인적인 호기심으로 원형 연결 리스트 기반 큐를 구현해 보겠습니다. 헤더 파일의 정의는 위에서 정의했던 것에서 조금 수정합니다.

//LBQueue.h 헤더 파일로 저장
#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 LBQueue
{
	Node* tail;    //front, rear가 아닌 tail
} LBQueue;

typedef LBQueue Queue;

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

#endif

원형 연결 리스트 기반 큐의 구현에서 달라지는 것은 front와 rear를 사용하지 않고 tail 하나만 사용한다는 것입니다. 이제 위 헤더 파일을 기반으로 각 함수들을 정의해 보겠습니다.

//LBQueue.c 소스 파일로 저장
#include "LBQueue.h"
#include <stdlib.h>
#include <stdio.h>

void QueueInit(Queue* pq)
{
	pq->tail = NULL;
}

int QIsEmpty(Queue* pq)
{
	return (pq->tail == NULL) ? TRUE : FALSE;
}

void Enqueue(Queue* pq, Data data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL)                          //동적 할당에 실패하면
	{
		printf("메모리 공간이 부족합니다. \n");    //문구 출력
		exit(1);                                  //프로그램 강제 종료
	}

	newNode->data = data;

	if (pq->tail == NULL)
	{
		newNode->next = newNode;
	}
	else
	{
		newNode->next = pq->tail->next;
		pq->tail->next = newNode;
	}

	pq->tail = newNode;
}

Data Dequeue(Queue* pq)
{
	if (pq->tail == NULL)
	{
		printf("큐에 저장된 데이터가 없습니다. \n");
		exit(1);
	}

	Node* delNode = pq->tail->next;
	Data delData = delNode->data;

	if (delNode == pq->tail)
	{
		pq->tail = NULL;
	}
	else
	{
		pq->tail->next = delNode->next;
	}

	free(delNode);
	return delData;
}

Data QPeek(Queue* pq)
{
	if (pq->tail == NULL)
	{
		printf("큐에 저장된 데이터가 없습니다. \n");
		exit(1);
	}

	return pq->tail->next->data;
}

원형 연결 리스트 기반 큐의 경우에도 데이터를 꼬리로 입력하고, 머리로 출력합니다. 코드가 어렵진 않아서 이해하기에도 어렵진 않을 것입니다.

앞서 사용했던 main 함수를 이용해 원형 연결 리스트 기반 큐를 테스트해본 결과입니다.

//main.c 소스 파일로 저장
#include "LBQueue.h"
#include <stdio.h>

int main(void)
{
	//Queue의 생성 및 초기화
	Queue q;
	QueueInit(&q);

	//데이터 넣기
	Enqueue(&q, 1);
	Enqueue(&q, 2);
	Enqueue(&q, 3);
	Enqueue(&q, 4);
	Enqueue(&q, 5);

	//데이터 꺼내기
	while (!QIsEmpty(&q))
	{
		printf("%d ", Dequeue(&q));
	}

	return 0;
}

/*
실행결과

1 2 3 4 5

*/