C++로 구현하는 순환 큐(Circular Queue) 자료구조

큐(Queue)는 여러 요소를 담는 추상 자료구조입니다. 큐는 FIFO(First In, First Out, 선입선출) 방식으로 동작하며, 즉 가장 먼저 삽입된 요소가 가장 먼저 삭제됩니다.

큐는 대표적인 선형(linear) 자료구조이지만, 단순히 배열(array)로 구현하면 몇 가지 문제가 발생할 수 있습니다. 삽입과 삭제 연산이 반복되면서 front(앞)와 rear(뒤) 포인터의 위치가 계속 뒤로 이동하게 되는데, 이때 실제로는 배열에 빈 공간이 남아 있음에도 논리적인 제약 때문에 더 이상 요소를 삽입할 수 없는 것처럼 보이는 상황이 생깁니다. 이러한 공간 낭비 문제를 해결하기 위해 순환 큐(circular queue) 자료구조를 사용합니다.

순환 큐는 큐의 마지막 위치가 첫 번째 위치와 연결되어 하나의 원(circle)을 이루는 형태의 큐입니다. 덕분에 rear 포인터가 배열의 끝에 도달하더라도 다시 처음 인덱스로 돌아가 비어 있는 공간을 계속 재활용할 수 있어, 고정된 배열로도 메모리를 효율적으로 사용할 수 있습니다.

C++ 순환 큐 구현 예제

아래 예제는 크기 5의 배열 기반 순환 큐를 구현한 것으로, 삽입(insert), 삭제(delete), 전체 출력(display) 세 가지 연산을 메뉴 형태로 제공합니다.

#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;
}

주요 동작 설명

삽입(insertCQ): 먼저 오버플로우 조건, 즉 (front == 0 && rear == n-1) 또는 (front == rear + 1)인 경우를 검사합니다. 두 조건은 모두 큐가 가득 찼음을 의미합니다. 큐가 비어 있다면(front == -1) front와 rear를 0으로 초기화하고, 그렇지 않으면 rear를 한 칸 뒤로 이동시키되 배열 끝에 도달하면 0으로 되돌립니다.

삭제(deleteCQ): 큐가 비어 있으면 언더플로우 메시지를 출력합니다. 삭제 후 front와 rear가 같아지면 큐가 비게 된 것이므로 두 값을 모두 -1로 초기화하고, 그렇지 않으면 front를 한 칸 앞으로 이동시키되 배열 끝에서는 0으로 순환시킵니다.

출력(displayCQ): front가 rear보다 작거나 같으면 한 번의 반복으로 출력하지만, rear가 배열 끝을 넘어 처음으로 감겨 들어간(wrap-around) 경우에는 배열 끝까지 출력한 뒤 인덱스 0부터 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과 20이 삭제된 후에도 순환 큐는 나머지 공간을 계속 활용할 수 있습니다. 일반적인 선형 큐였다면 이미 사용한 앞부분의 공간은 버려졌겠지만, 순환 큐는 인덱스를 원형으로 순환시켜 배열 전체를 끝없이 재사용할 수 있다는 점이 가장 큰 장점입니다.