Pythonのdeque（デック）徹底解説！追加・削除・回転など主要メソッドの使い方

deque（デック）とは

dequeは、スタックとキューを一般化したデータ構造で、両端から要素を出し入れできる「双方向キュー」です。Pythonでは標準ライブラリのcollectionsモジュールに含まれており、リストをもとに生成できます。最大の特徴は、要素の追加（append）と削除（pop）がどちらもO(1)の計算量で高速に実行できる点です。

dequeを使うには、まずcollectionsモジュールをインポートします。

import collections

以下では、dequeクラスの主なメソッドを機能別に解説していきます。

要素の追加：append()とappendleft()

dequeには2種類の追加メソッドがあります。append()は右端に要素を追加し、appendleft()は左端に要素を追加します。

サンプルコード

import collections as col

# 最初にいくつかの要素を挿入
my_deque = col.deque('124dfre')
print('Dequeue: ' + str(my_deque))

# 右端にx、左端にBを追加
my_deque.append('x')
my_deque.appendleft('B')
print('Dequeue after appending: ' + str(my_deque))

実行結果

Dequeue: deque(['1', '2', '4', 'd', 'f', 'r', 'e'])
Dequeue after appending: deque(['B', '1', '2', '4', 'd', 'f', 'r', 'e', 'x'])

要素の取り出し：pop()とpopleft()

追加と同様に、取り出しにも2種類のメソッドがあります。pop()は右端の要素を削除して返し、popleft()は左端の要素を削除して返します。

サンプルコード

import collections as col

# 最初にいくつかの要素を挿入
my_deque = col.deque('124dfre')
print('Dequeue: ' + str(my_deque))

# 右端と左端から要素を削除
item = my_deque.pop()
print('Popped Item: ' + str(item))

item = my_deque.popleft()
print('Popped Item: ' + str(item))

print('Dequeue after pop operations: ' + str(my_deque))

実行結果

Dequeue: deque(['1', '2', '4', 'd', 'f', 'r', 'e'])
Popped Item: e
Popped Item: 1
Dequeue after pop operations: deque(['2', '4', 'd', 'f', 'r'])

要素の情報取得：index()とcount()

dequeには、要素に関する情報を取得するためのメソッドもあります。代表的なものがindex()とcount()です。

• index()：指定した要素が最初に出現する位置（インデックス）を返します。開始位置や終了位置を引数で指定すると、その範囲内だけを検索します。
• count()：指定した要素がdeque内に出現する回数を数えます。

サンプルコード

import collections as col

# 最初にいくつかの要素を挿入
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))

# Dのインデックスを検索
print('Index of D:' + str(my_deque.index('D')))
print('Index of D in range 5 to 8 is: ' + str(my_deque.index('D', 5, 8)))

# 出現回数をカウント
print('Occurrences of A: ' + str(my_deque.count('A')))
print('Occurrences of D: ' + str(my_deque.count('D')))

実行結果

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Index of D:4
Index of D in range 5 to 8 is: 5
Occurrences of A: 2
Occurrences of D: 3

任意の位置への挿入と削除：insert()とremove()

これまで見たappend系・pop系メソッドのほかに、挿入と削除に関連するメソッドが2つあります。insert()は挿入位置（インデックス）を指定して要素を追加でき、remove()は指定した要素の最初の出現箇所を削除します。

サンプルコード

import collections as col

# 最初にいくつかの要素を挿入
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))

# 位置5にG、位置7にHを挿入
my_deque.insert(5, 'G')
my_deque.insert(7, 'H')
print('Dequeue after inserting: ' + str(my_deque))

# 最初に出現するDを削除
my_deque.remove('D')
print('Dequeue after removing: ' + str(my_deque))

実行結果

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Dequeue after inserting: deque(['A', 'A', 'B', 'C', 'D', 'G', 'D', 'H', 'E', 'F', 'D'])
Dequeue after removing: deque(['A', 'A', 'B', 'C', 'G', 'D', 'H', 'E', 'F', 'D'])

複数要素の一括追加：extend()とextendleft()

拡張系メソッドは、複数の要素を一度にdequeへ追加するときに使います。リストやタプルなどのイテラブルを渡すことで、まとめて値を追加できます。

• extend()：右端に要素を順に追加します。append()を繰り返し呼び出すのと同じ動作です。
• extendleft()：左端に要素を順に追加します。appendleft()を繰り返すのと同じため、渡した順序とは逆の並びになる点に注意してください。

サンプルコード

import collections as col

# 最初にいくつかの要素を挿入
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))

# 右端に1, 3, 5, 7を、左端にx, y, zを追加
my_deque.extend([1, 3, 5, 7])
my_deque.extendleft(['x', 'y', 'z'])
print('Dequeue after Extending: ' + str(my_deque))

実行結果

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Dequeue after Extending: deque(['z', 'y', 'x', 'A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D', 1, 3, 5, 7])

反転と回転：reverse()とrotate()

reverse()メソッドを使うと、dequeの要素の並びを反転できます。また、rotate()メソッドを使うと、引数に指定した数だけ要素を回転させられます。正の数を指定すると右方向へ、負の数を指定すると左方向へ回転します。

サンプルコード

import collections as col

# 最初にいくつかの要素を挿入
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))

# 要素を反転
my_deque.reverse()
print('Deque after Reversing:' + str(my_deque))

# 右方向に3要素分回転
my_deque.rotate(3)
print('Deque after rotating:' + str(my_deque))

実行結果

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Deque after Reversing:deque(['D', 'F', 'E', 'D', 'D', 'C', 'B', 'A', 'A'])
Deque after rotating:deque(['B', 'A', 'A', 'D', 'F', 'E', 'D', 'D', 'C'])

まとめ

dequeは、両端への追加・削除がO(1)で行える高性能なデータ構造です。キュー処理や履歴管理、スライディングウィンドウのような処理など、両端操作が頻繁に発生する場面で特に威力を発揮します。append/pop系、index/count系、insert/remove、extend系、reverse/rotateと、目的に応じた豊富なメソッドが用意されているので、ぜひ活用してみてください。