[자료구조] 원형 큐 Circular Queue

What is Circular Queue? 

원형 큐는 잘못된 포화 상태 인식을 방지하는 보다 효과적인 큐로서 1차원 배열의 처음과 끝이 서로 연결되었다고 본다.

• 인덱스도 이에 따라 변경, %(나머지) 연산 사용

잘못된 포화 상태 인식이란, 큐에서 삽입과 삭제를 반복하면서 앞부분에 빈자리가 있어도 rear = n-1 상태이면 포화상태로 인식하고 더 이상의 삽입을 수행하지 않는 것이다. 

 

원형 큐는 전단과 후단을 관리하기 위한 2개의 변수가 필요하다.

• 두 변수의 값 증가시 % M 사용, M은 큐의 크기
• front: 첫번째 요소 하나 앞의 인덱스 : front = (front+1) % M
• rear: 마지막 요소의 인덱스 : rear = (rear+1) % M

 

 

공백상태와 포화상태

• 공백상태 : front == rear  (초기 상태 : front = rear = 0)
• 포화상태 : front % M == (rear + 1) % M (M은 Q의 크기, 즉 원소개수)
• 공백상태와 포화상태를 구별하기 위하여 하나의 공간은 항상 비워둔다. 

 

원형 큐의 규현

#include <iostream>
using namespace std;

const int MAX_NUM = 100;
//define MAX_NUM 100
typedef int element;

class CQueue{
public:
    element data[MAX_NUM];
    int front, rear; //두개의 인덱스 사용
    
    CQueue(){
        front = rear = 0; //초기화
    }
    
    bool is_empty(){
        return(front == rear);
    }
    
    bool is_full(){
        return (front == (rear+1) % MAX_NUM);
    }
    
    void enQueue(element value){
        if(is_full()){
            cout << "Queue OVERFLOW!!!" << endl;
            exit(-1);
        }
        else{
            rear = (rear+1) % MAX_NUM;
            data[rear] = value;
        }
    }
    element deQueue(){
        if (is_empty()){
            cout<<"Queue UNDERFLOW!!!"<<endl;
            exit(-1);
        }
        else{
            front = (front+1) % MAX_NUM;
            return(data[front]);
        }
    }
    element peek(){
        if(is_empty()){
            cout<< "Queue UNDERFLOW!!!" <<endl;
            exit(-1);
        }
        else{
            return(data[(front+1) % MAX_NUM]);
        }
    }
    void printQueue(){
        cout << "Queue 상태\n";
        if(front <= rear){
            for(int i = front+1 ; i <= rear; i++)
                cout<<data[i]<<endl;
        }
        else{
            for (int i = front+1; i <= rear + MAX_NUM; i++)
                cout<<data[i % MAX_NUM ] << endl;
        }
        cout<<"FRONT : "<<front<<" "<<"REAR : "<<rear<<endl;
    }
};

int main(){ 
    CQueue MyQueue;
    
    MyQueue.enQueue(10); MyQueue.printQueue();
    MyQueue.enQueue(20); MyQueue.printQueue();
    MyQueue.enQueue(30); MyQueue.printQueue();
    MyQueue.deQueue(); MyQueue.printQueue();
    MyQueue.enQueue(40); MyQueue.printQueue();
    MyQueue.enQueue(50); MyQueue.printQueue();
    MyQueue.deQueue(); MyQueue.printQueue();
}