[큐] 원형 큐 (Circular Queue)

원형 큐 (Circular Queue)

기본적인 Queue 구조는 push와 pop을 반복하다보면 Index (Rear)는 오른쪽으로 이동하게 된다.

▶ [큐] Queue란?

[큐] Queue란?

그러다보면 Queue 배열 크기에 제한될 수 밖에 없다.

이를 위해 Queue Index가 순환하는 구조인 원형 큐가 존재한다.

→ 앞에 비어있는 공간을 재활용하는 구조로

    들어오는 Input Data가 적절하게 Enqueue / Dequeue 된다면 Queue Size를 최적화 할 수 있다.

Queue가 Full 되었을 때, 공간을 동적으로 할당하거나

비어있는 원소를 재배치 하는 것은 Overhead가 크기에 성능이 저하된다.

→ 원형 큐는 Front와 Rear 인덱스로 주어진 공간을 효율적으로 활용하는 구조

 

고려 사항

기본적으로 front와 rear가 순환되도록 enqueue / dequeue 동작이 이루어져야 한다.

비어있는 상태 / 가득 찬 상태를 구분해야 한다.

 

▶ 삽입 (Enqueue)

arr[re++ % QUEUE_SIZE] = data;

- 원형 큐 순환을 위해서 % {Queue Size} 처리가 필요하다.

   ex) Queue Size가 5일 때, "rear + 1 % 5" 로 처리된다.

 

▶ 가득 찬 상태 (isFull)

if(((re + 1) % Queue_SIZE) == fr)

- 데이터를 추가 하기전에 먼저 Full 상태를 확인해야 한다.

- "현재 rear가 있는 곳에서 다음 위치(rear + 1)인 Data가 존재하는지 확인"

    → 해당 위치 front와 동일하다면 f

 

▶ 삭제 (Dequeue)

arr[fr++ % QUEUE_SIZE];

- 원형 큐 순환을 위해서 % {Queue Size} 처리가 필요하다.

 

▶ 비어져 있는 상태 확인 (isEmpty)

if(re == fr)

- rear와 front가 같은 위치에 존재하면 비어져 있는 상태이다.

- 삭제(Dequeue) 할 때 비어져 있는지 먼저 확인해줘야 한다.

 

▶ 원소 개수 확인 (count)

if (fr > re) return QUEUE_SIZE - (fr - re);
return re - fr;

- 일반적인 Queue라면 "re - fr" 로 구할 수 있지만

  원형큐에서는 re와 fr 수치가 어떤 것이 앞서는지 데이터 상태에 따라 다르다.

  → 원소가 존재하면서, rear가 fornt보다 작아질 수 있는 것이다.

- Enqueue / Dequeue 될 때, 별도의 변수로 관리하거나

  수식으로는 (QUEUE_SIZE + rear - front) % QUEUE_SIZE 으로도 도출할 수 있다.

  혹은 조건문을 통해서 rear 와 front 크기를 비교를 통해서 분기할 수 있다.

 

인덱스가 순환되기 때문에 front와 rear 중 어떤 것이 앞서는지 알 수 없다.

그렇기에 Queue 전체 공간 중 버퍼 1개는 항상 비워둔다.

ex) Data가 최대 4개 정도 들어오는 상황이라면

      Queue Size를 4 + 1 개로 두어서 1개 정도 여유공간을 둔다.

 

또한, 비어있는 상태가 "rear == front 인데, 버퍼 한개를 추가로 두지 않았다면

이게 원소가 가득차서 rear와 front가 같은 위치인건지 명확히 구분할 수 없다.

 

Code

#include <stdio.h>
const int QUEUE_SIZE = 5;
int data[] = { 3, 2, 5, 4, 1, 8, 6, 9, 7};
struct CircularQueue {
       int fr, re;
    int arr[QUEUE_SIZE];
   
       void enQueue(int data) {
              if (((re + 1) % QUEUE_SIZE) == fr) {
                     printf("Queue is Full\n"); return;
              }
              arr[re++ % QUEUE_SIZE] = data;
       }
       int deQueue() {
              if (fr == re) {
                     printf("Queue is Empty\n"); return -1;
              }
              return arr[fr++ % QUEUE_SIZE];
       }
       int count()
       {
              if (fr > re) return QUEUE_SIZE - (fr - re);
              return re - fr;
       }
}CQ;

int main()
{
       // 비어있는 상태에서 dequeue
       printf("Dequeue: %d\n", CQ.deQueue());
       // 데이터 삽입
       for (int i = 0; i < 4; ++i)
       {
              CQ.enQueue(data[i]);
       }

       // 데이터 삭제 후 개수 확인
       printf("Dequeue: %d\n", CQ.deQueue());
       printf("Dequeue: %d\n", CQ.deQueue());
       printf("Queue Count: %d\n", CQ.count());

       // 데이터 삽입하며 Full 상태 만들기
       for (int i = 4; i < 8; ++i)
       {
              CQ.enQueue(data[i]);
       }

       // 데이터 개수 확인
       printf("Queue Count: %d\n", CQ.count());
}

 

 

Reference

- [큐] Queue란?

- [C++] [STL] Queue

- 우선순위 큐 (Priority Queue)

- 원형 큐 (Circular Queue) 동적할당 + Memory Pool 방식

 

 

관련 문제

- [Jungol] 3101 요세푸스 문제 1 

- [BOJ] 1158 요세푸스 문제

  (원형큐가 아닌 원소를 재배치하는 방식)