큐(Queue)는 여러 개의 요소를 담는 추상 자료구조(Abstract Data Structure)입니다. 큐는 FIFO(First In First Out, 선입선출) 방식으로 동작하며, 가장 먼저 삽입된 요소가 가장 먼저 삭제됩니다.
원형 큐(Circular Queue)는 큐의 한 종류로, 마지막 위치가 첫 번째 위치와 연결되어 하나의 원을 이루는 구조입니다. 일반적인 선형 큐와 달리 배열 뒤쪽이 가득 차더라도 앞쪽에 빈 공간이 있다면 그 공간을 재활용할 수 있어 메모리 활용도가 높다는 장점이 있습니다.
다음은 C++로 원형 큐를 구현한 프로그램입니다.
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;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
1)Insert 2)Delete 3)Display 4)Exit Enter choice : 1 Input for insertion: Enter choice : 1 Input for insertion: Enter choice : 1 Input for insertion: Enter choice : 1 Input for insertion: Enter choice : 1 Input for insertion: Enter choice : 2 Element deleted from queue is : 5 Enter choice : 2 Element deleted from queue is : 3 Enter choice : 2 Element deleted from queue is : 2 Enter choice : 1 Input for insertion: 6 Enter choice : 3 Queue elements are : 7 9 6 Enter choice : 4 Exit
코드 설명
1. insertCQ() – 요소 삽입
삽입 함수는 먼저 큐가 가득 찼는지 확인합니다. front가 0이면서 rear가 n-1인 경우, 또는 front가 rear 바로 뒤에 있는 경우에는 "Queue Overflow"(큐 오버플로우) 메시지를 출력하고 삽입을 중단합니다. 큐가 비어 있으면(front == -1) front와 rear를 0으로 초기화하고, 그렇지 않으면 rear를 한 칸 뒤로 이동시킵니다. 이때 rear가 배열 끝에 도달하면 0으로 되돌아가 순환 구조를 형성합니다.
2. deleteCQ() – 요소 삭제
삭제 함수는 큐가 비어 있는 경우(front == -1) "Queue Underflow"(큐 언더플로우) 메시지를 출력합니다. 큐에 요소가 있다면 front 위치의 값을 출력한 뒤 front를 한 칸 앞으로 이동시킵니다. front가 배열 끝에 도달하면 0으로 되돌아가며, front와 rear가 같아지면 모든 요소가 삭제된 것이므로 큐를 초기 상태(-1)로 되돌립니다.
3. displayCQ() – 큐 출력
출력 함수는 큐가 비어 있으면 "Queue is empty" 메시지를 출력합니다. front가 rear보다 작거나 같으면 해당 범위의 요소를 순서대로 출력하고, 그렇지 않은 경우(rear가 배열 끝을 지나 처음으로 감긴 경우)에는 배열 끝까지 출력한 후 다시 인덱스 0부터 rear까지 출력하여 전체 요소를 올바른 순서로 보여줍니다.
4. main() – 메뉴 기반 실행
main 함수는 사용자에게 메뉴(삽입, 삭제, 출력, 종료)를 보여주고 선택에 따라 각 연산을 수행하는 do-while 반복문으로 구성되어 있습니다. 사용자가 4를 입력하면 프로그램이 종료되며, 잘못된 값을 입력하면 "Incorrect!" 메시지를 출력합니다.
마무리
원형 큐는 고정된 크기의 버퍼를 효율적으로 활용해야 하는 상황에서 특히 유용합니다. 대표적인 활용 사례로 CPU 스케줄링의 라운드 로빈(Round Robin) 방식, 키보드 입력 버퍼, 스트리밍 데이터 처리 등이 있습니다. 위 예제를 직접 컴파일하고 실행해 보면서 front와 rear 포인터가 배열 내에서 어떻게 순환하는지 확인해 보시기 바랍니다.