[자료구조] Queue(큐), Deque(덱)

- 참조 문헌 및 사이트(Reference)

Data Structure : A Pseudocode Approach with C

Data Structure and Algorithm in C++

---

 

이번 글에서는 선형 리스트이며, 한쪽에서는 데이터의 삽입이 이루어지고, 반대편쪽에서는 데이터의 삭제만 이루어지는 큐(Queue)와 양쪽 끝에서 모두 데이터의 삽입과 삭제가 가능한 덱(Double-End Queue)에 대해서 알아보겠습니다.

 

Queue 큐

우선 큐부터 알아보도록 하겠습니다.

 

큐의 기본 컨셉은 위 그림과 같습니다. rear라는 한쪽 끝에서는 insert만 이루어지고, front라는 다른 한쪽 끝에서는 remove만 이루어집니다. 즉, 스택과는 반대로 FIFO(First in First out) 구조를 가지는 자료구조이며, 가장 먼저 들어간 데이터가 가장 먼저 나오게 됩니다. 이러한 구조를 가지고 있기 때문에 순서대로 처리해야되는 이벤트를 위해서 운영체제나 게임의 대기열이나 많은 곳에서 사용되고, BFS(Breadth-First Search) 알고리즘에서도 사용이 됩니다.

 

C++ STL인 <queue> 헤더에 큐가 구현되어 있으므로, 가능하면 구현없이 주어진 것을 사용하는 것이 좋지만.. 알아보는 시간이기 때문에 직접 한번 구현해보도록 하겠습니다.

 

우선 큐의 기본동작을 살펴보도록 하겠습니다.

 

1. Enqeueu

큐에 데이터를 삽입하는 동작이며, 그 데이터는 큐의 rear에 위치하게 됩니다.

여기서는 Enqueue라고 나와있으나, 조금 후에 실제로 구현을 할 때에는 push라는 이름으로 구현을 하도록 하겠습니다.(C++의 큐의 Enqueue 동작이 push함수로 이루어 집니다)

 

2. Dequeue

큐의 front에 위치한 데이터를 삭제하는 연산입니다. 큐의 front에 위치한 데이터가 삭제되며, 만약 큐가 비어있는 상태라면 Underflow 상태가 되어서 예외가 발생합니다.

Enqueue와 마찬가지로 Dequeue 연산은 pop이라는 함수로 구현을 하도록 하겠습니다.

 

3. front

큐의 front에 위치한 데이터의 값을 확인하는 연산입니다. 이 함수는 front에 위치한 값을 반환하며, 만약 큐에 아무런 데이터도 없다면 Dequeue와 마찬가지로 underflow 상태가 되어서 예외가 발생합니다.

 

추가적으로 큐가 비었는지 확인하는 empty, 큐의 데이터 개수를 확인하는 size 함수가 있습니다.

 

 

큐 역시 배열과 연결리스트 두 가지 방법으로 구현할 수 있는데, 우선 배열을 사용해서 구현해보도록 하겠습니다.

 

배열을 사용하게 되면, 배열의 사이즈를 초기에 결정하기 때문에 큐의 크기가 제한되게 됩니다. 선형으로 구현하여 데이터의 삽입과 삭제를 반복하다보면 마지막 배열에 도달 후에는 앞쪽의 배열이 비어있지만 오버플로우가 발생하게 됩니다. 따라서, 우리는 만약 큐의 끝에 도달하게 되면 다시 배열의 맨 앞쪽으로 보내서 연결시켜주는 원형큐(Circular Queue)로 구현을 해보겠습니다. 여기서 f는 front를 가리키는 index이고, r은 rear를 가리키는 index 입니다. 

 

전체 코드는 다음과 같습니다.

/* ArrayQueue.h */
#ifndef ARRAYQUEUE_H
#define ARRAYQUEUE_H
class QueueEmpty{};
class QueueFull{};

