[7] 원형 큐(Circular Queue)

[6] 큐(Queue) 에서 본 큐에 원소를 add하는 함수와 delete하는 함수를 보면

큐의 rear과 front 만 조정하는 것이고 실제로 원소를 삭제하는 것이 아니라

큐가 점차 오른쪽으로 이동하게 된다.

따라서 원소를 넣고 삭제할수록 큐가 완전히 다 차지 않았음에도

QueueFull() 에러가 발생할 수 있다는 것이다.

 

따라서 원형 큐를 이용하면 큐를 효율적으로 이용할 수 있다.

위는 원형 큐에 원소 A를 넣은 것이다.

front는 처음 넣은 원소보다 원소보다 하나뒤에,

rear는 가장 나중에 넣은 원소를 가리키도록 한다.

 

원형 큐에 원소 B를 넣으면

다음과 같이 rear는 원소 B를 가리키고, 

front는 원소 A 보다 하나 앞을 가리키게 될 것이다.

 

원소를 더 넣어 큐를 완전히 채워 보면 

위와 같다.

 

이 상태에서 원소를 하나 더 넣게 되면

front와 rear가 같아지는데, 이 때를 queue full로 판단하면 된다.

 

큐에서 원소를 삭제하기 위해서는 front 를 하나 증가시키면 된다.

큐가 비어있는지 파악하는 것도 마찬가지로

front와 rear가 같아지는지 확인하면 된다.

다음과 같은 상황에서 원소를 한번 더 삭제하면

front는 rear와 같아짐을 알 수 있다.

 

C언어 구현

#define MAX_QUEUE_SIZE 100
typedef struct {
    int key;
    // 다른 필드들
}element;
element queue[MAX_QUEUE_SIZE];
int front = 0;
int rear = 0;
 

원형 큐 선언

 

void add(element item) {
    rear = (rear + 1) % MAX_QUEUE_SIZE;
    if (rear == front)
        queueFull();
    queue[rear] = item;
}

원형 큐에 원소 삽입

 

element delete() {
    if (front == rear)
        return queueEmpty();
    front = (front + 1) % MAX_QUEUE_SIZE;
    return queue[front];
}

원형 큐에서 원소 삭제

 

원형 큐에서의 문제중 하나가 

큐가 모두 찼을 때와 큐가 비어있을 때를 구분하지 못한다는 것이다.

( 큐가 모두 찼을 때와 비어있을 때 모두 rear == front로 판단하기 때문)

 

따라서 큐에 원소가 MAX_QUEUE_SIZE -1 만큼 찰 수 있도록 한다.

따라서 원소를 삽입하는 경우에는 rear을 증가시키고 front와 동일한지 확인하고,

원소를 삭제하는 경우에는 front와 rear이 동일한지 확인한 후 front를 증가시킨다.