[C++] 원형 큐 (Circular Queue) 구현하기

원형 큐를 사용하는 이유

자료구조를 배우셨다면 큐 (Queue) 에 대해서 배우셨을 겁니다.

선입선출 (FIFO) 의 구조를 가지기 때문에, 수많은 알고리즘에서 큐가 사용됩니다.

만약 큐를 배열에 저장한다면 다음과 같은 상황이 만들어집니다.

 

이 상황은 어떤 상황일까요?

현재 큐에는 7, 5 라는 값이 들어있고, 출력 시 순서대로 7, 5 이 출력됨을 아실겁니다.

(만약 이 부분이 이해가지 않는다면, 큐를 공부하시면 되겠습니다.)

이 상황에서, 인덱스가 0인 공간을 활용하려면 어떻게 해야 할까요?

물론 배열의 모든 원소들을 앞당겨줄수도 있지만, 비용상의 문제로 이러한 작업은 비효율적입니다.

즉, 앞당김 작업없이 지속적인 큐의 사용을 위해서 우리는 원형 큐를 사용해야 합니다.

 

 

 

동작 원리

큐를 이해하고 있다면, 원형 큐는 간단히 이해할 수 있습니다.

위와 같은 상황을 가정해봅시다.

 

현재 큐에는 5, 8 의 값이 들어있습니다.

여기에서 값을 하나 추가하면, rear는 어디로 가야할까요?

 

맞습니다. 모듈러 (%) 연산을 통해서 다시 0번 자리로 가면 됩니다.

다음과 같이 말입니다.

 

인덱스가 순환하기 때문에, enqueue, dequeue 과정에서

배열을 앞당기지 않아도 됩니다.

이런 식으로 순환하는 과정때문에 원형 큐라는 이름이 붙게된 것입니다.

 

 

 

구현 (C++)

#include <iostream>

#define MAX_QUEUE	11

using namespace std;

template<typename T>
class SimpleQueue {
public:
	T arr[MAX_QUEUE];
	int f = 0, r = 0;

	T front() { return arr[f]; }
	bool isEmpty() { return (f == r); }
	bool isFull() { return ((r + 1) % MAX_QUEUE == f); }
	int size() { return (f > r ? f - r : r - f); }
	void enqueue(T element) 
	{ 
		if (isFull()) cout << "Queue is FULL!\n";
		else 
		{
			arr[r++] = element;
			r %= MAX_QUEUE;
		}
	}
	void dequeue() 
	{
		if (isEmpty()) cout << "Queue is Empty!\n";
		else f = (f + 1) %= MAX_QUEUE;
	}
};

int main(void)
{
	SimpleQueue<int> q;

	cout << q.size() << '\n';
	for (int i = 0; i < 8; i++)
	{
		q.enqueue(i);
	}
	cout << q.size() << '\n';

	return 0;
}