Chapter 07. 큐의 배열 기반 구현

주의 사항!

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

큐는 스택과 상당히 유사합니다. 유일한 차이점은 먼저 저장한 데이터가 먼저 사용된다는 것입니다. 그래서 배열 기반 큐는 배열 기반 스택을 구현했던 것을 조금 수정하면 구현할 수 있을 것만 같습니다. 하지만 생각보다는 그렇게 간단히 끝나지 않습니다. 다음의 배열을 생각해 보겠습니다.

1

2

3

4

위 배열에는 1, 2, 3, 4의 순서대로 데이터가 입력되었습니다. 여기에서 데이터를 하나 빼보겠습니다. 이 배열이 큐인 경우 먼저 저장된 데이터를 먼저 빼야 하기 때문에 다음과 같이 1이 빠져나옵니다.

2

3

4

여기서부터가 문제입니다. 배열의 첫 번째 요소가 비어있습니다. 때문에 다음과 같이 나머지 데이터들을 한 칸씩 앞으로 옮겨주어야 할 것 같습니다.

2

3

4

그럼 여러분들이라면 큐의 데이터를 하나씩 앞으로 옮기는 알고리즘을 어떻게 코드로 구성할지 생각해 보기 바랍니다. 우선 반복문이 사용되어야 할 것 같습니다. 그렇다면 for문이나 while문이 사용되어야 할 것입니다.

 

while문부터 검토해보겠습니다. while의 종료 조건은 무엇이 적당할까요? 배열에서 더 이상 데이터를 참조하지 못하면? 하지만 유의미한 데이터가 저장되어 있지 않은 배열 요소라고 해도 그 안에는 쓰레기 값이 저장되어 있기 때문에 해당 조건은 사용할 수 없습니다.

참조 횟수가 배열 요소의 개수와 같다는 것을 종료 조건으로 사용할 수도 있을 것 같습니다. 하지만 큐에 저장된 데이터가 1개뿐인데도 매번 배열의 끝까지 데이터 복사를 수행해야 하는 것은 매우 비효율적으로 보입니다.

따라서 while문은 적절한 반복문이 아닌 것 같습니다.

 

그렇다면 for문은 어떨까요? 입력된 데이터의 개수를 가지고 반복 횟수를 설정하면 너무나도 쉽게 구현할 수 있을 것 같습니다. 하지만 이는 큐에는 적용이 불가합니다. 큐는 저장된 데이터의 개수를 알 수 없기 때문입니다. 물론, 간단한 방법으로 큐에 저장된 데이터의 개수를 저장하는 변수를 선언할 수도 있습니다. 하지만 이는 큐의 특징과는 맞지 않습니다. 큐와 스택은 저장된 데이터의 개수를 별도로 저장하지 않습니다. 따라서 for문도 적절하지 않아 보입니다.

 

우리는 이런 문제를 해결하기 위해 전혀 다른 방법을 생각해야 합니다. 다음의 배열을 보겠습니다.

F			R
1	2	3	4

위 배열의 F는 데이터의 머리, R은 데이터의 꼬리를 가리키고 있습니다. 여기서 데이터를 하나 빼보겠습니다. 그럼 가장 먼저 저장된 1이 빠져나올 것입니다. 위 배열은 다음과 같은 형태가 됩니다.

	F		R
	2	3	4

큐에서 데이터를 하나 뺌과 동시에 F의 위치가 다음 칸으로 옮겨졌습니다. 이렇게 하면 큐 안에 저장된 데이터의 개수를 몰라도 매번 가장 먼저 저장된 데이터를 사용할 수 있습니다. 만약 새로운 데이터가 추가된다면 R을 다음 칸으로 옮깁니다. 그런데 여기서 다음과 같은 문제를 생각할 수 있습니다.

			F		R
			4	5	6

앞선 배열에서 2와 3을 빼내고, 5와 6을 새로 저장했습니다. 여기에서 만약 데이터를 하나 더 저장한다면 어떻게 될까요? 데이터를 추가하면 R을 다음 칸으로 옮겨야 합니다. 그런데 R은 이미 배열의 끝에 도달했으므로 여기서 다음 칸으로 옮기게 되면 배열을 벗어나게 됩니다. 물론 이 문제는 간단하게 해결할 수 있습니다. 다음과 같이 R이 배열의 끝에 도달해 있고 다음 칸으로 옮겨야 한다면 배열의 첫 번째 요소로 옮깁니다.

R			F
7			4	5	6

이는 F에 대해서도 똑같이 적용됩니다. 이렇게 함으로써 데이터를 매번 옮길 필요 없이 큐를 구현할 수 있게 되었습니다. 이런 형태의 큐를 가리켜 원형 큐라고 합니다. 마치 배열이 원형으로 구성되어 끝과 처음이 연결된 것으로 볼 수 있기 때문입니다. 

 

그런데 원형 큐도 한 가지 문제가 있습니다. 다음의 예를 보면서 큐에 데이터가 가득 찬 상태와 데이터가 하나도 없을 때의 차이를 어떻게 구분할 수 있을지 생각해 보기 바랍니다. 물론 데이터의 개수는 알 수가 없습니다.

 

다음은 원형 큐를 처음 생성했을 때입니다.

F, R