template<typename T>
class ArrayQueue
{
public:
	ArrayQueue(int Capacity = 100) : N(Capacity), n(0), f(0), r(0), Q(new T[Capacity]) {}
	~ArrayQueue();

	void push(const T& data);
	void pop();
	T& front() const;
	bool empty() const;
	int size() const;
	void print() const;

private:
	int N;
	int n;
	int f, r;
	T* Q;
};

template<typename T>
ArrayQueue<T>::~ArrayQueue()
{
	delete Q;
}

template<typename T>
void ArrayQueue<T>::push(const T& data)
{
	try {
		if (size() == N) throw QueueFull();

		Q[r] = data;
		r = (r + 1) % N;
		++n;
	}
	catch (QueueFull e) {
		cout << "Queue is Full\n";
		exit(2);
	}
}

template<typename T>
void ArrayQueue<T>::pop()
{
	try {
		if (empty()) throw QueueEmpty();

		f = (f + 1) % N;
		--n;
	}
	catch (QueueEmpty e) {
		cout << "Queue is Empty\n";
		exit(2);
	}
}

template<typename T>
T& ArrayQueue<T>::front() const
{
	try {
		if (empty()) throw QueueEmpty();

		return Q[f];
	}
	catch (QueueEmpty e) {
		cout << "Queue is Empty\n";
		exit(2);
	}
}

template<typename T>
bool ArrayQueue<T>::empty() const
{
	return (n == 0);
}

template<typename T>
int ArrayQueue<T>::size() const
{
	return n;
}

template<typename T>
void ArrayQueue<T>::print() const
{
	cout << "front [ ";
	for (int i = f; i != r; i = (i + 1) % N)
	{
		cout << Q[i] << " ";
	}
	cout << "] rear\n";
}
#endif

 

push를 할때마다 f의 값이 증가하게 됩니다. 그리고 pop을 할때마다 f의 값이 증가합니다. 즉, r쪽에 데이터가 삽입되고, f쪽에서 데이터가 삭제가 이루어집니다. 배열의 인덱스를 가지고 표현하기 때문에 데이터를 실제로 삭제를 하지는 않으며 인덱스가 삭제된 데이터를 가리키지 않을 뿐입니다. 그렇게 지정해둔 capacity 크기에 r이나 f가 도달하게 되면, 다시 배열의 맨 처음으로 돌아가서 가리키게 됩니다.

 

using namespace std;

#include <iostream>
#include "ArrayQueue.h"
int main() 
{
	ArrayQueue<int> q;
	q.push(5), q.print();
	q.push(3), q.print();
	q.push(7), q.print();
	q.push(15), q.print();
	q.pop(), q.print();
	q.push(9), q.print();
	q.push(2), q.print();
	q.front(), q.print();
	q.pop(), q.print();
	q.pop(), q.print();
	
	return 0;
}

위와 같은 코드를 실행하게 되면, 다음과 같은 결과를 얻을 수 있습니다.

 

 

다음으로는 연결리스트를 사용해서 큐를 구현해보도록 하겠습니다. 저번 리스트에 대한 게시글에서 구현해둔 Doubly Linked List를 사용해서 구현하려고 했지만, 그냥 간단한 노드를 새로 만들어서 큐 클래스 안에서 구현을 해보았습니다.

#ifndef LINKEDQUEUE_H
#define LINKEDQUEUE_H

class QueueEmpty{};

template<typename T>
class Node 
{
public:
	T data;
	Node<T> *next;

	Node() : next(nullptr) {}
	Node(T data, Node<T>* next) : data(data), next(next) {}
};

template<typename T>
class LinkedQueue
{
public :
	LinkedQueue() : n(0), head(nullptr), tail(nullptr) {}
	~LinkedQueue();

	void push(const T& data);
	T& front() const;
	void pop();
	int size() const;
	bool empty() const;
	void print() const;

private:
	int n;
	Node<T>* head;
	Node<T>* tail;
};

