큐 자료구조의 개요와 구현

이번 글에서는 큐가 어떤 자료구조인지 알아보고, C++로 구현해 봅니다.

목차

1. 큐란

2. 큐의 기본 연산 구현

3. 데크의 구현

작성하면서 참고한 자료

C++ 자료구조론, Horowitz 외

http://www.yes24.com/Product/Goods/2656393

C++ 자료구조론 (2판) - YES24

---

큐란

큐(queue)는 리어(rear)라고 하는 한쪽 끝에서 삽입이 일어나고 프런트(front)라고 하는 반대쪽 끝에서 삭제가 일어나는 순서 리스트입니다. 제일 먼저 삽입되는 원소가 제일 먼저 삭제되기 때문에 선입선출(FIFO: First-In-First-Out) 리스트라고도 부릅니다.

 

큐 자료구조의 기본적인 연산으로는 원소 삽입, 원소 삭제, 큐가 비었는지 검사 등이 있습니다.

큐의 기본 연산 구현

큐 자료구조를 구현하는 쉬운 방법은 역시 1차원 배열을 이용하는 것입니다. 그런데 톱(top)의 위치 하나만 신경쓰면 되었던 스택 구현과 달리 큐 구현은 리어와 프런트를 모두 신경써야 합니다.

 

우선 구현해야 할 Queue 클래스와 테스트를 위한 main 함수는 다음과 같습니다.

#include <iostream>
using namespace std;

template <class T>
class Queue
{
public:
	Queue(int queueCapacity = 10);
	// 처음에 크기가 queueCapacity인 빈 큐를 생성

	bool IsEmpty() const;
	// 큐의 원소 수가 0이면 true, 아니면 false를 반환

	T& Front() const;
	// 큐의 프런트 원소를 반환

	T& Rear() const;
	// 큐의 리어 원소를 반환

	void Push(const T& item);
	// 큐의 리어에 item을 삽입

	void Pop();
	// 큐의 프런트 원소를 삭제

private:
	T* queue;
	// 큐 원소를 위한 배열

	int front;
	// 프런트 원소의 위치

	int rear;
	// 리어 원소의 위치

	int capacity;
	// 큐 배열의 크기
};

int main()
{
	Queue<char> charQueue(5);
	
	cout << charQueue.IsEmpty() << endl;
	charQueue.Push('A');
	charQueue.Push('B');
	charQueue.Push('C');
	charQueue.Push('D');
	charQueue.Push('E');
	charQueue.Push('F');
	charQueue.Pop();
	cout << charQueue.Front() << " " << charQueue.Rear() << endl;

	return 0;
}

 

가장 먼저, 큐의 첫 번째 원소 queue[0]을 항상 프런트로 고정한다고 생각해 봅시다. 그러면 삽입은 항상 큐의 마지막에서 일어나기 때문에 \(\Theta(1)\) 시간에 수행될 수 있지만, 삭제는 한 번 일어날 때마다 나머지 원소들을 왼쪽으로 한 칸씩 이동시켜야 하므로 \(\Theta(n)\) 시간이 걸립니다. 때문에 큐의 프런트 위치를 변수 front로 저장해 두는 것이 합리적입니다.

 

만약 삽입과 삭제가 여러 번 일어나서 rear가 capacity - 1과 같게 되고(즉, 리어가 큐의 배열 끝부분까지 옴) front > 0이 되면(프런트가 한 칸이라도 오른쪽으로 이동함) 배열 크기의 변경 없이 큐에 새 원소를 삽입하기 위해 rear를 맨 앞인 0으로 이동시켜야 합니다. 이것은 배열을 원형으로 보는 아이디어입니다.

if (rear == capacity - 1) rear = 0;
else rear++;

위와 같이 해도 되겠지만, 나머지(modulo) 연산을 사용하면,

rear = (rear + 1) % capacity;

이쪽이 조금 더 코드가 간단해집니다.

 

생성자(constructor)는 다음과 같이 구현할 수 있습니다.

template <class T>
Queue<T>::Queue(int queueCapacity) : capacity(queueCapacity)
{
	if (capacity < 1) throw "Queue capacity must be > 0";
	queue = new T[capacity];
	front = rear = 0;
}

 

