[자료구조] Circular Queue

지난 글에서 큐에 대한 대략적인 개념을 공부했습니다.

 

하지만 앞에서 공부했던 대로 큐를 구현하게 되면 문제가 한 가지 존재합니다. 바로 add와 delete를 반복적으로 계속 수행하다 보면 front와 rear는 계속 증가하게 될 것이고, 그러면 아래의 그림과 같이 배열에 안쓰는 부분이 계속 증가하여 공간을 낭비하게 됩니다.

 

그래서 front와 rear가 너무 커지게 되면 이것을 다시 앞으로 당겨주는 작업이 필요하게 됩니다. 하지만 아무래도 이러한 작업이 번거롭다 보니 circular queue (원형 큐)라는 것이 등장합니다.

 

Cricular Queue

 

원형 큐는 위의 그림과 같은 형태로 큐의 양 쪽 끝을 이어놓은 형태입니다. 이런 형태로 구현을 하면 굳이 뒤로 밀린 front와 rear를 앞으로 당기지 않고 계속 순환하면서 큐를 사용할 수 있습니다.

 

add와 delete의 구현은 다음과 같습니다.

 

void addq (element item) {
 
      rear = (rear+1) % MAX_QUEUE_SIZE;
 
      if (front == rear)
 
            printf("Queue is Full\n");      
 
      queue [rear] = item;       
 
}
 
 
 
element deleteq () {
 
      if (front == rear)  // front와 rear의 값이 같다는 말은 큐가 비어있다는 것을 뜻합니다.
 
             printf("Queue is Empty\n");
 
      front = (front+1) % MAX_QUEUE_SIZE;
 
      return queue [front];
 
}

---

스택을 동적 할당을 이용하여 구현한 것 처럼 원형 큐도 동적 할당을 이용하여 큐가 가득찰 때 마다 큐를 늘려주면 메모리가 허락하는 한 계속해서 큐를 확장하여 사용할 수 있습니다.

 

하지만 스택과는 달리 원형 큐는 고려해야 할 부분이 하나 존재합니다. 바로 새로 배열의 크기를 늘려주면서 이미 원형 큐에 들어가있는 데이터들을 정리해주어야 한다는 점입니다.

 

물론 충분히 위의 그림과 같이도 구현할 수 있습니다. 하지만 worst case의 경우에 따라서는 굉장히 비효율적인 방법일 수도 있습니다. 그래서 우리는 아래와 같이 정렬을 하는 방법을 사용해 보려고 합니다. 

 

 

위의 사항을 고려하여 queue가 가득찼을 때 실행할 queueFull()을 구현하면 다음과 같습니다.

 

void queueFull() {
 
      element *newQueue = (element *)malloc(sizeof(2*capacity*sizeof(*queue)); // 새로운 큐를 생성.
                                                                               // queue는 기존의 큐를 뜻합니다.
      int start = (front+1) % capacity;
 
      if (start < 2)
            copy (queue+start, queue+start+capacity-1, newQueue);
      else {
            copy (queue+start, queue+capacity, newQueue);
            copy (queue, queue+rear+1, newQueue+capacity-start);
      }
 
 
      front = 2 * capacity - 1;
      rear = 2 * capacity - 2;
      capacirt *= 2;
 
      free(queue);
      queue = newQueue;
}

 

copy 함수는 개인적으로 구현을 하시면 될 것 같습니다.

 

이상으로 원형 큐에 대해 알아보았습니다. 읽어주셔서 감사합니다.