큐 자료구조에 대해 살펴본 후 이를 배열과 단일 링크드리스트를 이용해 구현해봅시다.
큐(Queue)
큐는 가장 먼저 들어온 자료가 가장 먼저 나가는 first-in first-out(FIFO, 선입선출)의 자료구조입니다. 일반적으로 자료의 삽입(enqueue)은 큐의 맨 끝(back, rear)에서 이뤄지고, 삭제(dequeue)는 큐의 맨 앞(front, head)에서 이루어집니다.
큐 ADT
큐에는 자료를 삽입하는 enqueue와 자료를 삭제하는 dequeue 기능이 필수적으로 필요합니다. 편의에 따라 front, size, empty 등이 구현될 수 있습니다.
// C++ code
class Queue {
void enqueue(string str) {}
string dequeue() {}
string front() {}
int size() {}
bool empty() {}
...
};큐의 구현
배열을 통한 구현
배열을 통해 큐를 구현할 때는 메모리의 효율적 사용을 위해 원형 배열(맨 끝 cell의 다음이 맨 첫번째 cell이 되는 형태의 배열)을 사용합니다. 큐의 맨 처음 인덱스를 frontIndex의 약자 f, 마지막 인덱스를 rearIndex의 약자 r로 표현하겠습니다.
#include<iostream>
#include<string>
using namespace std;
class Queue {
private:
string* arr;
int f, r; // f는 큐의 첫 cell의 idx, r는 마지막 cell의 idx
int n; // 배열의 크기(큐가 담을 수 있는 요소 개수의 최대치)
public:
Queue(int size) {
arr = new string[size];
f = r = -1;
this->n = size;
}
void enqueue(string str) {
if (f == -1) {
f = r = 0;
arr[0] = str;
}
else {
r = (r + 1) % n;
if (f == r) {
cout << "담을 수 있는 최대 개수 초과!\n";
r = (n + r - 1) % n;
return;
}
arr[r] = str;
}
}
string front() {
if (empty()) { cout << "큐에 아무 값이 없으므로 0을 반환합니다.\n"; return "0"; }
else return arr[f];
}
string dequeue() {
if (empty()) { cout << "더이상 뺄 요소가 없으므로 0을 반환합니다.\n"; return "0"; }
else {
string frontData = front();
f = (f + 1) % n;
return frontData;
}
}
int size() { // 큐에 있는 요소의 개수
if (r == 4 && f == 0) return 5;
return (n + r - f + 1) % n;
}
bool empty() {
return size() == 0 ? true : false;
}
void show() {
for (auto i = f; true; i = (i + 1) % n) {
cout << arr[i] << " ";
if (i == r) break;
}
cout << endl;
}
};
링크드리스트를 통한 구현
다음 코드는 링크드리스트를 이용하여 큐를 구현한 코드입니다.
class Node {
public:
string data;
Node* next;
Node(string e) {
data = e;
next = nullptr;
}
};
class Linked {
public:
Node* head;
Node* tail;
Linked() {
head = nullptr;
tail = nullptr;
}
void removeFront() {
if (empty()) cout << "더 이상 지울 수 없습니다." << endl;
else {
Node* front = head;
head = head->next;
delete front;
}
}
string front() {
if (empty()) { cout << "값이 없습니다."; return "none"; }
else {
return head->data;
}
}
bool empty() {
if (head == nullptr) return true;
else return false;
}
void showList() {
if (empty()) cout << "값이 없습니다."<< endl;
else {
for (auto i = head; i != nullptr; i = i->next)
{
cout << i->data << " ";
}
cout << endl;
}
}
void addBack(string x) {
Node* n = new Node(x);
if (empty()) {
head = n;
tail = n;
}
else {
tail->next = n;
tail = n;
}
}
};
class Queue {
private:
Linked list;
public:
void enqueue(string str) {
list.addBack(str);
}
string front() {
if (empty()) { cout << "큐에 아무 값이 없으므로 0을 반환합니다.\n"; return "0"; }
else return list.front();
}
string dequeue() {
if (empty()) { cout << "더이상 뺄 요소가 없으므로 0을 반환합니다.\n"; return "0"; }
else {
string frontData = front();
list.removeFront();
return frontData;
}
}
int size() { // 큐에 있는 요소의 개수
if (list.head == nullptr) return 0;
int i = 0;
for (auto p = list.head; true; p = p->next) {
i++;
if (p == list.tail) break;
}
return i;
}
bool empty() {
return size() == 0 ? true : false;
}
void show() {
if (empty()) return;
for (auto i = list.head; true; i = i->next) {
cout << i->data << " ";
if (i == list.tail) break;
}
cout << endl;
}
};링크드리스트로 구현했을 때는 배열과 다르게 큐의 크기가 가변적입니다.
큐의 동작
두 가지 방법으로 구현된 큐가 올바르게 작동하고 있는지 확인하기 위해 다음과 같은 상황을 설정합시다. 단, 배열로 구현한 스택의 최대 크기는 5라고 가정합시다.
- 바나나, 사과, 딸기, 키위, 망고, 쓰레기값을 순서대로 enqueue한다.
- 값을 두 번 dequeue한다.
- 배를 enqueue한다.
이를 메인함수로 나타내면 다음과 같습니다.
int main() {
Queue Q = Queue(5);//배열로 구현했을 때
Queue Q;//linkedList로 구현했을 때
Q.enqueue("바나나");
Q.enqueue("사과");
Q.enqueue("딸기");
Q.enqueue("키위");
Q.enqueue("망고");
Q.show(); // array구현과 linkedList구현의 차이를 나타내기 위해 넣은 코드
Q.enqueue("쓰레기값");
Q.dequeue();
Q.dequeue();
Q.show();
Q.enqueue("배");
Q.show();
}먼저 배열로 구현한 큐에서는 다음과 같은 결과가 나타납니다.
배열의 크기가 5이므로 배열로 구현한 큐는 다섯 개 이상의 값을 담을 수 없습니다. 따라서 여섯번 째 값인 "쓰레기값"은 큐에 들어가지 않습니다. 한편, 원형 배열로 구현하였으므로 두 번 dequeue한 후 "배"를 enqueue하여도 정상적으로 큐에 값이 들어가게 됩니다.
다음은 링크드리스트로 구현했을 때의 결과입니다.
링크드리스트로 구현하면 최대 크기 제한이 없어지므로 "쓰레기값" 역시 큐에 들어가게 됩니다.
Applications of Queue
큐의 활용 예시
큐는 우리가 일상생활에서 줄을 선 것과 비슷하다고 할 수 있습니다. 따라서 은행 대기 순번 관리 체계같은 곳에서 활용할 수 있습니다. 비슷한 예로 프린터의 프린트 목록 대기열같은 선입선출이 요구되는 곳에서도 큐가 사용됩니다. 이 뿐만 아니라 큐는 다른 자료구조를 구현할 때도 사용할 수 있습니다.
Deque(데크, 덱)
Deque는 선입선출의 구조인 Que와 달리, front와 tail 모두에서 push와 pop이 가능한 자료구조를 말합니다.
