원형큐

개요

배열을 이용하여 Queue 를 작성할 경우, 큐의 상태를 저장하는 변수의 값(head, tail)이 감소하지 않고 계속 증가하기 때문에 한계치(QUEUESIZE) 에 도달하면 더 이상 올바른 저장소를 가리키지 못하기 때문에 이를 보완할 수 있는 방법이 필요합니다.

변수의 값이 최대치에 도달할 경우, 이를 초기값으로 돌려주는 방식으로 원형큐를 사용완가능합니다.

※ 참고로 원형큐를 링버퍼라고도 합할 수 있습니다.

다음은 이러한 아이디어를 C 언어로 구현한 것입니다.

구현

앞서 작성한 포스트의 배열로 구현한 (선형)큐의 소스코드를 기초로 합니다.

// main.c 

#define QUEUESIZE   256
#include <stdio.h>

typedef struct {
    int head, tail;
    int items[QUEUESIZE];
} Queue;

void fnInit (Queue *q) {
    q->head = q->tail = -1;
}

void fnEnque(Queue *q, int i) {
    q->items[++q->tail] = i;
}

int fnDequeue(Queue *q) {
    return q->items[++q->head];
}

int main (void) {
    Queue q;
    fnInit(&q);

    fnEnque(&q, 7);
    fnEnque(&q, 0);
    fnEnque(&q, 6);
    fnEnque(&q, 2);
    fnEnque(&q, 9);
    
    printf("%d\n", fnDequeue(&q));
    printf("%d\n", fnDequeue(&q));
    printf("%d\n", fnDequeue(&q));
    printf("%d\n", fnDequeue(&q));
    printf("%d\n", fnDequeue(&q));

    return 0;
}

우선, 원형큐는 초기 상태를 표시하는 값으로 head 와 tail 을 -1 이 아닌 큐의 인덱스값 중 하나의 값으로 선택하면 됩니다. 여기서는 0 으로 수정하도록 하겠습니다.

또한 head 와 tail 를 가르키는 값이 최대값(QUEUESIZE)에 도달하였을 때 이 값을 0 으로 해당값을 설정합니다. 즉, 앞서 언급했던 것과 같이 마지막 저장공간과 첫번째 저장공간을 서로 연결하는 것입니다.

하지만 아무때나 이 값을 초기값으로 변경할 수는 없습니다. head 와 tail 은 항상 상대적으로 움직여야 합니다. 예를 들어, 큐가 가득차 있을 경우에 데이터가 추가로 유입되었다고 하여 tail 을 임의로 진행하게 된다면, 가장 오래된 데이터가 사라지게 되는 것 입니다. 또한 데이터가 없을 때도 fnDequeue 요청에 대해서 head 를 증가시킨다면 엉뚱한 데이터를 결과로 돌려주게 됩니다.

이를 위하여 큐에 데이터가 없는 경우(fnIsEmpty) 와 큐가 가득찬 경우(fnIsFull) 를 검사하는 방법을 추가하도록 합니다.

선형큐나 원형큐 모두 데이터가 없는 경우는 head 의 값과 tail 의 값이 같을 경우 입니다. 다음 그림과 같은 형태가 될 것입니다.

        H, T         
         ↓         
(out) □ □ □ □ □ □ (in) @ QUEUESIZE(=6)

큐가 가득찬 상태는 선형큐의 경우는 QUEUESIZE 의 값과 tail의 값이 같은 경우입니다.

그림으로 그려보면 다음과 같습니다.

      H         T
      ↓         ↓
(out) ■ ■ ■ ■ ■ ■ (in) @ QUEUESIZE(=6)

반면 원형큐에서는 head 와 tail 이 순환을 하므로 조금 복잡해집니다.

다음과 같이 1개의 공간이 있을 경우, 그림을 보면 tail 의 값이 head 의 값과 2가 차이가 나는 것을 볼 수 있습니다.

       (out)    (in)
         H       T
         ↓       ↓
      □ ■ ■ ■ ■ ■ @ QUEUESIZE(=6)
       └ ─ ─ ─ ─ ┘

여기에 하나의 데이터가 더 유입되어 가득차게 된다면 다음과 같은 형태가 될 것입니다.

       T H       
       ↓ ↓       
       ■ ■ ■ ■ ■ ■ @ QUEUESIZE(=6)
       └ ─ ─ ─ ─ ┘

즉, tail 과 head 의 값이 하나차이가 날 때, 다시 말해 tail + 1 과 head 의 값이 같을 경우 가득찬 상태라는 것을 알 수 있습니다. 즉 여기에서 데이터를 하나 더 넣었을 때 가르키는 인덱스의 값이 같아진다면 가득찬 상태인 것입니다.

단 이때, 순환을 고려한다면 tail + 1 을 QUEUESIZE 로 나눈 나머지 값과 같을 경우입니다.

이상의 내용을 바탕으로 코드를 작성하면 다음과 같습니다.

int fnIsEmpty(Queue *q) {
   if (q->tail == q->head) {
     return 1;
   } else {
     return 0;
   }
}

int fnIsFull(Queue *q) {
   if (((q->tail + 1)%QUEUESIZE) == q->head) {
     return 1;
   } else {
     return 0;
   }
}

삽입(fnEnque) 연산 및 삭제(fnDeque) 에서 최대값에 도달하였을 때, head 값이 0 보다 큰 경우 tail 값을 0 으로 초기화 합니다.

int fnEnqueue(Queue *q, int i) {
    if(fnIsFull(q) == 1) {
      return -1;
    } else {
	  q->items[(q->tail++)%QUEUESIZE] = i;
	  return 0;
    }
}

int fnDequeue(Queue *q) {
	if(fnIsEmpty(q) == 1) {
	  return -1;
	} else {
	  q->items[(q->head++)%QUEUESIZE];
	  return 0;
	}
}

결론

배열을 이용하면 큐를 상대적으로 간단히 구현 할 수 있습니다. 하지만 선형큐의 경우는 배열의 원소를 가르키는 인덱스의 값이 증가하기만 할 뿐이므로 이를 보완해줄 필요가 있습니다. 이에 따라 우리는 가장 마지막 원소의 인덱스를 가장 앞선 인덱스와 연결하는 원형큐(혹은 링버퍼)의 개념을 도입하여 실무에서 사용가능한 큐를 구현해보았습니다.

다음에는 앞, 뒤 양쪽 끝에서 데이터를 입/출력할 수 있는 덱(deque) 을 이번에 작성한 배열기반의 원형큐를 기반으로 작성해보도록 하겠습니다.