순환 큐(Circular Queue)

선입선출!

큐(Queue)란 자료구조는 앞서 배웠던 스택(Stack) 자료구조와는 달리 선입선출(First In, First Out: FIFO)의 구조를 지니고 있습니다. 한마디로 먼저 들어온 데이터는 먼저 나간다는 소리입니다. 예를 들면, 점심시간에 학생들이 점심을 먹으러 일렬로 줄을 서있다고 가정합시다. 줄을 선 순서대로 차례차례 급식을 받고 빠져나가죠? 이러한 구조를 지닌 자료구조가 바로 큐(Queue)라고 말할 수 있습니다. 오늘은 순환 큐(Circular Queue)와 링크드 큐(Linked Queue)에 대해 알아보기 전에, 기본적으로 짚고 넘어가야 할 사항들이 있습니다.

우리가 리스트(List)에서는 가장 앞에 있는 노드를 헤드(Head), 가장 뒤에 있는 노드를 테일(Tail)이라고 했었죠? 이번에 배우게 될 큐(Queue)에서는 가장 앞에 있는 요소를 전단(Front), 가장 뒤에 있는 요소를 후단(Rear)이라고 합니다. 저 위의 그림에선 the가 전단, mat이 후단이라고 말할 수 있습니다. 그리고 큐는 선입선출의 구조이기 때문에, 먼저 들어온 게 먼저 나가는 형태를 띤다고 했었죠? 즉, 제거(Dequeue)는 전단에서 이루어지며, 삽입(Enqueue)은 후단에서 이루어집니다. 이해되시죠? 

순환 큐(Circular Queue)

큐가 직선이 아닌 원형으로!

순환 큐(Circular Queue)에 대해 설명하기 전에, 직선 구조를 띈 큐(Queue)의 문제점을 보도록 하겠습니다. 

나가면서 뒤에 있던 B, C, D, E, F 요소 모두 앞으로 옮겨가는 상황이 벌어졌습니다. 전단에 있는 요소가 제거될 때마다 뒤에 있는 요소가 앞으로 따라와야 한다는 소리입니다. 그러면 1000개의 요소가 있다고 가정했을 때, 전단에 있는 요소가 제거되면 999번의 연산을 추가적으로 거치게 됩니다. 즉, 큐의 크기가 커질수록 성능의 저하는 심각한 상황입니다. 이런 문제를 해결하기 위한 방안으로, 순환 큐가 등장했습니다. 

순환 큐에서는 시작과 끝이 이어져 있습니다. 마치 더블 링크드 리스트처럼 말입니다. 어떻게 되어있는지 한번 볼까요?

단과 후단이 같아진다면 전단이 후단이 같아지면 큐가 비어있는지, 꽉 차 있는지 알 수가 없습니다. 실제로, 후단은 실제 후단의 다음에 위치하며, 전단과 후단을 구분하기 위해 더미(Dummy) 공간을 만들어 만들어질 배열의 크기는 실제 배열의 크기에 1을 더한 값을 갖습니다. 이러면, 전단과 후단이 같다면 비어있는(Empty) 상태, 후단의 다음 노드가 전단이라면 꽉 찬(Full) 상태라고 말할 수 있습니다. 이제 직접 구현을 해보도록 합시다. 먼저 순환 큐의 노드를 구조체로 표현해보도록 합시다.

typedef struct Node
{
    int data; // 데이터 필드
} Node;

위의 Node 구조체를 보시면 멤버가 data 하나뿐입니다. Node 구조체에 대해서는 따로 설명드리지 않아도 단번에 이해하실 것 같네요. 이번엔 CircularClass를 살펴보도록 하겠습니다.