template<typename T>
LinkedQueue<T>::~LinkedQueue()
{
	Node<T>* delNode = head;
	while (head != nullptr)
	{
		head = head->next;
		delete delNode;
	}
}

template<typename T>
void LinkedQueue<T>::push(const T& data)
{
	if (empty())
	{
		head = new Node<T>(data, nullptr);
		tail = head;
	}
	else
	{
		tail->next = new Node<T>(data, nullptr);
		tail = tail->next;
	}

	++n;
}

template<typename T>
T& LinkedQueue<T>::front() const
{
	try {
		if (empty()) throw QueueEmpty();

		return head->data;
	}
	catch (QueueEmpty e) {
		cout << "Queue is empty\n";
		exit(2);
	}
}

template<typename T>
void LinkedQueue<T>::pop()
{
	try {
		if (empty()) throw QueueEmpty();

		Node<T>* delNode = head;
		head = head->next;

		delete delNode;
		--n;
		
		if (n == 0)
			tail = nullptr;
	}
	catch (QueueEmpty e) {
		cout << "Queue is empty\n";
		exit(2);
	}
}

template<typename T>
int LinkedQueue<T>::size() const
{
	return n;
}

template<typename T>
bool LinkedQueue<T>::empty() const
{
	return (n == 0);
}

template<typename T>
void LinkedQueue<T>::print() const
{
	Node<T>* walk = head;
	cout << "front [ ";
	while (walk != nullptr)
	{
		cout << walk->data << " ";
		walk = walk->next;
	}
	cout << "] rear\n";
}
#endif

스택과는 다르게 head와 tail, 두 개의 포인터가 필요합니다. 

push에서 tail->next에 새로운 데이터가 삽입되고, tail 포인터는 새로운 데이터 tail->next를 가리키게 됩니다.

pop에서는 head 노드가 삭제되고, head->next가 새로운 head가 됩니다.

만약 큐가 비어있다면, head와 tail 두 포인터 모두 null입니다.

 

위의 구현 내용을 통해서 큐의 시간 복잡도를 한번 살펴봅시다.

push와 pop 모두 특정 지점(리스트의 front와 rear)에서 이루어지기 때문에 삽입과 삭제의 시간복잡도는 O(1)이 될 것입니다. 마찬가지로 큐의 front의 값을 읽는 것 또한 O(1)의 시간복잡도를 가지게 됩니다.

Deque 덱

덱(Deque)은 처음에 설명했듯이, Double-End Queue의 약자로 양방향으로 데이터의 삽입과 삭제가 가능한 자료구조입니다. 덱은 C++ STL에 <deque> 헤더에서 지원합니다. 하지만 어떻게 구현되어있는지 한 번 보도록 합시다.

 

큐와 사용한 노드 클래스에 링크를 하나 더 추가해서 이중 연결리스트로 구현했습니다. 그리고 큐의 push와 pop 대신에 양방향으로 삽입과 삭제를 위해서 push_back, push_front, pop_back, pop_front 메소드를 사용합니다. 그리고 rear에 있는 값을 얻기 위해서 back 메소드도 추가되었습니다.

/* LinkedDeque.h */
#ifndef LINKEDDEQUE_H
#define LINKEDDEQUE_H

class DequeEmpty{};

template<typename T>
class Node
{
public:
	T data;
	Node<T> *next, *prev;

	Node() : next(nullptr) {}
	Node(T data, Node<T>* next, Node<T>* prev) : data(data), next(next), prev(prev) {}
};

template<typename T>
class LinkedDeque
{
public:
	LinkedDeque() : n(0), head(nullptr), tail(nullptr) {}
	~LinkedDeque();

	void push_front(const T& data);
	void pop_front();
	T& front() const;
	void push_back(const T& data);
	void pop_back();
	T& back() const;
	int size() const;
	bool empty() const;
	void print() const;

private:
	int n;
	Node<T>* head;
	Node<T>* tail;
};

