[Data Structure] #3-1 원형 큐 (Circular Queue)

원형 큐 (Circular Queue)

 큐를 다루는 첫 포스트다. 큐는 실생활을 프로그램으로 표현할 때 많이 사용된다. 그러다보니 본 필자의 전공인 산업공학에서 자주 발견할 수 있다. 특히나... 이번학기에 있었던 경영과학(Oeration Research) 과목에서 Queuing Model을 배우기도 했다. 잡설은 그만하고 큐에 대해 알아보자. 큐는 먼저 들어간 녀석이 먼저 나오는 구조다. 예를 들면 은행에서 줄을 선다던지 맥도날드에서 주문하려고 서는 줄에서 볼 수 있다. 먼저 들어간 것이 먼저 나온다. 우리 삶의 일반적인 규칙이다. 그 규칙이 바로 큐인 것이다.

 스택에는 top이라는 index가 있다면 큐에는 front와 rear가 있다. 초기 큐는 front와 rear 둘 모두 0을 가리킨다. 이 때, Max Size가 3이라고 가정하자. 아이템이 하나 삽입 되면 rear 가 1이 되고 index 1에 아이템이 삽입된다. 그리고 한번 더 아이템을 삽입하면 rear가 2가 되고 index 2에 아이템이 삽입 된다. 이제 한번 더 아이템을 삽입하면 어떻게 되어야 할까? 배열은 0,1,2만 사용이 가능하다. 이제 큐는 이제 꽉 찬 것이다. 더 이상 아이템을 넣을 수 없다. 자, 그럼 삽입을 위해 하나를 삭제해보자. 아이템을 하나 빼게 되면 front 가 +1이 되고 index 1의 아이템이 사라진다. 이 때 front는 idnex 1을 rear는 index 2를 가리킨다. 그리고 아이템은 하나만 있으니 하나를 더 넣을 수 있어야 한다. 이제 다시 아이템을 삽입한다고 가정해보자.. 근데 이미 꽉 찬 상태라고 출력된다... 뭔가 이상하다.

 여기서 원형 큐의 개념이 나온다. rear는 2를 가리키고 있고 front는 1을 가리키고 있다. index 0은 비어있다. rear가 index 0을 가리키고 아이템을 삽입해야하는 상황인 것이다. 그래서 % keyword를 사용한다. % 키워드는 프로그래밍 중에 꽤나 자주 사용되는데도 불구하고 잘 못쓰는 사람이 많다. 단순하다. %는 한정된 숫자 사이를 반복할 때 사용한다. 왜냐하면 나머지 키워드이니까. 이 부분은 주제와 동떨어지므로 자세히 설명하지 않겠다. 다만 지금 상황에서 보면... max size가 3 (배열이기 때문에 index 0, 1, 2를 사용할 수 있다)이고 rear가 2를 가리키고 있고 front는 1을 가리키고 있으므로 index 0은 비었다. 그리고 새롭게 삽입시에 rear가 0을 가리켜야 한다. 이때에는 (rear+1) % MAX_SIZE를 해주면 된다. 요 부분 이해 안가는 나머지 연산자를 가지고 조금만 놀아보라.. % 연산자를 통해서 원형 큐가 완성된다.

 근데 왜 max size가 3인데 (배열에서는 0,1,2) 초기 front와 rear는 0을 가리키고 있고 삽입/삭제 시에 미리 +1을 한 후에 작동을 하는 걸까? 그렇게 되면 index 0은 비워진 상태로 삽입이 되지 않겠는가?... 사실 큐는 한 자리를 무조건 비운다. 한 자리를 비우는 이유는 큐가 꽉 찼는지 혹은 완전히 비었는지 구별하기 위함이다. 조금 전 상황으로 되돌아가보자.

 rear는 index 2를 기리키고 있고 front는 index 1을 가리킨다. index 0과 1은 비어있고 2에는 아이템이 존재한다. 한번 더 삭제를 해보자. front가 +1이 되면서 index 2에 있는 아이템까지 삭제된다. 자, 여기서 큐가 완전히 비었다는 것을 체크 할 수 있다. 그것은 바로 rear와 front가 같을 때이다. 이 때에는 큐가 빈 것이다. 아니, 그럼 꽉 찬 상황은 뭐가 다르단 말인가?

 다시 상황을 정의해보자. rear와 front가 초기 index 0을 가리키는데 아이템이 두 번 삽입 되어 rear가 2를 가리키고 있다고 가정하자. 그럼 front는 여전히 0을 가리키고 있을 것이다. 여기서 rear가 원형 큐의 특성으로 index 0에 아이템을 넣었다고 하면 front와 rear는 같은 index 0을 가리키게 된다. 분명히 꽉 찼는데 완전히 빈 상황과 똑같은 상황이 되었다. rear와 front가 같은 index를 가리키고 있는 것이다. 그래서 이것을 방지하기 위해 한 칸을 비우는 것이다. 이것을 체크 하기 위해 코드에서는 rear+1과 front가 같은지를 검사한다.

 이제 코드를 보도록 하자. 

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

#define MAX_QUEUE_SIZE 100

typedef int element;
typedef struct {
    element queue[MAX_QUEUE_SIZE];
    int rear;
    int front;
} QueueType;

void error(char *message){
    fprintf(stderr,"%s\n",message);
    exit(1);
}

// 초기 front와 rear를 0으로 하는 이유는
// empty와 full을 구분하기 위한 index 0을 비우기 위해서다.
void init(QueueType *q){
    q->front = 0;
    q->rear = 0;
} 

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

// % 연산자는 제한된 index를 반복하기 위해서 사용한다
int is_full(QueueType *q){
    return (q->rear+1) % MAX_QUEUE_SIZE == q->front;
}

void enqueue(QueueType *q, element item){
    if (is_full(q)){
        error("q is full");
        exit(1);
    }
    q->rear = (q->rear+1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}

element dequeue(QueueType *q){
    if (is_empty(q)){
        error("q is empty");
        exit(1);
    }
    q->front = (q->front+1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}

element peek(QueueType *q){
    if (is_full(q)) {
        error("q is full");
        exit(1);
    }
    return q->queue[(q->front+1) % MAX_QUEUE_SIZE];
}

int main(){
    QueueType q;
    init(&q);

    printf("front=%d rear=%d\n",q.front,q.rear);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    enqueue(&q, 3);
    
    printf("dequeue()=%d\n",dequeue(&q));
    printf("dequeue()=%d\n",dequeue(&q));
    printf("dequeue()=%d\n",dequeue(&q));
    printf("front=%d rear=%d\n",q.front,q.rear);
    
    return 0;
}

 사실 큐는 연결리스트, 스택처럼 자주 사용되기 때문에 대부분의 프로그래머들이 익숙할 것이다. 여기서는 기초적인 내용을 다루고자 하였으니 혹시 자신이 이 부분을 모르겠다면 어서 공부가 시급한 상황이다. 자료구조를 모르고서는 프로그래머가 될 수 없다 :) 오늘 포스트는 여기서 마친다. 궁금한 점이 있다면 댓글로 남겨주면 빠르게 답변하겠다 :)