[자료구조] 원형 큐(Circular Queue) - 배열을 이용한 구현

원형 큐(Circular Queue)

 

원형 큐란?

• 선형 큐의 문제점을 보완하기 위한 자료구조이다.
• Rear가 가르키는 마지막 인덱스가 DeQueue로 발생한 빈 공간을 활용 할 수가 없는걸 사용 할 수 있게 된다.

원형 큐의 일반적인 구조 그림

원형 큐의 주요 기능

• EnQueue
• DeQueue

원형 큐는 % Module연산을 통해서 순환 할 수 있는 구조를 만든다.

이때 중요한점이 위 그림처럼 4의 크기를 가지고는 있지만 실질적인 데이터는 3개뿐이 저장을 못하고

1개는 빈 공간인 구조를 가지게 된다. 이때 빈 공간은 Front의 인덱스가 된다.

 

원형 큐의 확인

DeQueue를 하다보면 Front와 Rear가 같아지게 되는데 이때 데이터가 비어있는걸 확인 할 수 있다.

또한 (Front + 1) % Capacity 를 해서 Front와 같으면 꽉차있는지 확인 할 수 있다.

bool MyQueue::IsEmpty()
{
    return Rear == Front ? true : false;
}

bool MyQueue::IsFull()
{
    return (Rear + 1) % Capacity == Front ? true : false;
}

 

원형 큐의 삽입

삽입은 Front의 공백자리 전까지 삽입이 가능하다.

차례대로 1,2,3을 EnQueue를 해주고 4를 EnQueue를 하게되면 꽉차있는 상태여서 삽입을 할 수 없게 된다.

int MyQueue::DeQueue()
{
    if (IsEmpty())
    {
        return -1;
    }
    Front = (Front + 1) % Capacity;
    int Value = Data[Front];
    return Value;
}

 

원형 큐의 삭제

삭제는 Front를 +1해준 자리의 인덱스 기준으로 삭제를 하게 된다.

void MyQueue::EnQueue(const int& NewData)
{
    if (!IsFull())
    {
        Rear = (Rear + 1) % Capacity;
        Data[Rear] = NewData;
    }
}

원형 큐의 메인 코드

int main()
{
    MyQueue* Queue = new MyQueue();

    Queue->CreateQueue(5);
    Queue->EnQueue(1);
    Queue->EnQueue(2);
    Queue->EnQueue(3);
    Queue->EnQueue(4);
    Queue->EnQueue(5);
    Queue->DeQueue();
    Queue->DeQueue();
    Queue->EnQueue(5);
    Queue->EnQueue(6);
    Queue->Show();
}

먼저 5개의 사이즈의 큐를 만들어 준다

EnQueue를 통해 1,2,3,4,5를 해주면 Front의 공백이 한개 있기때문에 4개까지만 사용이 가능해진다

이로서 1,2,3,4 만 큐에 담겨지고 DeQueue를 2번해서 앞에있는 데이터 2개를 1,2를 지우고

3,4인상태에서 5,6을 EnQueue를 해주며 출력을 하면

3,4,5,6이 출력됨을 확인 할 수 있다.