[개념] 순환 큐(Circular Queue)

이 글은 순환 큐(Circular Queue)에 대해 다루겠습니다. 전체적인 내용은 Programiz를 정리했습니다. 공부한 것을 정리하는 형식으로 작성되었으므로 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

 

'순환 큐'하면 제일 먼저 떠오르는 중요한 개념은 일반 큐 또는 배열보다 공간을 효율적으로 사용한다는 점입니다.

아래 [그림1]에 총 11번의 enqueue와 7번의 dequeue가 일어난 큐를 표현 해 놓았습니다. 앞으로 새로운 값을 이 큐에 넣을 때는 뒤로 넣게 되기 때문에 앞에 dequeue된 공간은 사용하지 못합니다.(물론 큐를 empty시켜서 처음부터 넣게다고 한다면 모를까..) 이렇게 메모리에는 공간의 낭비가 발생하게 됩니다.

 

[그림1] enqueue와 dequeue가 몇 차례 일어난 queue

순환 큐의 작동 방식

[그림2]

순환 큐는 index 값을 증가하되 값을 넣을 때는 modulo 연산자를 사용합니다. 그래서 index가 0인 값과 8인 값은 같은 공간에 들어가게 되지만 queue[0] 이 dequeue되지 않은 상태로 queue[8]의 값을 넣으려고 한다면 덮어 씌워지겠죠.

큐와 마찬가지로 front와 rear 포인터를 갖고 있습니다.(포인터가 int *front, *rear로 관리되기 때문에 포인터가 아니라 그 index를 가리키고 있기 때문에 포인터라고 표현하는 것입니다.) front는 값이 있는 제일 앞을 가리키고 rear는 값이 있는 가장 끝을 가리킵니다. 그래서 Enqueue 시에는 rear 값이 늘어나고 dequeue 시에는 front 값이 늘어나겠죠? 물론 일반 큐에서 front, rear은 계속 증가하지만 순환 큐에서 front와 rear은 0~순환큐의 크기 사이의 값입니다.

 

여기까지는 일반 큐와 같지만 순환 큐의 경우에는 enqueue시에는 남는 공간이 있는지(= 꽉 차지는 않았는지), dequeue시에는 비어 있지 않은지를 확인하는 작업을 추가로 진행해야 합니다. 꽉 차 있을 때 enqueue를 하면 원래 있는 값에 overwrite가 되기 때문이고 비어 있는 큐를 dequeue하려고 하면 에러기 때문입니다.

 

순환 큐에 대한 코드는 아래와 같이 짤 수 있습니다. 코드 복사를 원하시면 더보기를 누르시면 됩니다.

#include <iostream>
#define SIZE 8 /* Size of Circular Queue */

using namespace std;

class Queue{
private:
    int elements[SIZE], front, rear;
public:
    Queue(){
        front = -1;
        rear = -1;
    }
    bool isFull(void); // check if queue is full
    bool isEmpty(void); // check if queue is empty
    void enqueue(int element); // enqueue element
    int dequeue(void); // dequeue element
    void printQueue(void); // display queue
};

bool Queue::isFull(){
    if(front == rear + 1){ return true; }
    if(front == 0 && rear == SIZE - 1){
        return true;
    }
    return false;
}

bool Queue::isEmpty(){
    if(front == -1){
        return true;
    } else{
        return false;
    }
}

void Queue::enqueue(int ele){
    if(!isFull()){
        if(front == -1){
            front = 0;
        }
        
        rear = (rear + 1) % SIZE;
        elements[rear] = ele;
        cout << ele << " inserted" << endl;
    } else{
        cout << "Circular Queue is full" << endl;
    }
}

int Queue::dequeue(){
    int ele;
    if(!isEmpty()){
        ele = elements[front];
        if(front == rear){
            // when queue is empty after dequeing
            front = -1;
            rear = -1;
        } else{
            front = (front + 1) % SIZE;
        }
        return ele;
    } else{
        cout << "Circular Queue is empty" << endl;
        return -1;
    }
    
}

void Queue::printQueue(){
    if(!isEmpty()){
        for(int i = front; i != rear; i = (i + 1) % SIZE){
            cout << elements[i] << " ";
        }
        cout << elements[rear];
    } else{
        cout << "Circular Queue is empty" << endl;
    }
}

int main(void){
    Queue que;
    
    que.dequeue(); // fails because queue is empty
    
    for(int i = 0; i < SIZE; i++){
        que.enqueue(i * 3 + 1);
    }
    que.enqueue(100); // fails because queue is full
    que.printQueue();
    
    int deqEle = que.dequeue();
    if(deqEle > -1){
        cout << endl;
        cout << "Dequeued Element : " << deqEle << endl;
    }
    que.enqueue(0);
    que.printQueue();
    cout << endl;
    return 0;
}