원형 큐(Circular Queue)

원형큐

원형큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일하다. 그러나 마지막 위치가 시작위치와 연결되는 원형 구조를 띠기 때문에 링 버퍼 라고도 부른다.

 

기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없었다. 심지어 앞쪽에 요소들이 deQueue()로 모두 빠져서 충분한  공간이 남게 돼도 그쪽으로는 추가할 수 있는 방법이 없다. 그래서 앞쪽에 공간이 남아 있다면 이 그림처럼 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용 가능한 구조가 바로 원형 큐이다. 원형큐의 삽입과 삭제 원리는 위의 그림과 같다.

동작하는 원리는 투 포인터와도 비슷하다. 마지막 위치와 시작 위치를 연결하는 원형 구조를 만들고, 요소의 시작점과 끝점을 따라 투 포인터가 움직인다. 그림 처럼 enQueue()를 하게 되면 rear 포인터가 움직이고 deQueue()를 하게되면 front 포인터가 앞으로 이동한다. 그림에서  만약 deQueue()를 하지않고 계속 진행하여 60을 enQueue하려고 하면 rear 포인터와 front 포인터가 같은 위치에서 서로 만나게 되어 공간부족에러가 발생된다.