Queue
-
원형 큐(Circular Queue)언어/파이썬 2021. 1. 18. 23:26
원형큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일하다. 그러나 마지막 위치가 시작위치와 연결되는 원형 구조를 띠기 때문에 링 버퍼 라고도 부른다. 기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없었다. 심지어 앞쪽에 요소들이 deQueue()로 모두 빠져서 충분한 공간이 남게 돼도 그쪽으로는 추가할 수 있는 방법이 없다. 그래서 앞쪽에 공간이 남아 있다면 이 그림처럼 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용 가능한 구조가 바로 원형 큐이다. 원형큐의 삽입과 삭제 원리는 위의 그림과 같다. 동작하는 원리는 투 포인터와도 비슷하다. 마지막 위치와 시작 위치를 연결하는 원형 구조를 만들고, 요소의 시작점과 끝점을 따라 투 포인터가 움직인다. 그림 처럼 enQueue()를 하게 ..
-
Queue언어/파이썬 2021. 1. 16. 19:06
큐는 시퀀스의 한쪽 끝에는 엔티티를 추가하고, 다른 반대쪽 끝에는 제거할 수 있는 엔티티 걸렉션이다. FIFO(First In First Out)로 처리되는, 줄을. 서는 것에 비유할 수 있는 큐는 상대적으로 스택에 비해서 쓰임새가 적다. 그러나 스택에 비해서 그렇다는 얘기일 뿐, 데크(deque)나 우선순위큐(priority queue) 같은 변형들은 여러분야에서 매우 유용하게 쓰인다. 이외에도 너비우선 탐색(Breadth-First Search)이나 캐시등을 구현할때도 널리 사용된다. 파이썬에는 동일한 이름의 queue라는 모듈이 있긴 하지만 이 모듈은 사실상 자료구조로서의 큐보다는 동기화 기능에 집중된 모듈로, 큐 자료형을 위해 널리 쓰이는 모듈은 아니다. 사실상 파이썬의 리스트가 큐의 모든 연산을..