Pythonのdequeでキュー、スタック、デック（両端キュー）を扱う

Pythonの標準ライブラリcollectionsモジュールのdeque型を使うと、データをキューやスタック、デック（両端キュー）として効率的に扱うことができる。

• collections.deque --- コンテナデータ型 — Python 3.11.4 ドキュメント

組み込みのリストlistをキューやスタック、デック（両端キュー）として使うことも可能だが、リストは先頭の要素に対する削除や追加（挿入）の処理速度が遅いためdequeのほうが効率的。なお、dequeには、両端以外の要素へのアクセスが遅いというデメリットもあるので注意。

本記事のサンプルコードでは以下のようにdequeクラスをインポートして使う。

from collections import deque

リストlistに対する要素の追加・削除については以下の記事を参照。

• 関連記事: Pythonでリスト（配列）に要素を追加するappend, extend, insert
• 関連記事: Pythonでリスト（配列）の要素を削除するclear, pop, remove, del

リストとdequeの計算量の違い・使い分け

リストとdequeの各種操作に対する計算量は公式のWikiの以下のページにまとめられている。

• TimeComplexity - Python Wiki

リストでは先頭の要素を削除して取り出すpop(0)、先頭に要素を追加するinsert(0, v)などの操作でO(n)のコストを必要とするが、dequeでは先頭・末尾の要素を追加・削除するappend(), appendleft(), pop(), popleft()がすべてO(1)で実行できる。

公式ドキュメントにも記載されている。

Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。

list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。
collections.deque --- コンテナデータ型 — Python 3.11.4 ドキュメント

一方、両端以外の要素に対する[]によるアクセス（取得）はリストのほうが有利。

（dequeは）d[0] のような添字による参照をサポートしています。添字によるアクセスは、両端の要素では O(1) ですが、中央部分の要素では O(n) と遅くなります。高速なランダムアクセスのためには、代わりにリストを使ってください。 collections.deque --- コンテナデータ型 — Python 3.11.4 ドキュメント

したがって、ざっくりとした使い分けの指針は以下の通り。

• 要素の追加・取り出し（削除）・アクセス（取得）が両端のみ → deque
• 両端以外の要素に頻繁にアクセス → リスト

明確にキューやスタック、デックとしてデータを扱いたい、という場合は dequeを使ったほうがよい。

ただ、環境や条件にもよるが、要素数が数百個や数千個程度であれば、リストでもdequeでも体感できるほどの処理速度の差はない。ミリ秒オーダーで処理時間を切り詰めたいアプリケーションや競技プログラミングでもない限り、多くの場合はリストを使っていても特に問題はないはず。

とはいえ、リストは先頭に要素を追加したり先頭の要素を削除したりするのが遅い、dequeは中央部分の要素へのアクセスが遅い、といったことは頭に入れておくといいだろう。

環境や条件が固定された状態でどちらを使うか検討する場合はtimeitモジュールで処理時間を実測するとよい。

• 関連記事: Pythonのtimeitモジュールで処理時間を計測

collections.dequeの使い方

以下のようにcollectionsモジュールからdequeクラスをインポートして使う。

from collections import deque

dequeオブジェクトの生成

コンストラクタdeque()でdequeオブジェクトを生成する。

引数を省略すると空のdequeオブジェクト、引数にリストなどのイテラブルオブジェクトを指定するとその要素を持つdequeオブジェクトが生成される。

d = deque()
print(d)
# deque([])

print(type(d))
# <class 'collections.deque'>

d = deque(['m', 'n'])
print(d)
# deque(['m', 'n'])

第二引数maxlenで最大長（最大要素数）を制限することもできる。後述。

要素の追加: append(), appendleft(), extend(), extendleft(), insert()

append()は末尾（右側）、appendleft()は先頭（左側）に要素を追加する。

d = deque(['m', 'n'])

d.append('o')
print(d)
# deque(['m', 'n', 'o'])

d.appendleft('l')
print(d)
# deque(['l', 'm', 'n', 'o'])

extend()は末尾、extendleft()は先頭にリストなどのイテラブルオブジェクトの要素をすべて追加する。extendleft()では引数に指定したイテラブルの要素の順番が逆転して連結されるので注意。dequeの先頭にイテラブルの要素を順番に追加していくイメージ。

d.extend(['p', 'q'])
print(d)
# deque(['l', 'm', 'n', 'o', 'p', 'q'])