class CircularQueue
{
private:
    Node* node; // 노드 배열
    int capacity; // 큐의 용량
    int front; // 전단의 인덱스
    int rear; // 후단의 인덱스
public:
    CircularQueue(int capacity)
    {
        this->capacity = capacity + 1; // 노드 배열의 크기는 실제 용량에서 1을 더한 크기 (더미 공간 때문)
        node = new Node[this->capacity]; // Node 구조체 capacity + 1개를 메모리 공간에 할당한다
        front = 0; rear = 0; // 전단과 후단의 초기화
    }
..

위의 CircularQueue 생성자를 보시면, 위에서 말했듯이 노드 배열의 크기는 실제 용량에서 1을 더한 크기여야 합니다. 이는 더미(Dummy) 공간 때문이며, 더미 공간이 존재하는 이유는 큐가 꽉 찼는지, 비어있는지를 구분하기 위한 것입니다. 이번에는 enqueue 함수를 살펴보도록 합시다.

..
    void enqueue(int data)
    {
        int pos; // 데이터가 들어갈 인덱스
        // 후단의 인덱스와 더미 공간을 제외한 큐의 용량이 같다면 
        if (rear == capacity - 1) {
            // pos에 rear를 대입하고, rear를 0으로 초기화 시킨다
            pos = rear; rear = 0;
        } else // 후단의 인덱스와 더미 공간을 제외한 큐의 용량이 같지 않다면
            pos = rear++; // pos에 rear 값을 들여놓고, rear의 값을 1 증가시킨다
        node[pos].data = data; // pos 번째의 노드의 데이터에 data를 대입한다
    }
..

위의 삽입 함수를 보시면, 더미 공간을 제외한 큐의 용량과 후단의 인덱스를 비교하는데 만약 서로 같다면 pos에 후단의 인덱스를 대입합니다. 그리고 후단의 인덱스를 0으로 초기화시킵니다. 여기서 0으로 초기화시키는 이유는, 큐가 순환하는 큐이기에 계속 이어지기 때문입니다. 그리고 더미(Dummy) 공간에는 데이터가 들어갈 수 없습니다. 반대로, 서로 같지 않다면 그냥 후단의 인덱스를 pos에 대입하고, 후단의 인덱스를 1만큼 증가시킵니다. 

..
    int dequeue() {
        int pos = front; // pos에 전단의 인덱스 대입
        // 전단의 인덱스와 더미 공간을 제외한 큐의 용량이 같다면
        if (front == capacity - 1) front = 0; // front를 0으로 초기화 시킨다
        // 전단의 인덱스와 더미 공간을 제외한 큐의 용량이 같지 않다면
        else front++; // 전단의 인덱스를 1 증가시킨다
        return node[pos].data; // 제외되는 데이터를 반환한다
    }
..

위의 제거 함수를 살펴보면, 전단의 인덱스와 더미 공간을 제외한 큐의 용량이 같은지 비교합니다. 만약에 같을 경우, 전단의 인덱스를 0으로 초기화 시킵니다. 삽입 함수와 마찬가지로 전단의 인덱스가 더미 공간을 제외한 큐의 용량을 넘어서려고 하면 0으로 초기화시키고 계속 이어가도록 만들어 주어야 합니다. 반대로, 같지 않다면 그냥 전단의 인덱스를 간단하게 1만 증가시키면 됩니다. 그럼, 전의 전단이었던 노드가 제외되는 셈입니다. 이번엔 getSize 함수를 살펴보도록 합시다.

..
    int getSize() {
        if (front <= rear) // 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작다면
            return rear - front; // 후단의 인덱스에서 전단의 인덱스를 뺀값을 반환한다
        else // 전단의 인덱스가 후단의 인덱스보다 크다면
            return capacity - front + rear; // 용량에서 전단의 인덱스를 뺀 뒤에 후단의 인덱스를 더한 값을 반환한다
    }
..

큐의 크기를 가져오는 함수를 살펴보면, 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작은지 비교합니다. 만약 같거나 작을 경우에는, 후단의 인덱스에서 전단의 인덱스를 빼주면 됩니다. 반대로, 전단의 인덱스가 후단의 인덱스보다 크다면 더미 공간을 포함한 큐의 용량에서 전단의 인덱스를 빼고 후단의 인덱스를 더합니다. 

만약 위 그림처럼, 전단의 인덱스가 2, 후단의 인덱스가 7이라고 가정합니다. 후단의 인덱스는 실제 후단의 인덱스에 1을 더한 값이므로 요소가 존재하는 위치는 2, 3, 4, 5, 6입니다. 여기서 후단의 인덱스에서 전단의 인덱스를 빼주면 5가 나오는 겁니다. (설명이 조금 애매할지도 몰라서, 이 부분에 대해 궁금한 사항이 있으시면 댓글로 달아주세요.) 요번엔, 비어있는지 꽉 차 있는지 구분을 하기 위한 함수를 구현해보도록 합시다.

..
    bool isEmpty() {
        return front == rear; // 전단의 인덱스와 후단의 인덱스가 같을 경우 true, 아니면 false
    }
    
