큐(순환 큐 / 링크드 큐)

큐는 스택과 달리 선입선출(FIFO : Fist In First Out) 구조이다. 먼저 들어간 데이터가 먼저 나온다.

순환 큐

순환 큐는 무엇인가? 마치 환형 링크드 리스트처럼, 맨 뒤 노드랑 맨 앞 노드랑 연결돼있는 큐이다. 근데 순환 큐는 문제점이 있다. 무엇인가? 큐가 비어있을 때랑 가득 차 있을 때랑 구분할 수 없다는 것이다.

어떻게 해결하는가? 일반적으로는 큐 배열을 생성할 때 실제 용량보다 1만큼 더 크게 만들어서 전단과 후단 사이를 비우는 것이다. (비워둬야 한다. 안 그러면 의미 없다.) 전단은 맨 앞 인덱스, 후단은 맨 뒤 인덱스 + 1이다. 그럼 비어있을 땐 전단과 후단이 같은 곳을 가리키고, 가득 차면 후단은 전단보다 1만큼 작은 곳을 가리킨다.

이 점을 기억하며 순환 큐를 만들어보자.

typedef int ElementType;

struct Node
{
	ElementType data;
};

struct QueueCircular
{
	int capacity;	// 용량.
	int front;		// 전단 인덱스.
	int rear;		// 후단 인덱스.
	Node* nodes;	// 노드 배열.
};

void QC_CreateQueue(QueueCircular** queue, int capacity)
{
    if (QC_IsFull(queue))
	{
    	cout << "가득 차 있음";
        return;
	}
    
	*queue = new QueueCircular;
	(*queue)->nodes = new Node[capacity + 1];
	(*queue)->capacity = capacity;
	(*queue)->front = 0;
	(*queue)->rear = 0;
}

void QC_DestroyQueue(QueueCircular* queue)
{
	delete[] queue->nodes;
	delete queue;
}

기본적인 함수는 지금까지 해왔던 거랑 거의 똑같아서 쉽게 할 수 있다. 주의할 건 Enqueue에서 만약 가득 차 있다면 바로 리턴하게 했다.

int QC_IsEmpty(QueueCircular* queue)
{
	return (queue->front == queue->rear);
}

int QC_IsFull(QueueCircular* queue)
{
	if (queue->front < queue->rear)
		return (queue->rear - queue->front) == queue->capacity;
	else
		return (queue->rear + 1) == queue->front;
}

배열 1칸 늘린 것을 고려해서 가득 차 있음 / 비어 있음을 만들어주었다.

int CQ_GetSize(QueueCircular* queue)
{
	if (queue->rear >= queue->front)
		return queue->rear - queue->front;
	else
		return queue->capacity + 1 - (queue->front - queue->rear);
}

사이즈도 QC_IsFull()가 마찬가지로 rear과 front의 위치차를 고려해서 만들었다.

다음 예제를 통해 제대로 만들었는지 확인한다.

int main()
{
	int i;
	QueueCircular* queue;
	QC_CreateQueue(&queue, 10);

	QC_Enqueue(queue, 1);
	QC_Enqueue(queue, 2);
	QC_Enqueue(queue, 3);
	QC_Enqueue(queue, 4);

	for (i = 0; i < 3; i++)
		cout << "Dequeue : " << QC_Dequeue(queue) << ", front : " << queue->front << ", rear : " << queue->rear << endl;
	i = 100;
	while (QC_IsFull(queue) == 0)
		QC_Enqueue(queue, i++);

	cout << "Capacity : " << queue->capacity << ", Size : " << CQ_GetSize(queue) << endl;
	while (QC_IsEmpty(queue) == 0)
		cout << "Dequeue : " << QC_Dequeue(queue) << ", front : " << queue->front << ", rear : " << queue->rear << endl;

	QC_DestroyQueue(queue);
	int debug = -1;
}

실행 결과.

링크드 큐

링크드 큐는 무엇인가? 링크드 리스트로 스택 구현한 것처럼, 링크드 리스트로 큐를 구현한 것이다. 노드 포인터로 구성되어있기 때문에, 순환 큐보다 구현하기 더 쉽다. 그럼 순환 큐 보다 더 좋다는 건가? 그렇다고는 할 수 없다. 왜냐하면 순환 큐는 동적 할당을 할 필요가 없기 때문이다. 크기가 예측 가능하고 고성능이 필요한 버퍼와 같은 사례에서는 링크드 큐보다 순환 큐가 더 적합하다.

링크드 큐는 다음과 같이 구현하면 된다. 지금까지 많이 했으므로 코드만 적겠다!

#include <string>
struct Node
{
	char* data;
	Node* nextNode;
};

struct QueueLinked
{
	Node* front;	// 큐의 시작.
	Node* rear;		// 큐의 끝.
	int count;		// 노드의 수.
};

void QL_CreateQueue(QueueLinked** queue);
void QL_DestroyQueue(QueueLinked* queue);
Node* QL_CreateNode(char* newData);
void QL_DestroyNode(Node* node);
void QL_Enqueue(QueueLinked* queue, Node* newNode);
Node* QL_Dequeue(QueueLinked* queue);
int QL_IsEmpty(QueueLinked* queue);

inline void QL_CreateQueue(QueueLinked** queue)
{
	*queue = new QueueLinked;
	(*queue)->front = nullptr;
	(*queue)->rear = nullptr;
	(*queue)->count = 0;
}

inline void QL_DestroyQueue(QueueLinked* queue)
{
	while (!QL_IsEmpty(queue))
	{
		Node* temp = QL_Dequeue(queue);
		QL_DestroyNode(temp);
	}
	delete queue;
}

inline Node* QL_CreateNode(const char* newData)
{
	Node* node = new Node;
	node->data = new char[strlen(newData) + 1];
	strcpy_s(node->data, strlen(newData) + 1, newData);
	return node;
}

inline void QL_DestroyNode(Node* node)
{
	delete[] node->data;
	delete node;
}

inline void QL_Enqueue(QueueLinked* queue, Node* newNode)
{
	if (queue->front == nullptr)
		queue->front = newNode;
	else
		queue->rear->nextNode = newNode;
	queue->rear = newNode;
	queue->count++;
}

inline Node* QL_Dequeue(QueueLinked* queue)
{
	if (queue->front == nullptr)
		return nullptr;

	Node* temp = queue->front;
	if (temp->nextNode == nullptr)
	{
		queue->front = nullptr;
		queue->rear = nullptr;
	}
	else
		queue->front = queue->front->nextNode;
	queue->count--;
	return temp;
}

inline int QL_IsEmpty(QueueLinked* queue)
{
	return queue->front == nullptr;
}