キュー

コード例

from collections import deque

dq = deque([0, 1, 2, 3, 4])
dq.popleft()
print(dq) # deque([1, 2, 3, 4])

Pythonでキュー（FIFO）構造を実現するには、collections.dequeが最適である。

標準ライブラリにはqueue.Queueも存在するが、これはマルチスレッド環境での安全性を確保する機能が優先されており、アルゴリズムで利用するには不要なオーバーヘッドを持つ。

dequeは、要素の先頭・末尾どちらからの追加・削除も O(1) という非常に高速な計算量で行えるよう設計されている。これにより、アルゴリズムで求められるキューの「先頭から要素を取り出す」操作を、リスト（O(N)）よりもはるかに効率的に実行できる。