Python3 キュー操作 (collections.deque)

Python3でキュー操作を行うことができる、collections.deque の基本操作メモ。

Deque とは、スタックとキューを一般化したものです

dequeは本来、左右どちらからでも出し入れのできる、両端キューを扱うためのもの。
一般的なキュー用に queue.Queue も用意されており、こちらは複数のスレッドを扱う場合でも安全に使うことができる。その分動作速度は劣る。

インデックス付けもサポートされていて、リストのように扱えるが、両端の操作しかしない場合にリストよりも効率よく動作する。

両端における append や pop を高速に行えるリスト風のコンテナ

単にキューのデータ構造を使いたいだけの場合はdequeで大丈夫。

環境

$ python3 --version
Python 3.7.4

キューの作成

q = deque([])

# import
>>> from collections import deque

# キューの作成(空で作成)
>>> q = deque([])
>>> q
deque([])

# キューの作成(最初から要素を入れておくこともできる)
>>> q = deque([1, 2, 3, 'a', 'b'])
>>> q
deque([1, 2, 3, 'a', 'b'])

追加

append(item)

# 要素の追加
# q = deque([1, 2, 3, 'a', 'b'])
>>> q.append(10)
>>> q
deque([1, 2, 3, 'a', 'b', 10])

取り出し

popleft()

# 先頭(左側)要素の取り出し
# q = deque([1, 2, 3, 'a', 'b'])
>>> q.popleft()
1
>>> q
deque([2, 3, 'a', 'b', 10])

# 取り出した値の変数への代入もできる
>>> item = q.popleft()
>>> item
2
>>> q
deque([3, 'a', 'b', 10])

# 右側の要素の取り出し
>>> item = q.pop()
>>> item
10
>>> q
deque([3, 'a', 'b'])

参考

公式ドキュメント：
https://docs.python.org/ja/3/library/collections.html#collections.deque

• python - Queue.Queue vs. collections.deque - Stack Overflow
  • (queue.queueとcollections.dequeの違いは "python queue.queue vs collections.deque" でググるとよかった)
• Python で「両端キュー」として使えるデータ型 collections.deque - kakakakakku blog
  • deque詳細な動作確認
• Pythonのキューと優先度付きキュー - n-knuu's logs