자료구조 : 큐(Queue) 이해하고, 구현하기 in C++

Queue 1분만에 파악하기!

큐(Queue)은  선입선출 (First In First Out, FIFO) 자료구조이다.

먼저 넣은 자료가 가장 마지막에 나오는 스택(Stack)과는 반대이다. >> 스택에 대한 포스트를 참조

큐에 자료를 넣는 행동은 Put(또는 Enqueue), 꺼내는 행동은 Get(또는 Dequeue)이라고 하며

큐의 제일 앞에 있는 자료를 Front(또는 Head), 가장 뒤의 자료를 Rear(또는 Tail)라고 한다.

또한 큐가 꽉 차서 더 이상 큐에 자료를 넣을 수 없는 경우를 Overflow라고 하고,

큐가 비어있어 자료를 더이상 Get(Dequeue)할 수 없는 경우를 Underflow라고 한다.

Queue, 어디에 쓸까?

'Queue'는 줄, 대기행렬이라는 뜻을 가지고 있다. 따라서 큐를 이해하기에는 화장실 줄을 생각하면 쉽다.

즉, 먼저 와서 기다린 사람이 먼저 나오는 것이다!

이러한 큐는 프린터의 출력, 프로세스 관리 등 입력된 시간 순서대로 처리되어야 할 상황에 자주 응용되는 자료구조다.

Queue의 종류

큐에는 여러가지 종류가 있다.

원형 큐(Circular Queue)와 우선순위 큐(Priority Queue) 등이 있지만

지금은 선형 큐만 구현해 보기로 한다.

Queue의 추상자료형 (Abstract Data Type)

큐의 ADT를 알아 보도록 하자.

구현 코드가 C++로 되어있기 때문에 ADT도 C++ 스타일로 적겠다.

다음 ADT를 가지고 여러분이 직접 코드를 작성해보고 테스트 해 보면 좋을 것이다!

template <typename T>

class Queue {

public:

Queue(); // 생성자

~Queue(); // 소멸자

void Enqueue(const T&); // 큐에 자료 넣기

void Dequeue(); // 큐에서 자료 빼내기

T& Front(); // 큐 제일 앞의 자료

bool IsEmpty(); // 큐가 비어있는지 검사

private:

int capacity; // 큐의 크기

int front = -1;

int rear;

}

Queue의 구현

이전 강의 스택처럼 큐를 배열로 구현하면 너무 간단하지만 큐가 한 번 꽉차면 다시 사용할 수 없기 때문에 실용적이지 않아서 헤드 노드가 있는 원형 연결리스트(Circular Linked list with head node) 방식으로 구현 해 보았다. 이런식으로 하면 큐의 용량에 관계 없이 계속해서 큐를 사용할 수 있다. 따라서 위의 ADT에서 private 변수들 모두를 지우고, 헤드 노드인 Node* head를 만든다.

코드는 아래에 구현해 놓았다. 또는 Github에서 직접 코드를 다운받을 수 있다. >> Github 링크

/*
	Linear Queue (Linked List) in C++
	@author: PARK JI EUN
	@date: 2016.12.19
	*/
	#include <iostream>
	using namespace std;
	template <typename T>
	class Queue;
	/** Linked List Node **/
	template <typename T>
	class Node {
	friend class Queue<T>;
	public:
	Node():link(0) {}; // init link = 0
	Node(const T&);
	private:
	T data;
	Node* link;
	};
	template <typename T>
	Node<T>::Node(const T& _data) {
	data = _data;
	link = 0;
	}
	/** Linear Queue implemented with Linked List **/
	template <typename T>
	class Queue {
	friend ostream& operator<<(ostream& os, Queue queue) {
	Node<T>* current = queue.head;
	while (current->link != queue.head) {
	current = current->link;
	os << current->data << " ";
	}
	os << endl;
	return os;
	};
	public:
	Queue();
	void Enqueue(const T&); // Push data to the queue
	void Dequeue(); // Remove data from the queue
	T& Front(); // Get First data of the queue
	T& Rear(); // Get Last data of the queue
	bool IsEmpty(); // Check if the queue is Empty or not
	private:
	Node<T>* head; // head node
	};
	template <typename T>
	Queue<T>::Queue() {
	head->link = head;
	}
	template <typename T>
	bool Queue<T>::IsEmpty() {
	bool isEmpty = false;
	// if head points themself, that's empty!
	if (head->link == head) {
	isEmpty = true;
	cout << "\tQueue is Empty." << endl;
	}
	return isEmpty;
	}
	template <typename T>
	void Queue<T>::Enqueue(const T& data) {
	Node<T>* newNode = new Node<T>(data);
	if (IsEmpty()) {
	head->link = newNode;
	} else {
	// Find the Last node
	Node<T>* current = head;
	while (current->link != head) {
	current = current->link;
	}
	current->link = newNode;
	}
	newNode->link = head;
	}
	template <typename T>
	void Queue<T>::Dequeue() {
	if (!IsEmpty()) {
	// now, headnode points 2nd node
	Node<T>* firstNode = head->link;
	head->link = firstNode->link;
	delete firstNode;
	}
	}
	template <typename T>
	T& Queue<T>::Front() {
	T data = NULL;
	if (!IsEmpty()) {
	// return data of first element
	data = head->link->data;
	}
	return data;
	}
	template <typename T>
	T& Queue<T>::Rear() {
	T data = NULL;
	if (!IsEmpty()) {
	// Find the Last node
	Node<T>* current = head;
	while (current->link != head) {
	current = current->link;
	}
	data = current->data;
	}
	return data;
	}
	int main(void)
	{
	Queue<char> queue;
	int select = 0;
	char data;
	while (true) {
	cout << "\n- Select Command -" << endl;
	cout << "1:Enqueue, 2:Dequeue, 3:Front, 4:Rear, 5:Display, 0: Quit\n\t>> ";
	cin >> select;
	switch (select) {
	case 1:
	cout << "\tEnter Data to Enqueue >> ";
	cin >> data;
	queue.Enqueue(data);
	cout << queue;
	break;
	case 2:
	queue.Dequeue();
	cout << queue;
	break;
	case 3:
	cout << "\tFront >> " << queue.Front() << endl;
	break;
	case 4:
	cout << "\tRear >> " << queue.Rear() << endl;
	break;
	case 5:
	cout << queue;
	break;
	case 0:
	cout << "BYE!" << endl;
	exit(0);
	default:
	cout << "WRONG INPUT" << endl;
	cout << "Re-Enter" << endl;
	break;
	}
	}
	system("pause");
	return 0;
	}

Queue 프로그램 돌려보기

다음은 구현한 코드를 실행해 본 결과다. (Xcode에서 돌려본 것입니다.)

각 명령마다 큐의 상황을 그림으로 그려놓았으니 참조하면서 보면 좋을 것 같다.

실제론 더 잘그리지만 ㅎㅎ 타블렛의 한계로 조금 구불구불해서 아쉽다...