[C 자료구조] 큐(Queue) - 연결리스트 구현

[C 자료구조] 큐(Queue) - 선형큐 / 원형큐 배열 구현

지난 포스팅에서 큐에 대해 설명하고, 선형큐와 원형큐를 배열을 사용해 구현해보았습니다. 오늘은 배열이 아닌 연결 리스트를 사용하여 큐를 구현하는 법에 대해 다뤄보겠습니다.

 

다시 한 번 큐에 대해 간단히 복습해보면

큐는 front 에서 dequeue ( 삭제, 꺼냄 ) 연산이 진행되고 rear 에서 enqueue ( 삽입 ) 연산이 진행되는 자료구조입니다.

연결리스트를 이용해 큐를 구현하는 것은 배열과 거의 유사한 순서로 진행되고, 문법이나 노드의 구현만 조금 다릅니다.

 

노드, 큐 정의

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

typedef int element;

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

typedef struct Queue {
	Node* front;
	Node* rear;
	int count;
}Queue;

먼저 노드와 큐를 정의해줍니다. 연결리스트를 사용할 것이니 당연히 데이터와 포인터가 함께 존재하는 노드가 필요합니다. 또한 이런 노드를 하나씩 집어넣는 거니까 큐가 필요한데 배열로 큐를 구현할 때는 front 와 rear 이 int 형이었습니다. 왜냐하면 큐 내에서의 위치를 나타내기 위해서 배열 형태는 인덱스가 필요하고 인덱스는 정수로 나타내기 때문입니다.

 

그럼 연결리스트로 구현된 큐 내에서 데이터의 위치를 파악하려면? 인덱스가 아닌 포인터가 필요합니다. 따라서 front와 rear는 노드 포인터로 정의됩니다. 또한 count 변수가 하나 추가되는데요, 이는 아래의 enqueue 에서도 설명하겠지만 연결리스트로 만든 큐는 MAX_QUEUE_SIZE 가 없습니다. 내가 데이터를 넣는 족족 동적할당해서 데이터를 저장하기 때문에 제한되는 크기가 없는 것이죠. 따라서 현재 큐 내에 몇 개의 데이터가 있는지 저장하는 count 변수도 껴서 큐를 정의합니다.

 

 

init() : 큐 초기화 함수

void init(Queue* q)
{
	q->front = q->rear = NULL;
	q->count = 0;
}

배열로 구현한 큐에서는 front = rear = -1 로 초기화를 시켜줬습니다. 연결리스트에서 front 와 rear 는 포인터이므로 NULL 포인터로 초기화 시켜주고 처음에 큐에는 노드가 0개 이니까 count 또한 0으로 초기화 시켜 줍니다.

 

 

isempty() : 공백 검사 함수

int isempty(Queue* q)
{
	return ( q->count == 0 );
}
// 다른 방법
int isempty(Queue *q)
{
	return (q->front == NULL && q->rear == NULL)
}

위에서 말했듯 연결리스트로 구현한 큐는 데이터를 추가로 삽입할 때마다 동적할당하여 새로운 노드를 만들어 큐에 저장하는 방식이기 때문에 가득 찼다 라는 개념이 없습니다. 따라서 이전까지 계속 isempty() 와 세트로 구현했던 isfull() 함수가 필요 없습니다. 그러나 큐에서 데이터를 꺼낼 때 큐가 비어있다면 오류가 발생할 수 있습니다. 따라서 큐가 비어있는지 체크하는 함수 isempty() 는 필요합니다.

 

큐가 비어있는지 확인하는 방법은 2개 입니다. 첫 번째로 초기화 한 것처럼 front 와 rear 포인터가 모두 NULL 포인터라면 큐는 비어 있는 겁니다. 다른 방법으로는 count 변수를 큐 구조체 안에 선언했으므로 노드의 개수를 나타내는 count 가 0이라면 당연히 큐에는 0개의 노드가 있으므로 큐가 비어있습니다. 어떤 방법을 사용해도 괜찮습니다.

 

 

enqueue() : 데이터 삽입 함수

void enqueue(Queue* q, element data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = NULL;

	if (isempty(q)) // 큐가 비어있을 때
	{
		q->front = newNode;
	}
	else
	{
		q->rear->next = newNode; 	// 맨 뒤의 다음을 newNode 로 설정
	}
	q->rear = newNode;		 	// rear 포인터를 방금 삽입한 newNode 로 이동
	q->count++;		    	        // 큐 안의 노드 개수 1 증가
}

큐의 데이터 삽입은 rear 부분에 삽입합니다. 새로운 노드를 할당하여 입력받은 데이터를 노드에 써주고 이후 큐에 넣습니다. 그 다음은 큐가 비어있을 때, 비어있지 않을 때로 구분되어 있습니다.

큐가 비어있을 때 enqueue

