circular_Queue
-
원형 큐(Circular Queue)언어/파이썬 2021. 1. 18. 23:26
원형큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일하다. 그러나 마지막 위치가 시작위치와 연결되는 원형 구조를 띠기 때문에 링 버퍼 라고도 부른다. 기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없었다. 심지어 앞쪽에 요소들이 deQueue()로 모두 빠져서 충분한 공간이 남게 돼도 그쪽으로는 추가할 수 있는 방법이 없다. 그래서 앞쪽에 공간이 남아 있다면 이 그림처럼 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용 가능한 구조가 바로 원형 큐이다. 원형큐의 삽입과 삭제 원리는 위의 그림과 같다. 동작하는 원리는 투 포인터와도 비슷하다. 마지막 위치와 시작 위치를 연결하는 원형 구조를 만들고, 요소의 시작점과 끝점을 따라 투 포인터가 움직인다. 그림 처럼 enQueue()를 하게 ..