큐(Queue)는 요소들의 집합을 저장하는 추상 자료구조입니다. 큐는 FIFO(First In, First Out, 선입선출) 방식을 따르며, 가장 먼저 삽입된 요소가 가장 먼저 삭제됩니다.
왜 순환 큐가 필요한가?
큐는 대표적인 선형 자료구조 중 하나입니다. 하지만 배열로 큐를 구현하면 몇 가지 문제가 발생할 수 있습니다. 삽입과 삭제 연산이 반복되면서 front와 rear 포인터가 계속 뒤로 이동하게 되는데, 어느 순간 실제로는 여유 공간이 남아 있음에도 불구하고 논리적인 제약 때문에 새 요소를 삽입할 수 없는 상태처럼 보이게 됩니다. 이렇게 낭비되는 공간 없이 메모리를 효율적으로 활용하기 위해 순환 큐(Circular Queue) 자료구조를 사용합니다.
순환 큐는 마지막 위치가 첫 번째 위치와 연결되어 마치 원형을 이루는 것처럼 동작하는 큐입니다. 덕분에 rear가 배열의 끝에 도달하더라도 다시 처음으로 돌아가 빈 공간을 재활용할 수 있습니다.
알고리즘
삽입 연산 — insert(queue, key)
begin
if front = 0 and rear = n – 1, or front = rear + 1, then queue is full, and return
otherwise
if front = -1, then front = 0 and rear = 0
else
if rear = n – 1, then, rear = 0, else rear := rear + 1
queue[rear] = key
end삽입 시에는 큐가 가득 찼는지 먼저 확인합니다. front가 0이면서 rear가 n-1인 경우, 또는 front가 rear + 1과 같은 경우가 꽉 찬 상태입니다. 빈 공간이 있다면 rear를 한 칸 이동시키거나 배열 끝에서 처음으로 되돌린 후 값을 저장합니다.
삭제 연산 — delete(queue)
begin
if front = -1 then queue is empty, and return
otherwise
item := queue[front]
if front = rear, then front and rear will be -1
else
if front = n – 1, then front := 0 else front := front + 1
end삭제 시에는 큐가 비어 있는지(front == -1) 먼저 확인합니다. 요소를 꺼낸 후, front와 rear가 같다면 큐가 비게 된 것이므로 두 포인터를 모두 초기값(-1)으로 되돌립니다. 그렇지 않으면 front를 한 칸 앞으로 이동하거나 배열 끝에서 처음으로 순환시킵니다.
C++ 전체 구현 예제
#include <iostream>
using namespace std;
int cqueue[5];
int front = -1, rear = -1, n=5;
void insertCQ(int val) {
if ((front == 0 && rear == n-1) || (front == rear+1)) {
cout<<"Queue Overflow \n";
return;
}
if (front == -1) {
front = 0;
rear = 0;
}
else {
if (rear == n - 1)
rear = 0;
else
rear = rear + 1;
}
cqueue[rear] = val ;
}
void deleteCQ() {
if (front == -1) {
cout<<"Queue Underflow\n";
return ;
}
cout<<"Element deleted from queue is : "<<cqueue[front]<<endl;
if (front == rear) {
front = -1;
rear = -1;
}
else {
if (front == n - 1)
front = 0;
else
front = front + 1;
}
}
void displayCQ() {
int f = front, r = rear;
if (front == -1) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are :\n";
if (f <= r) {
while (f <= r){
cout<<cqueue[f]<<" ";
f++;
}
}
else {
while (f <= n - 1) {
cout<<cqueue[f]<<" ";
f++;
}
f = 0;
while (f <= r) {
cout<<cqueue[f]<<" ";
f++;
}
}
cout<<endl;
}
int main() {
int ch, val;
cout<<"1)Insert\n";
cout<<"2)Delete\n";
cout<<"3)Display\n";
cout<<"4)Exit\n";
do {
cout<<"Enter choice : "<<endl;
cin>>ch;
switch(ch) {
case 1:
cout<<"Input for insertion: "<<endl;
cin>>val;
insertCQ(val);
break;
case 2:
deleteCQ();
break;
case 3:
displayCQ();
break;
case 4:
cout<<"Exit\n";
break;
default: cout<<"Incorrect!\n";
}
} while(ch != 4);
return 0;
}위 코드는 크기 5의 배열 기반 순환 큐를 구현한 것으로, 삽입(insertCQ), 삭제(deleteCQ), 출력(displayCQ) 세 가지 기능을 메뉴 형태로 제공합니다. 특히 출력 함수에서는 front가 rear보다 뒤에 있는 경우(순환이 발생한 경우) 배열을 두 구간으로 나누어 순서대로 출력합니다.
실행 결과
1)Insert 2)Delete 3)Display 4)Exit Enter choice : 1 Input for insertion: 10 Enter choice : 1 Input for insertion: 20 Enter choice : 1 Input for insertion: 30 Enter choice : 1 Input for insertion: 40 Enter choice : 1 Input for insertion: 50 Enter choice : 3 Queue elements are : 10 20 30 40 50 Enter choice : 2 Element deleted from queue is : 10 Enter choice : 2 Element deleted from queue is : 20 Enter choice : 3 Queue elements are : 30 40 50 Enter choice : 4 Exit
실행 결과를 보면 10부터 50까지 다섯 개의 요소를 삽입한 뒤, 10과 20을 차례로 삭제했을 때 나머지 요소들이 FIFO 순서대로 올바르게 유지되는 것을 확인할 수 있습니다. 삭제로 생긴 앞쪽 공간은 이후 rear가 배열 끝에 도달하면 다시 재사용되므로, 일반 선형 큐에서 발생하는 메모리 낭비 문제가 해결됩니다.