원형 큐(Circular Queue) in C++

출처: https://www.programiz.com/dsa/circular-queue

 

 

아래 그림을 보면 0, 1에 공간이 남았지만 REAR가 컨테이너의 끝에 닿았기 때문에 더 이상 공간이 없다고 판단한다. 

아니면 원소들을 다시 items[0]부터 시작하도록 옮기는데 비용이 든다. 

형 큐는 원래 알던 일반 Queue를 아래 그림처럼 생각하면 된다.

일반 큐에서 삽입, 삭제를 반복하면서 사용할 수 없는 메모리가 생기는 단점을 보완한 자료 구조다. 

 

 

---

원형 큐 동작

• 원형 큐는 FRONT와 REAR라는 두 가지 포인트를 가진다. 
• FRONT는 큐의 첫번째 원소를 가리킨다. 
• REAR는 큐의 마지막 원소를 가리킨다. 
• FRONT와 REAR는 초기값을 -1로 설정해준다. 

 

1. 원소 삽입

• 큐가 사이즈를 초과하는지 확인한다.
• 첫번째 원소를 넣을 때는 FRONT를 0으로 설정한다. 
• 원소를 삽입할 때마다 REAR가 1씩 증가한다.
• 증가한 REAR의 위치에 데이터를 넣는다. 

 

2. 원소 삭제 

• 큐가 비었는지 확인한다.
• FRONT를 이용해 가장 앞에 있는 원소를 반환한다. 
• 원소를 삭제할 때마다 FRONT가 1씩 증가한다. 
• 모든 원소가 삭제되면 FRONT와 REAR를 -1로 설정한다. 

 

큐가 꽉 찼는지 확인하는 방법은 두가지 방법이 있다. 

• FRONT == 0 && REAR == SIZE - 1
• FRONT = REAR + 1

두번째 케이스는 아까 일반 큐에서 0, 1 자리를 사용하기 때문에 생기는 조건이다. 

 

 

여기서 제일 중요한 건 REAR + 1 % SIZE == FRONT 를 잘 이해하는 것이다. 

근데 이걸 어떻게 설명할지 모르겠다... 

 

 

#include <iostream>
#define MAX_SIZE 500000

class Queue {
    
public:
    Queue(int n): size(n), front(-1), rear(-1){};
    
    bool isFull()
    {
        if ((front == 0 && rear == size - 1) || (front == rear + 1))
            return true;
        else
            return false;
    }
    
    bool isEmpty()
    {
        if (front == -1)
            return true;
        else
            return false;
    }
    
    void enQueue(int data)
    {
        if (!isFull())
        {
            if (front == -1) front = 0;
            rear = (rear + 1) % size;
            items[rear] = data;
        }
    }
    
    int deQueue()
    {
        if (isEmpty())
            return (-1);
        
        int data = items[front];
        if (front == rear)
        {
            front = -1;
            rear = -1;
        }
        else
        {
            front = (front + 1) % size;
        }
        return data;
    }
    
    void display()
    {
        std::cout << "\ndisplay---------------\n";

        for(int i = 0; i<size; ++i)
        {
            std::cout << items[i] << "\t";
        }
        std::cout << "\n----------------------\n";
    }
    
private:
    int items[MAX_SIZE];
    int front, rear;
    int size;
    
};

int main()
{
    Queue q(4);
    q.deQueue();
    for(int i = 1; i<=4; ++i)
    {
        q.enQueue(i);
    }
    q.display();
    
    q.deQueue();
    q.display();
    
    q.enQueue(6);
    q.display();
    
    
    return 0;
}

display---------------
1	2	3	4	
----------------------

display---------------
1	2	3	4	
----------------------

display---------------
6	2	3	4	
----------------------