[Python] queue과 deque의 pop()

요새 BFS 문제를 풀고 있어서 queue를 사용할 일이 많은데 그동안은 queue의 pop() 연산을 pop(0)으로 구현했다. 따로 라이브러리를 import 하지 않아도 되기 때문에 애용하는 방식이었는데 문제는 pop(0)이 리스트의 임의의 위치에 있는 원소를 제거하는 작업이기 때문에 시간 복잡도가 O(N)이라는 것이다. 따라서 시간 초과를 피하기 위해 pop() 연산을 O(1)에 수행할 수 있는 deque에 대해 정리해두고자 한다.

deque는 stack과 queue의 기능을 모두 지닌 기특한 자료형이다. 이름에서 알 수 있듯이 double-ended queue, 앞과 뒤에서 모두 데이터의 삽입, 삭제가 가능하다. deque의 사용법은 리스트와 거의 유사하다. 대신 popleft()의 시간 복잡도가 O(1)이기 때문에 시간 초과를 피하는 데 훨씬 유리하다.

from collections import deque

queue = deque([1, 2, 3])

queue.popleft()
queue.popleft()

print(queue) # deque([3])

deque가 지원하는 다양한 메서드는 Python 공식 문서 - collections.deque에서 확인할 수 있다.