원형 큐를 처음 생성하면 F와 R을 0으로 초기화합니다. 이제 데이터를 하나 추가하겠습니다.

F	R
	1

R에 1을 더합니다. 그러면 R은 이제 1이 되고, 배열의 1번지, 즉, 두 번째 칸을 가리키게 됩니다. R이 가리키는 곳에 1을 저장했습니다. 이제 이 데이터를 빼겠습니다.

	F, R

F에 1을 더합니다. 그러면 F는 이제 1이 되고, 배열의 1번지, 즉, 두 번째 칸을 가리키게 됩니다. F가 가리키는 곳의 데이터를 빼냈습니다. 이제 데이터 5개를 추가하겠습니다.

R	F
6		2	3	4	5

이 상태에서 데이터를 하나 더 추가하겠습니다. 

	F, R
6	7	2	3	4	5

예시는 여기까지입니다. 우리가 큐를 통해서 알 수 있는 것은 F와 R의 위치뿐입니다. 그렇다면 F와 R의 위치를 이용해서 데이터가 가득 찼는지, 비어 있는지를 알아내야 합니다. 'F와 R이 같으면 큐가 비어 있는 것이다'라고 할 수 있습니다. 하지만 보다시피 F와 R이 같은데도 데이터가 가득 차 있는 경우도 있습니다. 

 

위와 같은 원형 큐에서는 데이터가 가득 찼는지, 비어 있는지를 알 수가 없습니다. 바로 이것이 원형 큐가 가지는 문제점입니다. 하지만 이 문제도 간단하게 해결할 수 있습니다. 대신 배열 요소 하나를 포기해야 합니다. 무슨 말인지 바로 예시로 보이겠습니다.

 

원형 큐를 처음 생성했을 때입니다.

F, R

원형 큐를 생성하면 F와 R을 0으로 초기화합니다. 이제 데이터를 하나 추가하겠습니다.

F	R
	1

다시 데이터를 하나 빼겠습니다.

	F, R

이제 데이터를 5개 추가하겠습니다.

R	F
6		2	3	4	5

앞서 소개한 원형 큐의 문제를 해결하는 방법은 여기서 드러납니다. 바로 지금 이 상태를 큐가 가득 찬 상태라고 정하는 것입니다. 

 

...?

 

이런 반응일 것 같습니다. 해결방법 같지도 않습니다. 하지만 이는 효과적인 해결책입니다. 데이터를 저장할 공간 하나를 포기하는 대신 우리는 큐가 가득 찼는지 비어 있는지를 확실히 구분할 수 있게 되었습니다. F와 R이 같으면 큐가 비어 있는 것이고, F가 R보다 한 칸 앞서 있으면 큐는 가득 찬 것이 됩니다.

---

이제 원형 큐에 대한 이해를 마쳤으므로 이를 코드로 구현해 보고자 합니다. 큐의 ADT를 기반으로 다음과 같이 헤더 파일을 정의할 수 있습니다.

//CircularQueue.h 헤더 파일로 저장
#ifndef CIRCULARQUEUE_H
#define CIRCULARQUEUE_H

#define ARR_LEN 20
#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct CircularQueue
{
	Data arr[ARR_LEN];
	int front;
	int rear;
}CircularQueue;

typedef CircularQueue Queue;

void QueueInit(Queue* pq);
void enqueue(Queue* pq, Data data);
Data dequeue(Queue* pq);
Data QPeek(Queue* pq);
int QIsEmpty(Queue* pq);

#endif

위 헤더 파일을 바탕으로 각 함수들을 정의해 봅니다.

 

각 함수들은 간단히 정의할 수 있기 때문에 자세한 과정은 설명하지 않겠습니다. 함수들은 구현한 결과는 다음과 같습니다.

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

int NextIndex(int pos)
{
	return (pos == ARR_LEN - 1) ? 0 : pos + 1;    //입력 받은 값이 배열의 마지막 요소를 가리키고 있다면 0 반환, 아니면 1을 더한 값을 반환
}

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

void enqueue(Queue* pq, Data data)
{
	int next = NextIndex(pq->rear);

	if (next == pq->front)    //rear 앞이 front라면
	{
		printf("큐에 공간이 부족합니다.\n");
		return;
	}

	pq->rear = next;
	pq->dataArr[pq->rear] = data;
}

Data dequeue(Queue* pq)
{
	if (QIsEmpty)
	{
		printf("큐에 저장된 데이터가 없습니다.\n");
		exit(1);
	}
	
	pq->front = NextIndex(pq->front);
	return pq->dataArr[pq->front];
}

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

	return  pq->dataArr[NextIndex(pq->front)];
}

int QIsEmpty(Queue* pq)
{
	return (pq->front == pq->rear) ? TRUE : FALSE;    //front와 rear가 같으면 비어있는 것
}

위의 소스 파일에는 헤더 파일에는 선언되어 있지 않은 NextIndex 함수가 정의되어 있습니다. 이 함수는 front 혹은 rear의 다음 위치를 계산하기 위해 정의된 함수입니다. 

 

구현이 끝이 났으니 적절한 main 함수를 작성하여 실행 결과를 확인하겠습니다.

//main.c 소스 파일로 저장
#include "CircularQueue.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

*/