큐가 비었는지 검사하는 연산을 생각해 볼까요. 원소를 삭제할 때는 front가 시계 방향으로 한 칸 전진하고, 삽입할 때는 rear가 시계 방향으로 한 칸 전진하기 때문에, 빈 큐는 반드시 front == rear를 만족할 것입니다. 그런데 큐가 꽉 차 있을때도 front == rear가 되기 때문에, 결국 front == rear를 비었는지의 판정 조건으로 사용하려면 큐가 꽉 차기 전에 큐의 배열 크기를 늘리도록 구현해야 함을 알 수 있습니다.

 

그래서 IsEmpty(), Front(), Rear()는 다음과 같이 구현합니다.

template <class T>
bool Queue<T>::IsEmpty() const
{
	return front == rear;
}

template <class T>
T& Queue<T>::Front() const
{
	if (IsEmpty()) throw "Queue is empty. No front element";
	return queue[(front + 1) % capacity];
}

template <class T>
T& Queue<T>::Rear() const
{
	if (IsEmpty()) throw "Queue is empty. No rear element";
	return queue[rear];
}

 

이제 Push()의 구현을 생각합니다. 스택 구현에서와 대부분 비슷하지만, 단순히 동적 배열의 크기를 두 배로 하는 함수를 사용할 경우 원하는 동작을 얻을 수가 없습니다. 큐가 원형으로 되어 있기 때문이죠. 그래서 큐의 원소들을 다음과 같이 복사하는 함수를 구현할 것입니다.

 

(1) 두 배 크기의 새 배열 newQueue를 생성한다

(2) queue[front+1] ~ queue[capacity-1]에 해당하는 원소들을 newQueue의 0에서부터 복사해 넣는다

(3) queue[0] ~ queue[rear]에 해당하는 원소들을 newQueue의 capacity-front-1에서부터 복사해 넣는다

 

상세한 구현은 다음과 같습니다.

template <class T>
void Queue<T>::Push(const T& item) 
{
	// 큐가 꽉 차 있는 경우 크기를 두 배로 한다
	if ((rear + 1) % capacity == front) {
		T* newQueue = new T[capacity * 2];

		int start = (front + 1) % capacity;
		if (start >= 2) {
			copy(queue + start, queue + capacity, newQueue);
			copy(queue, queue + rear + 1, newQueue + capacity - start);
		}
		else {
			copy(queue + start, queue + start + capacity - 1, newQueue);
		}

		front = 2 * capacity - 1;
		rear = capacity - 2;
		capacity *= 2;
		delete[] queue;
		queue = newQueue;
	}

	rear = (rear + 1) % capacity;
	queue[rear] = item;
}

 

Pop()의 구현은 다음과 같습니다.

template <class T>
void Queue<T>::Pop()
{
	if (IsEmpty()) throw "Queue is empty. Cannot delete.";
	front = (front + 1) % capacity;
	queue[front].~T(); // T의 소멸자
}

 

지금까지 구현한 내용으로 테스트를 해 보면 다음을 얻습니다!

데크의 구현

데크(deque: double-ended queue)는 삽입, 삭제를 양쪽 끝 어디에서나 할 수 있는 선형 리스트입니다. 클래스 Deque는 Queue의 파생 클래스(derived class)로 구현할 수 있습니다.

 

데크의 구현은 다음과 같습니다. (큐의 구현과 상속 포함)

#include <iostream>
using namespace std;

template <class T>
class Queue
{
public:
	Queue(int queueCapacity = 10);
	// 처음에 크기가 queueCapacity인 빈 큐를 생성

	bool IsEmpty() const;
	// 큐의 원소 수가 0이면 true, 아니면 false를 반환

	T& Front() const;
	// 큐의 프런트 원소를 반환

	T& Rear() const;
	// 큐의 리어 원소를 반환

	void Push(const T& item);
	// 큐의 리어에 item을 삽입

	void Pop();
	// 큐의 프런트 원소를 삭제

protected:
	T* queue;
	// 큐 원소를 위한 배열

	int front;
	// 프런트 원소의 위치

	int rear;
	// 리어 원소의 위치

	int capacity;
	// 큐 배열의 크기
};