    bool isFull() {
        // 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작을 경우
        if (front <= rear)
            return (rear - front) == (capacity - 1); // 후단의 인덱스에서 전단의 인덱스를 뺀 뒤의 결과가 더미 공간을 제외한 큐의 용량과 같을 경우
        else // 전단의 인덱스가 후단의 인덱스보다 클 경우
            return (rear + 1) == front; // 후단의 다음 노드가 전단 노드면 true, 아니면 false
    }
..

비어있는 경우를 확인하는 함수는 isEmpty이고, 이 함수는 전단의 인덱스와 후단의 인덱스가 같으면 큐가 비어있는 것이므로 true를, 아닐 경우에는 false를 반환하도록 했습니다. 다음 꽉 차 있는 경우를 확인하는 함수인 isFull은 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작을 경우 후단의 인덱스에서 전단의 인덱스를 뺀 값과 더미 공간을 제외한 큐의 용량이 서로 같은지 비교합니다. (더미 공간엔 데이터가 들어가지 않으므로. 참고로 더미 공간은 고정되어 있는 게 아니며 계속 움직입니다.) 반대로 전단의 인덱스가 후단의 인덱스보다 크다면 간단히 후단의 다음 노드가 전단 노드인지 확인을 하시면 됩니다. 아래 예를 한번 살펴보도록 합시다.

예제보기

#include <iostream>
using namespace std;
typedef struct Node
{
    int data; // 데이터 필드
} Node;

class CircularQueue
{
private:
    Node* node; // 노드 배열
    int capacity; // 큐의 용량
    int front; // 전단의 인덱스
    int rear; // 후단의 인덱스
public:
    CircularQueue(int capacity)
    {
        this->capacity = capacity + 1; // 노드 배열의 크기는 실제 용량에서 1을 더한 크기 (더미 공간 때문)
        node = new Node[this->capacity]; // Node 구조체 capacity + 1개를 메모리 공간에 할당한다
        front = 0; rear = 0; // 전단과 후단의 초기화
    }
    ~CircularQueue()
    {
        delete []node; // 노드 배열 소멸
    }
    void enqueue(int data)
    {
        int pos; // 데이터가 들어갈 인덱스
        // 후단의 인덱스와 더미 공간을 제외한 큐의 용량이 같다면 
        if (rear == capacity - 1) {
            // pos에 rear를 대입하고, rear를 0으로 초기화 시킨다
            pos = rear; rear = 0;
        } else // 후단의 인덱스와 더미 공간을 제외한 큐의 용량이 같지 않다면
            pos = rear++; // pos에 rear 값을 들여놓고, rear의 값을 1 증가시킨다
        node[pos].data = data; // pos 번째의 노드의 데이터에 data를 대입한다
    }
    int dequeue() {
        int pos = front; // pos에 전단의 인덱스 대입
        // 전단의 인덱스와 더미 공간을 제외한 큐의 용량이 같다면
        if (front == capacity - 1) front = 0; // front를 0으로 초기화 시킨다
        // 전단의 인덱스와 더미 공간을 제외한 큐의 용량이 같지 않다면
        else front++; // 전단의 인덱스를 1 증가시킨다
        return node[pos].data; // 제외되는 데이터를 반환한다
    }
    int getSize() {
        if (front <= rear) // 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작다면
            return rear - front; // 후단의 인덱스에서 전단의 인덱스를 뺀값을 반환한다
        else // 전단의 인덱스가 후단의 인덱스보다 크다면
            return capacity - front + rear; // 용량에서 전단의 인덱스를 뺀 뒤에 후단의 인덱스를 더한 값을 반환한다
    }
    bool isEmpty() {
        return front == rear; // 전단의 인덱스와 후단의 인덱스가 같을 경우 true, 아니면 false
    }
    bool isFull() {
        // 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작을 경우
        if (front <= rear)
            return (rear - front) == (capacity - 1); // 후단의 인덱스에서 전단의 인덱스를 뺀 뒤의 결과가 더미 공간을 제외한 큐의 용량과 같을 경우
        else // 전단의 인덱스가 후단의 인덱스보다 클 경우
            return (rear + 1) == front; // 후단의 다음 노드가 전단 노드면 true, 아니면 false
    }
    int getRear() { return rear; }
    int getFront() { return front; }
};
int main()
{
    CircularQueue cq(10);
    int size;
    // 데이터의 삽입과 제거
    cq.enqueue(10); cq.enqueue(20); cq.enqueue(30);
    cq.dequeue(); cq.dequeue(); cq.dequeue();   
    cq.enqueue(10); cq.enqueue(20); cq.enqueue(30);
    cq.enqueue(20); cq.enqueue(20); cq.enqueue(20);
    cq.enqueue(20); cq.enqueue(20); cq.enqueue(520);
    // 큐의 현재 크기를 얻어옴
    size = cq.getSize();
    for (int i = 0; i < size; i++)
        cout << "빠져나간 데이터: " << cq.dequeue() << ", Front: " << cq.getFront() << ", Rear: " << cq.getRear() << endl;
    return 0;
}

결과보기

빠져나간 데이터: 10, Front: 3, Rear: 1
빠져나간 데이터: 20, Front: 4, Rear: 1
빠져나간 데이터: 30, Front: 5, Rear: 1
빠져나간 데이터: 20, Front: 6, Rear: 1
빠져나간 데이터: 20, Front: 7, Rear: 1
빠져나간 데이터: 20, Front: 8, Rear: 1
빠져나간 데이터: 20, Front: 9, Rear: 1
빠져나간 데이터: 20, Front: 10, Rear: 1
빠져나간 데이터: 520, Front: 0, Rear: 1

계속하려면 아무 키나 누르십시오...

위의 예의 메인 함수부터 보시면, “데이터 삽입 3번 -> 데이터 제거 3번 -> 데이터 삽입 9번” 이런 식으로 되어있는데, 처음 데이터 삽입 3번으로 후단의 인덱스가 3이나 증가합니다. 그다음 데이터 제거 3번으로 인해 전단의 인덱스도 3이나 증가합니다. 그다음 데이터 삽입 9번으로 인해 후단의 인덱스 값이 9나 증가합니다. 그러나 큐의 용량을 초과하므로 큐의 용량에서 후단의 인덱스를 뺍니다. 그럼 후단의 인덱스가 1인데, 그 뒤에 for문으로 큐에 남아있는 데이터를 모두 제거하니 최종적으로 전단과 후단의 인덱스는 1이 되었습니다. 순환 큐는 편리하기 한 것 같으나 좀 복잡한 것 같죠? 이번에는 링크드 큐를 한번 살펴보도록 합시다.