d.extendleft(['k', 'j'])
print(d)
# deque(['j', 'k', 'l', 'm', 'n', 'o', 'p', 'q'])

insert()で途中に要素を追加することもできる。第一引数に位置、第二引数に追加する値を指定する。第一引数に負の値を指定すると末尾からの位置になる。範囲外の位置を指定した場合は先頭か末尾に追加される。

d.insert(3, 'XXX')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'q'])

d.insert(-1, 'YYY')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q'])

d.insert(100, 'ZZZ')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q', 'ZZZ'])

d.insert(-100, 'XYZ')
print(d)
# deque(['XYZ', 'j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q', 'ZZZ'])

要素の削除: pop(), popleft(), remove(), clear()

pop()は末尾（右側）、popleft()は先頭（左側）から要素をひとつ削除し、その値を返す。リストのpop()と異なり、引数に位置を指定することはできない。

d = deque(['a', 'b', 'c', 'b', 'd'])

print(d.pop())
# d

print(d)
# deque(['a', 'b', 'c', 'b'])

print(d.popleft())
# a

print(d)
# deque(['b', 'c', 'b'])

remove()は引数に指定した値と等しい最初の要素を削除する。該当する要素が複数あっても削除されるのは最初の要素のみ。該当する要素がない場合はエラーとなる。

d.remove('b')
print(d)
# deque(['c', 'b'])

# d.remove('X')
# ValueError: deque.remove(x): x not in deque

clear()はすべての要素を削除する。空のdequeになる。

d.clear()
print(d)
# deque([])

空のdequeの場合、pop(), popleft()はエラーとなる。clear()はエラーにならない。

# d.pop()
# IndexError: pop from an empty deque

# d.popleft()
# IndexError: pop from an empty deque

d.clear()
print(d)
# deque([])

要素全体をローテート: rotate()

リストにはないメソッドとしてrotate()がある。デフォルトでは右に1個ずつ要素がローテート（スクロール）する。

d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate()
print(d)
# deque(['e', 'a', 'b', 'c', 'd'])

引数に整数値を指定すると、その個数ずつ要素が右にローテートする。負の値を指定すると左にローテート。要素数を超える値も指定可能。

d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(2)
print(d)
# deque(['d', 'e', 'a', 'b', 'c'])

d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(-1)
print(d)
# deque(['b', 'c', 'd', 'e', 'a'])

d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(6)
print(d)
# deque(['e', 'a', 'b', 'c', 'd'])

要素・インデックスの取得: [], index()

リストと同様、[]にインデックスを指定して要素を取得できる。負の値で末尾からの位置を指定することもできる。要素の変更も可能。

d = deque(['a', 'b', 'c', 'd', 'e'])
print(d[0])
# a

print(d[-1])
# e

d[2] = 'X'
print(d)
# deque(['a', 'b', 'X', 'd', 'e'])

スライス:は直接は使えないが、標準ライブラリitertoolsのislice()で代用できる。

• itertools.islice() --- 効率的なループ実行のためのイテレータ生成関数 — Python 3.11.4 ドキュメント

# print(d[2:4])
# TypeError: sequence index must be integer, not 'slice'

import itertools

print(deque(itertools.islice(d, 2, 4)))
# deque(['X', 'd'])

index()で引数に指定した値に一致する最初の要素のインデックスを取得できる。存在しない値を指定するとエラーとなる。

d = deque(['a', 'b', 'c', 'c', 'd'])
print(d.index('c'))
# 2

# print(d.index('x'))
# ValueError: 'x' is not in deque

そのほかの操作（要素数・カウント・存在確認・反転など）

そのほか、リストと同様に様々な操作が可能。

組み込み関数len()で要素数を取得。

• 関連記事: Pythonのlen関数で様々な型のオブジェクトのサイズを取得

d = deque(['a', 'a', 'b', 'c'])
print(len(d))
# 4

count()で指定した値と等しい要素の数をカウント。

• 関連記事: PythonのCounterでリストの各要素の出現個数をカウント

print(d.count('a'))
# 2

print(d.count('x'))
# 0

in演算子で要素が存在するか判定。

• 関連記事: Pythonのin演算子でリストなどに特定の要素が含まれるか判定

print('b' in d)
# True

print('x' in d)
# False

