Queue

큐는 시퀀스의 한쪽 끝에는 엔티티를 추가하고, 다른 반대쪽 끝에는 제거할 수 있는 엔티티 걸렉션이다. 

queue

FIFO(First In First Out)로 처리되는, 줄을. 서는 것에 비유할 수 있는 큐는 상대적으로 스택에 비해서 쓰임새가 적다. 그러나 스택에 비해서 그렇다는 얘기일 뿐, 데크(deque)나 우선순위큐(priority queue) 같은 변형들은 여러분야에서 매우 유용하게 쓰인다.

이외에도 너비우선 탐색(Breadth-First Search)이나 캐시등을 구현할때도 널리 사용된다. 파이썬에는 동일한 이름의 queue라는 모듈이 있긴 하지만 이 모듈은 사실상 자료구조로서의 큐보다는 동기화 기능에 집중된 모듈로, 큐 자료형을 위해 널리 쓰이는 모듈은 아니다. 

사실상 파이썬의 리스트가 큐의 모든 연산을 지원하기 때문에 그대로 사용해도 무방하지만 좀 더 나은 성능을 위해서는 양방향 삽입, 삭제가 모두 O(1)에 가능한 데크를 사용하는 편이 좋다.