template <class T>
Queue<T>::Queue(int queueCapacity) : capacity(queueCapacity)
{
	if (capacity < 1) throw "Queue capacity must be > 0";
	queue = new T[capacity];
	front = rear = 0;
}

template <class T>
bool Queue<T>::IsEmpty() const
{
	return front == rear;
}

template <class T>
T& Queue<T>::Front() const
{
	if (IsEmpty()) throw "Queue is empty. No front element";
	return queue[(front + 1) % capacity];
}

template <class T>
T& Queue<T>::Rear() const
{
	if (IsEmpty()) throw "Queue is empty. No rear element";
	return queue[rear];
}

template <class T>
void Queue<T>::Push(const T& item) 
{
	// 큐가 꽉 차 있는 경우 크기를 두 배로 한다
	if ((rear + 1) % capacity == front) {
		T* newQueue = new T[capacity * 2];

		int start = (front + 1) % capacity;
		if (start >= 2) {
			copy(queue + start, queue + capacity, newQueue);
			copy(queue, queue + rear + 1, newQueue + capacity - start);
		}
		else {
			copy(queue + start, queue + start + capacity - 1, newQueue);
		}

		front = 2 * capacity - 1;
		rear = capacity - 2;
		capacity *= 2;
		delete[] queue;
		queue = newQueue;
	}

	rear = (rear + 1) % capacity;
	queue[rear] = item;
}

template <class T>
void Queue<T>::Pop()
{
	if (IsEmpty()) throw "Queue is empty. Cannot delete.";
	front = (front + 1) % capacity;
	queue[front].~T(); // T의 소멸자
}

template <class T>
class Deque : public Queue<T>
{
public:
	Deque(int dequeCapacity = 10);
	// 처음에 크기가 dequeCapacity인 빈 데크를 생성

	void PushFront(const T& item);
	// 데크의 프런트에 item을 삽입

	void PopRear();
	// 데크의 리어 원소를 삭제
};

template <class T>
Deque<T>::Deque(int dequeCapacity) : Queue<T>(dequeCapacity)
{
	// Queue 생성자를 호출한다
}

template <class T>
void Deque<T>::PushFront(const T& item)
{
	// 데크가 꽉 차 있는 경우 크기를 두 배로 한다
	if ((this->rear + 1) % this->capacity == this->front) {
		T* newDeque = new T[this->capacity * 2];

		int start = (this->front + 1) % this->capacity;
		if (start >= 2) {
			copy(this->queue + start, this->queue + this->capacity, newDeque);
			copy(this->queue, this->queue + this->rear + 1, newDeque + this->capacity - start);
		}
		else {
			copy(this->queue + start, this->queue + start + this->capacity - 1, newDeque);
		}

		this->front = 2 * this->capacity - 1;
		this->rear = this->capacity - 2;
		this->capacity *= 2;
		delete[] this->queue;
		this->queue = newDeque;
	}

	this->front = (this->front - 1) % this->capacity;
	this->queue[this->front + 1] = item;
}

template <class T>
void Deque<T>::PopRear()
{
	if (this->IsEmpty()) throw "Deque is empty. Cannot delete.";
	this->rear = (this->rear - 1) % this->capacity;
	this->queue[this->rear + 1].~T(); // T의 소멸자
}

int main()
{
	Deque<char> charDeque(5);

	cout << charDeque.IsEmpty() << endl;
	charDeque.Push('C');
	charDeque.Push('D');
	charDeque.Push('E');
	charDeque.Push('F');
	charDeque.PushFront('B');
	charDeque.PushFront('A');
	charDeque.Pop();
	charDeque.PopRear();
	cout << charDeque.Front() << " " << charDeque.Rear() << endl;

	return 0;
}

[주의] 데크 구현 시 새로 구현하는 PushFront(), PopRear() 함수의 경우 this 포인터를 꼭 써줘야 한다고 합니다.

https://stackoverflow.com/questions/194492/accessing-protected-members-from-subclasses-gcc-vs-msvc

Accessing protected members from subclasses: gcc vs msvc

 

어쨌든 지금까지 구현한 내용으로 테스트를 해 보면 다음을 얻습니다!

---

다음 게시물에서는 또다른 중요한 자료구조인 연결 리스트를 알아보겠습니다.