collections 모듈 (5) - deque

deque는 double-ended queue의 약자로 일반 리스트와 달리 양방향에서 처리할 수 있는 queue 자료구조입니다. 리스트처럼 맨 뒤에 자료를 추가할 수 있고 맨 앞에도 자료를 추가할 수 있습니다. 특히, 맨 앞의 자료를 추가하거나 삭제할 때, 리스트는 각 원소를 복사해야되므로 $O(n)$의 시간 복잡도가 소요되지만 deque에서는 상수 시간 복잡도 $O(1)$이 소요됩니다.

deque 생성

deque 생성 시에는 maxlen이란 파라미터를 지정할 수 있어 deque의 최대 크기를 지정할 수 있습니다. 최대 크기를 넘어갈 때에는 맨 앞의 원소가 삭제되면서 큐를 전체적으로 앞으로 이동합니다.

appendleft(), popleft(), extendleft()

deque는 맨 앞에 원소에 대한 연산을 지원합니다. 이 작업은 리스트와 달리 상수 시간 복잡도가 소요되며, 배열이 매우 큰 경우 매우 유용합니다. 특히, extendleft() 연산의 경우에는 입력으로 들어온 배열이 처음부터 왼쪽에 삽입되므로 결과적으로는 뒤집혀서 삽입됩니다.

홍머스 정리

• 앞, 뒤 모두에 대해 상수 시간 연산 가능