reverse()メソッド、または、組み込み関数reversed()で順番を反転。reverse()メソッドは元のオブジェクト自体が反転し、reversed()は反転したイテレータを返す。

• 関連記事: Pythonでリストや文字列を逆順に並べ替え（reverse, reversed）

d = deque(['a', 'b', 'c', 'd', 'e'])
d.reverse()
print(d)
# deque(['e', 'd', 'c', 'b', 'a'])

d = deque(['a', 'b', 'c', 'd', 'e'])
print(deque(reversed(d)))
# deque(['e', 'd', 'c', 'b', 'a'])

forループでも使える。

• 関連記事: Pythonのfor文によるループ処理（range, enumerate, zipなど）

d = deque(['a', 'b', 'c'])

for v in d:
    print(v)
# a
# b
# c

list()やtuple()でリストやタプルに変換可能。

• 関連記事: Pythonでリストとタプルを相互に変換するlist(), tuple()

d = deque(['a', 'b', 'c'])

l = list(d)
print(l)
# ['a', 'b', 'c']

print(type(l))
# <class 'list'>

maxlenで最大長（最大要素数）を制限

コンストラクタdeque()の第二引数maxlenを指定すると、最大長（最大要素数）を制限できる。maxlenのデフォルトはNoneで長さ（要素数）に制限はない。

from collections import deque

d = deque(['l', 'm', 'n'], 3)
print(d)
# deque(['l', 'm', 'n'], maxlen=3)

maxlenを設定した場合、dequeが満杯（要素数とmaxlenが等しい状態）になると、要素を追加すると逆側の要素が捨てられる。

append(), appendleft(), extend(), extendleft()での動作は以下の通り。

d.append('o')
print(d)
# deque(['m', 'n', 'o'], maxlen=3)

d.appendleft('l')
print(d)
# deque(['l', 'm', 'n'], maxlen=3)

d.extend(['o', 'p'])
print(d)
# deque(['n', 'o', 'p'], maxlen=3)

d.extendleft(['m', 'l'])
print(d)
# deque(['l', 'm', 'n'], maxlen=3)

insert()だと先頭や末尾に追加する場合でもエラーとなる。

# d.insert(0, 'XXX')
# IndexError: deque already at its maximum size

要素数がmaxlenに達していなければinsert()で追加することも可能。

print(d.pop())
# n

print(d)
# deque(['l', 'm'], maxlen=3)

d.insert(1, 'XXX')
print(d)
# deque(['l', 'XXX', 'm'], maxlen=3)

maxlenは属性として取得できるが、読み出し専用なので変更することはできない。

print(d.maxlen)
# 3

# d.maxlen = 5
# AttributeError: attribute 'maxlen' of 'collections.deque' objects is not writable

キュー（queue, FIFO）として使う

キュー（queue）は先入れ先出し（FIFO: First In, First Out）のデータ構造。キューでは、データを入れることをエンキュー（enqueue）、取り出すことをデキュー（dequeue）と呼ぶ。

• キュー (コンピュータ) - Wikipedia

dequeをキューとして使うには、エンキューとしてappend()、デキューとしてpopleft()を使えばよい。

from collections import deque

d = deque(['a', 'b', 'c'])
print(d)
# deque(['a', 'b', 'c'])

d.append('d')
print(d)
# deque(['a', 'b', 'c', 'd'])

print(d.popleft())
# a

print(d)
# deque(['b', 'c', 'd'])

スタック（stack, LIFO）として使う

スタック（stack）は後入れ先出し（LIFO: Last In, First Out）のデータ構造。スタックでは、データを入れることをプッシュ（push）、取り出すことをポップ（pop）と呼ぶ。

• スタック - Wikipedia

dequeをスタックとして使うには、プッシュとしてappend()、ポップとしてpop()を使えばよい。

from collections import deque

d = deque(['a', 'b', 'c'])
print(d)
# deque(['a', 'b', 'c'])

d.append('d')
print(d)
# deque(['a', 'b', 'c', 'd'])

print(d.pop())
# d

print(d)
# deque(['a', 'b', 'c'])

デック（deque, 両端キュー）として使う

デック（deque）は両端（先頭または末尾）で要素を追加・削除できるキューで、両端キューや双方向キューなどとも呼ばれる。

• 両端キュー - Wikipedia

これまでの例のように、dequeではappend(), appendleft(), pop(), popleft()で両端の要素の追加・削除が可能。