큐가 비어있을 때 새로운 노드를 삽입하면 front 포인터와 rear 포인터는 같은 노드를 가리키게 됩니다.

 

큐가 비어있지 않을 때 enqueue

큐가 비어있지 않을 때 노드를 삽입하면 front 는 맨 앞의 노드, rear 은 방금 삽입한 노드를 가리키게 됩니다. 

 

1. newNode 생성

2. rear 의 next 가 newNode 를 가리키게 설정

3. rear 가 newNode 를 가리키게 설정

 

next 포인터가 enqueue 방향과 반대로 설정되는 것을 유의깊게 보셔야 합니다. 이는 dequeue 연산을 위한 것입니다.

그 이후 마지막으로 노드가 한 개 추가되었으므로 큐 내의 노드 개수를 의미하는 count 변수를 1 증가시키며 종료됩니다.

 

 

dequeue() : 데이터 반환(꺼냄) 함수

element dequeue(Queue* q)
{
	element data;
	Node* ptr;
	if (isempty(q))
	{
		printf("큐 공백 에러\n");
		return 0;
	}
	ptr = q->front;				// 꺼낼 노드를 ptr 설정
	data = ptr->data;			// 반환할 data 변수에 꺼낼 노드의 데이터를 복사
	q->front = ptr->next;			// front 포인터를 꺼낼 노드의 다음으로 이동
	free(ptr);				// ptr 해제 (꺼낸 노드 해제)
	q->count--;				// 큐 안의 노드 개수 1 감소

	return data;
}

dequeue 는 큐의 맨 앞, front 가 가리키는 노드에서 발생합니다. 큐가 비어 있는지 isempty 함수로 체크를 해주고 비어있지 않다면 맨 앞의 노드의 데이터를 반환하는 함수입니다. 데이터를 반환하기에 앞서 꺼낸 노드를 메모리 해제를 해줘야 하기 때문에 임시 포인터 변수 ptr 과 반환할 데이터를 저장할 data 변수를 선언합니다.

 

먼저 임시 포인터 ptr 이 꺼낼 노드를 가리키도록, 즉 원래의 front 포인터가 가리키던 노드를 가리키게 합니다.

그 이후 반환할 data 변수에 노드의 data 값을 복사하고, front 포인터를 꺼낼 노드의 다음 노드를 가리키도록 합니다.

그럼 이제 꺼낸 노드의 역할은 없으므로 꺼낸 노드를 free(ptr) 을 통해 해제 시키고, 큐 내의 노드 개수를 의미하는 count 변수를 1 감소시킵니다. 마지막으로 꺼낸 data 를 반환하는 함수입니다. 이를 그림을 통해 이해해보면

 

ptr = q->front

임시 포인터 변수 ptr 이 front 가 가리키던 노드를 가리키도록 하고 ptr이 가리키는 노드의 데이터를 선언한 data 변수에 복사합니다.

q->front = ptr->next

노드를 꺼내기 이전에 front 포인터가 다음 노드를 가리키도록 합니다. 이를 위해 enqueue 과정에서 next 포인터를 역방향으로 설정한 것입니다.

그 이후에 free 를 통해 ptr을 해제, count 1 감소, data 반환 과정으로 dequeue 가 이뤄집니다.

 

 

전체 코드 및 실행 결과

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

typedef int element;

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

typedef struct Queue {
	Node* front;
	Node* rear;
	int count;
}Queue;

void init(Queue* q)
{
	q->front = q->rear = NULL;
	q->count = 0;
}

int isempty(Queue* q)
{
	return (q->count == 0);
}

void enqueue(Queue* q, element data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = NULL;

	if (isempty(q)) // 큐가 비어있을 때
	{
		q->front = newNode;
	}
	else
	{
		q->rear->next = newNode; // 맨 뒤의 다음을 newNode 로 설정
	}
	q->rear = newNode;			 // rear 포인터를 방금 삽입한 newNode 로 이동
	q->count++;		    	     // 큐 안의 노드 개수 1 증가
}

element dequeue(Queue* q)
{
	element data;
	Node* ptr;
	if (isempty(q))
	{
		printf("큐 공백 에러\n");
		return 0;
	}
	ptr = q->front;				// 꺼낼 노드를 ptr 설정
	data = ptr->data;			// 반환할 data 변수에 꺼낼 노드의 데이터를 복사
	q->front = ptr->next;		// front 포인터를 꺼낼 노드의 다음으로 이동
	free(ptr);					// ptr 해제 (꺼낸 노드 해제)
	q->count--;					// 큐 안의 노드 개수 1 감소

	return data;
}

int main(void)
{
	int i;
	Queue q;

	init(&q);
	for (i = 1; i < 10; i++)
	{
		enqueue(&q, i);
	}

	while (!isempty(&q))
	{
		printf("[%d] ", dequeue(&q));
	}
	printf("\n");
	return 0;
}

참고 및 이미지 출처 : https://code-lab1.tistory.com/6