template<typename T>
LinkedDeque<T>::~LinkedDeque()
{
	Node<T>* delNode = head;
	while (head != nullptr)
	{
		head = head->next;
		delete delNode;
	}
}

template<typename T>
void LinkedDeque<T>::push_front(const T& data)
{
	if (empty())
	{
		head = new Node<T>(data, nullptr, nullptr);
		tail = head;
	}
	else
	{
		head = new Node<T>(data, head, nullptr);
		head->next->prev = head;
	}

	++n;
}

template<typename T>
void LinkedDeque<T>::pop_front()
{
	try {
		if (empty()) throw DequeEmpty();

		Node<T>* delNode = head;
		head = head->next;
		head->prev = nullptr;

		delete delNode;
		--n;

		if (n == 0)
			tail = nullptr;
	}
	catch (DequeEmpty e) {
		cout << "Deque is Empty\n";
		exit(2);
	}
}

template<typename T>
T& LinkedDeque<T>::front() const
{
	try {
		if (empty()) throw DequeEmpty();

		return head->data;
	}
	catch (DequeEmpty e) {
		cout << "Deque is Empty\n";
		exit(2);
	}
}

template<typename T>
void LinkedDeque<T>::push_back(const T& data)
{
	if (empty())
	{
		head = new Node<T>(data, nullptr, nullptr);
		tail = head;
	}
	else
	{
		tail = new Node<T>(data, nullptr, tail);
		tail->prev->next = tail;
	}

	++n;
}

template<typename T>
void LinkedDeque<T>::pop_back()
{
	try {
		if (empty()) throw DequeEmpty();

		Node<T>* delNode = tail;
		tail = tail->prev;
		tail->next = nullptr;

		delete delNode;
		--n;

		if (n == 0)
			head = nullptr;
	}
	catch (DequeEmpty e) {
		cout << "Deque is Empty\n";
		exit(2);
	}
}

template<typename T>
T& LinkedDeque<T>::back() const
{
	try {
		if (empty()) throw DequeEmpty();

		return tail->data;
	}
	catch (DequeEmpty e) {
		cout << "Deque is Empty\n";
		exit(2);
	}
}

template<typename T>
int LinkedDeque<T>::size() const
{
	return n;
}

template<typename T>
bool LinkedDeque<T>::empty() const
{
	return (n == 0);
}

template<typename T>
void LinkedDeque<T>::print() const
{
	Node<T>* walk = head;
	cout << "front [ ";
	while (walk != nullptr)
	{
		cout << walk->data << " ";
		walk = walk->next;
	}
	cout << "] rear\n";
}

#endif

노드 클래스에 prev 포인터를 추가해서 다음 노드뿐만 아니라 이전 노드도 참조할 수 있게 했습니다. 이것은 pop_back을 했을 때, tail 포인터를 마지막 이전 값을 가리키기 위해서 사용됩니다.

push_front에서 front 위치에 데이터가 삽입됩니다. push_pop에서는 front에 위치한 데이터가 삭제됩니다.(head 포인터)

push_back, pop_back에서는 rear에서 데이터가 삽입 및 삭제됩니다.(tail 포인터)

front와 back 함수에서 양 끝의 데이터를 확인할 수 있습니다.

 

using namespace std;

#include <iostream>
#include "LinkedDeque.h"
int main() 
{
	LinkedDeque<int> dq;

	dq.push_front(5), dq.print();
	dq.push_front(1), dq.print();
	dq.push_front(2), dq.print();
	dq.push_back(15), dq.print();
	dq.front(); dq.print();
	dq.push_front(7), dq.print();
	dq.push_back(6), dq.print();
	dq.back(); dq.print();
	dq.push_front(11), dq.print();
	dq.push_front(8), dq.print();
	dq.pop_back(), dq.print();
	dq.pop_front(), dq.print();
	return 0;
}

위 코드를 실행하면 아래와 같은 결과를 얻을 수 있습니다.