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

• 원형큐의 등장 이유

- 큐는 구조가 간단하고 연산이 쉬운 장점이 있지만 front와 rear포인터가 계속 증가하다

  보면 큐의 앞부분이 비어 있더라도 자료를 추가로 삽입할 수 없는 문제가 생김

- 기존에 저장된 자료를 앞으로 이동시켜 삽입할 공간을 확보하는 방법도 있지만 이 경우에도

  자료를 일일이 옮겨 주어야 하는 번거로움과 그에 따른 비용이 발생해 효율성이 떨어짐

 

• 원형큐

- 기본 큐의 처믕과 끝을 논리적(포인터)으로 연결하여 자료의 오버플로가 발생하는 문제점을

  보완하고 저장 곤간을 보다 효율적으로 사용한다는 장점을 가짐

- front와 rear의 초깃값은 0이며 자료가 입력될 때마다 rear 포인터가 한 칸씩 앞으로 이동하며

  연산을 수행함

- 모든 공간에 자료가 가득 차게 되면 front 포인터와 rear 포인터가 또 다시 같아져 포화 상태와

  공백 상태를 구분할 수 없게 됨

   ↳ 이러한 문제를 해결 하기 위해 원형 큐의 마지막 한 자리는 항상 비워 두어야 함

   ↳ 최대로 저장할 수 있는 자료의 개수를 n개라고 했을 때, rear 값이 front보다 1개 적은 시점, 즉

      원소가 n-1개 까지 자료를 입력해야 함

 

• 원형큐의 삽입

- 새로운 자료를 삽입할 때는 먼저 원형 큐 내에 여유 공간이 있는지 확인하는 절차가 필요함

 

• 원형큐의 삭제

- 저장된 자료를 삭제할 때는 먼저 front와 rear의 값을 비교하여 공백 상태가 아닌지 확인

- 큐 안에 삭제할 원소가 남아 있으면 front를 1 증가시킨 후 해당 위치의 원소를 반환함