[Data Structure] 원형 큐(circular queue)

---

원형 큐

 

 

선형 큐는 구현하였을 때 전열과 후열이 큐를 사용하면서 지속적으로 증가하기 때문에 전열과 후열이 배열의 끝에 도달한다면 배열의 앞 부분이 비어있더라도 사용하지 못하는 단점이 있다. 이를 보완하기 위해 모든 요소를 왼쪽으로 이동시킬 필요가 있는데, 실제 데이터를 이동시키기 위해서는 추가 연산도 필요하고, 구현도 복잡해지기 때문에 다른 방법이 필요하다.

이러한 단점을 극복한 것이 원형 큐이다. 원형 큐는 배열을 선형이 아니라 원형으로, 즉 전열과 후열을 연결하여 배열의 끝에 도달하더라도 지속적으로 큐를 사용할 수 있게 하는 것이다. 실제로 배열을 원형으로 만드는 것은 아니고 후열이 배열의 끝에 도달하면 다시 전열을 사용하도록 하여 개념적으로 원형을 만들어 사용한다.

큐를 어떻게 구현할 것인가가 다를 뿐이기 때문에 선형 큐와 ADT(추상 자료형)은 같다.

 

---

구현 | C

 

배열을 원형으로 만들기 위해 rear 가 배열 사이즈의 끝에 도달하면 0 으로 바꾼다. 즉 MAX_QUEUE_SIZE - 1 = 0 이 되도록 하여 배열의 앞과 뒤를 연결하고, 개념상 원으로 만든다. 이때 선형 큐와 마찬가지로 front 와 rear 를 설정하면 큐가 비어있을 때와 가득 차 있을 때가 구분되지 않을 수 있다. is_empty 는 front 와 rear 가 같은지로 확인하고, is_full 은 rear 가 MAX_QUEUE_SIZE - 1 과 같은지 확인하기 때문인데 원형 큐에서는 MAX_QUEUE_SIZE - 1 이 0 이 되기 때문에 큐가 가득 찬다면 front 도 0 이 되고, rear 도 0 이 되기 때문에 구분되지 않는다. 따라서 front 와 rear 의 초기값을 0 으로 설정하여 가장 앞 칸을 공백으로 만들어줘서 이 문제를 해결한다.

참고로 count 변수를 따로 만들어주고 이를 활용하면 큐가 가득 찬 상태와 비어있는 상태를 구분할 수 있기 때문에 큐가 한 칸 비어서 활용되지 못하는 문제를 해결할 수 있다.

배열 사이즈의 끝에 도달하면 0 으로 바꿔주는 문제는 나머지 연산을 통해 해결한다. 이를 구현하면 아래와 같다. 아래 코드는 main 함수를 제외한 원형 큐 선언과 원형 큐를 관리하는 코드이다. element 는 선형 큐와 마찬가지로 임의로 int 로 설정하였고, dequeue 나 front, rear 에서 에러도 임의로 -1 을 반환하도록 하였다.

#include <stdio.h>
#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct {
    element data[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;

void init_queue(Queue* q) {
    q->front = q->rear = 0;
}

int is_empty(Queue* q) {
    return (q->front == q->rear);
}

int is_full(Queue* q) {
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

void enqueue(Queue* q, element item) {
    if (is_full(q)) {
        printf("Queue is full\n");
        return;
    } else {
        q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
        q->data[q->rear] = item;
    }
}

element dequeue(Queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        q->front = (q->front + 1) % MAX_QUEUE_SIZE;
        return q->data[q->front];
    }
}

element front(Queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
    }
}

element rear(Queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        return q->data[q->rear];
    }
}

int size(Queue* q) {
    return (q->rear - q->front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

void display(Queue* q) {
    for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
        if (i > q->front && i <= q->rear) {
            printf("%d\t|", q->data[i]);
        } else if (q->front > q->rear) {
            if (i > q->front || i <= q->rear) {
                printf("%d\t|", q->data[i]);
            } else {
                printf("\t|");
            }
        } else {
            printf("\t|");
        }
    }
    printf("\n");
}

main 함수를 아래와 같이 구현하고 실행해보자.

int main()
{
    Queue q;
    init_queue(&q);
    enqueue(&q, 1); display(&q);
    enqueue(&q, 2); display(&q);
    enqueue(&q, 3); display(&q);
    enqueue(&q, 4); display(&q);
    enqueue(&q, 5); display(&q);
    enqueue(&q, 6); display(&q);
    enqueue(&q, 7); display(&q);
    enqueue(&q, 8); display(&q);
    enqueue(&q, 9); display(&q);
    enqueue(&q, 10); display(&q);
    dequeue(&q); display(&q);
    enqueue(&q, 11); display(&q);
    dequeue(&q); display(&q);
    enqueue(&q, 12); display(&q);
    enqueue(&q, 13); display(&q);
    return 0;
}

결과는 아래와 같다.

	|1	|	|	|	|	|	|	|	|	|
	|1	|2	|	|	|	|	|	|	|	|
	|1	|2	|3	|	|	|	|	|	|	|
	|1	|2	|3	|4	|	|	|	|	|	|
	|1	|2	|3	|4	|5	|	|	|	|	|
	|1	|2	|3	|4	|5	|6	|	|	|	|
	|1	|2	|3	|4	|5	|6	|7	|	|	|
	|1	|2	|3	|4	|5	|6	|7	|8	|	|
	|1	|2	|3	|4	|5	|6	|7	|8	|9	|
Queue is full
	|1	|2	|3	|4	|5	|6	|7	|8	|9	|
	|	|2	|3	|4	|5	|6	|7	|8	|9	|
11	|	|2	|3	|4	|5	|6	|7	|8	|9	|
11	|	|	|3	|4	|5	|6	|7	|8	|9	|
11	|12	|	|3	|4	|5	|6	|7	|8	|9	|
Queue is full
11	|12	|	|3	|4	|5	|6	|7	|8	|9	|

처음 enqueue 값이 들어간 자리가 첫 번째 자리가 아니라 두 번째 자리인 것을 확인할 수 있다. 앞서 is_empty 와 is_full 을 구분하기 위해 front 와 rear 값을 -1 이 아니라 0 으로 초기화한 것이 그 이유이다. 또한 그 때문에 큐의 사이즈가 10 으로 설정되어 있지만 실제로 값은 9 개 밖에 안 들어간다. 10 을 추가하려하니 큐가 가득찼다는 메시지가 출력되었다.

선형큐와 다르게 앞 공간이 있으면 배열의 끝까지 데이터를 사용하여도, 앞 부분을 활용하여 데이터를 저장하는 것 역시 확인할 수 있다. 1 부터 9 까지 값을 저장하고, 1 을 삭제한 후 11 을 추가하자 11 이 큐의 배열의 가장 앞에 저장되었다. 주의해야 할 것은 배열의 앞에 저장된 것이지 front 에 저장된 것은 아니다. display 함수는 위 결과를 보여주기 위해 구현하였고, 큐에 저장된 순서에 맞게 출력하는 것이 적절할 수 도 있다.