스택과 마찬가지로 큐도 많이 사용되는 자료구조 중 하나이다. 이 포스트에서는 선형큐의 한계와 이를 극복하기 위해 원형큐를 구현하는 것을 정리하겠다.
1. 큐란?
큐의 형태를 쉽게 이해하고 싶다면, 종이컵 디스펜서를 생각해보면 된다. 종이컵 디스펜서에서 종이컵을 꺼낼 때 우리는 가장 처음에 들어갔던 종이컵을 꺼내게 된다. 또 다른 예시로 무언가를 기다리는 줄을 생각하면 된다. 이도 마찬가지로 가장 먼저 기다리던 사람한테 가장 먼저 차례가 오게 된다. 이러한 입출력 형태를 FIFO(First In First Out)이라고 한다.
1, 2, 3을 순서대로 삽입했을 때 큐의 형태를 그림으로 나타낸 것이다. 큐에 있는 1, 2, 3을 큐의 요소라고 부르며, 삽입이 일어나는 곳을 rear, 삭제가 일어나는 곳을 front라고 한다.
또한, 큐에 요소가 하나도 들어있지 않을 때는 공백(empty) 상태라 하고 꽉 차서 더 이상 요소를 집어넣지 못하 경우 포화(full) 상태라고 한다.
다음과 같이 front에서 빼오는 연산을 dequeue, 큐의 rear에 새로운 요소를 추가하는 연산을 enqueue라고 한다. dequeue의 경우 큐가 공백(empty) 상태인지 확인해야 하며, enqueue의 경우 큐가 포화(full) 상태인지 확인해야 한다.
2. 선형 큐의 구현
선형 큐는 다음과 같이 배열을 통해 구현할 수 있다. 구현하는데 사용한 언어는 C++이고 템플릿 클래스로 구현하였다.
#include <iostream>
using namespace std;
template <class T> class Queue {
private:
int front;
int rear;
int size;
T *elements;
public:
Queue(int size) {
front = 0;
rear = 0;
this->size = size;
elements = new T[size];
}
~Queue() {
delete[] elements;
}
bool isEmpty() {
return front == rear;
}
bool isFull() {
return rear == size;
}
void enqueue(T elem) {
if (isFull()) {
cout << "Error : Queue is Full!" << endl;
} else {
elements[rear++] = elem;
}
}
T dequeue() {
if (isEmpty()) {
cout << "Error : Queue is Empty!" << endl;
} else {
return elements[front++];
}
}
T peek() {
if (isEmpty()) {
cout << "Error : Queue is Empty!" << endl;
} else {
return elements[front + 1];
}
}
void display() {
for (int i = front; i < rear; i++) {
cout << elements[i] << " ";
}
cout << endl;
}
};선형 큐는 이해하기도 구현하기도 쉽지만 한 가지 문제점이 있다. 다음 코드를 실행해본다고 생각해보자.
#include "queue.h"
int main() {
Queue<int> queue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
queue.display();
cout << queue.dequeue() << endl;
queue.enqueue(6);
queue.display();
return 0;
}큐의 사이즈는 5이고 5개의 요소를 삽입하고 하나를 빼고 하나를 삽입한다. 그러면 안의 들어간 요소의 개수가 5개를 넘어가는 일이 없어서 정상적으로 삽입되어야 하지만, queue.enqueue(6);에서 큐가 포화 상태라는 메세지를 받는다.
5개의 요소를 삽입했을 때 배열은 다음과 같은 형태가 된다.
하나의 요소를 뺐을 때 배열의 형태는 다음과 같다. 여기서 문제를 알 수 있다. rear와 front의 값이 자꾸 증가하기만 해서 결국 배열의 앞부분이 비어있더라도 더이상 삽입하지 못하는 경우가 발생한다. 이와 같은 공간 낭비를 더 이상 삽입할 공간이 없을 때 배열의 요소들의 인덱스를 하나씩 당겨주는 방법으로 해결할 수 있지만, 원형 큐로 구현하면 더 쉽게 해결할 수 있다.
3. 원형 큐의 구현
마찬가지로 c++로 구현한 소스 코드이다.
#include <iostream>
using namespace std;
template <class T> class Queue {
private:
int front;
int rear;
int size;
T *elements;
public:
Queue(int size) {
front = 0;
rear = 0;
this->size = size + 1;
elements = new T[size];
}
~Queue() {
delete[] elements;
}
bool isEmpty() {
return front == rear;
}
bool isFull() {
return (rear + 1) % size == front;
}
void enqueue(T elem) {
if (isFull()) {
cout << "Error : Queue is Full!" << endl;
} else {
rear = (rear + 1) % size;
elements[rear] = elem;
}
}
T dequeue() {
if (isEmpty()) {
cout << "Error : Queue is Empty!" << endl;
} else {
front = (front + 1) % size;
return elements[front];
}
}
T peek() {
if (isEmpty()) {
cout << "Error : Queue is Empty!" << endl;
} else {
return elements[(front + 1) % size];
}
}
void display() {
int maxi = (front < rear) ? rear : rear + size;
for (int i = front + 1; i <= maxi; i++) {
cout << elements[i % size] << " ";
}
cout << endl;
}
};선형 큐의 문제점을 배열을 원형인 것처럼 활용함으로써 해결할 수 있다. 즉 이전과는 다르게 front와 rear가 배열의 끝 인덱스에서 증가하면은 인덱스 0을 가리키도록 하면 된다. 이는 나머지 연산으로 쉽게 구현할 수 있다. 이 코드에서 front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소를 가리킨다.
아까와 마찬가지로 5개의 요소를 삽입한 모습이다. 원형큐로 구현할 시에 공백 상태와 포화 상태를 구분하지 못하는 문제가 생기는데, 이는 해결하기 위해 인덱스 하나는 비워두었다. 위의 그림을 예로 들면, 인덱스를 하나 비워두지 않으면 공백 상태, 포화 상태 모두 rear와 front가 인덱스 0을 가리키는 문제가 생긴다.
#include "queue.h"
int main() {
Queue<int> queue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
queue.display();
cout << queue.dequeue() << endl;
queue.enqueue(6);
queue.display();
return 0;
}다시 위의 코드를 작동시켜보면 선형 큐로 구현했을 때와는 달리 포화 상태라는 메세지 없이 정상적으로 삽입되는 것을 확인할 수 있다.
4. 참조
천인국, 최영규, 「C++로 쉽게 풀어쓴 자료구조」, 생능출판사, 2019년
