[자료구조] 원형 큐 (Circular Queue)

원형 큐 (Circular Queue)

앞서 선형 큐의 단점을 설명하면서 rear가 가리키는 인덱스에 삽입한다고 했습니다. 이는 큐의 크기에 따라 제한될 수 있다고 했습니다. 원형 큐는 이 점을 개선할 수 있습니다. 어떤 방식으로 개선할 수 있을까요?

 

큐의 삽입 함수인 enqueue()에서는 rear을 1 증가시키면서 다음 인덱스에 큐를 삽입할 수 있습니다. 만약 MAX_QUEUE_SIZE에 인덱스가 접근하려고 하면 자동으로 인덱스를 0으로 만들어주면 될 것입니다. 이렇게 숫자가 꽉 차면 0으로 돌아가는 현상을 어디서 겪을 수 있을까요? 바로 나머지 연산에서 찾을 수 있습니다.

0을 5로 나누었다고 해봅시다. 수학적으로는 말이 안되지만, 일단 해봅시다. 나머지 연산에 따르면 나머지가 0이 나옵니다. 1를 5로 나눈다면, 나머지는 1입니다. … 5를 5로 나눠봅시다. 나머지가 다시 0이 나옵니다. 이렇게 0 → 1 → … → 4→ 0으로 순환하는 것을 알 수 있습니다. 여기에서 아이디어를 얻어 원형 큐라는 것을 만들 수 있는 것입니다.

 

사실은, 큐가 진짜로 원형으로 이루어져 있는 것은 아닙니다. 단지 인덱스가 큐의 끝에 도달한다면 다시 처음을 가리키도록 짜 마치 원형처럼 순환하기 때문에 표현만 원형 큐라고 하는 것입니다.

 

전체 코드는 아래와 같습니다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct {
    element data[MAX_QUEUE_SIZE];
    int front, 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 print_q(Queue *q) {
    printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
    if(!is_empty(q)) {
        int i = q->front;
        do {
            i = (i + 1) % (MAX_QUEUE_SIZE);
            printf("%d | ", q->data[i]);
            if(i == q->rear) {
                break;
            }
        } while(i != q->front);
    }
    printf("\n");
}

void enqueue(Queue *q, element item) {
    if(is_full(q)) {
        fprintf(stderr, "큐가 꽉 차있습니다.");
        return;
    }
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
}

element dequeue(Queue *q) {
    if(is_empty(q)) {
        fprintf(stderr, "큐가 비어있습니다.");
        exit(1);
    }
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}

int main() {
    Queue q;
    int element;

    init_queue(&q);
    printf("=== 데이터 추가 단계 ===\n");
    while(!is_full(&q)) {
        scanf("%d", &element);
        enqueue(&q, element);
        print_q(&q);
    }
    printf("큐가 꽉 찼습니다.\n");
    print_q(&q);

    printf("===데이터 삭제 단계===\n");
    while(!is_empty(&q)) {
        element = dequeue(&q);
        printf("꺼내진 정수: %d \n", element);
        print_q(&q);
    }
    printf("큐가 비어있습니다.");
}

입출력 결과.