collections の deque というクラスについてご紹介します。
from collections import dequedeque は、キュー・スタック的処理を効率的に行うためのクラスです。
通常のリストでも append pop insert などのキュー・スタック的処理は行えますが、キュー・スタック処理のためだけに設計されたものではないため効率的ではありません。一方この deque はキュー・スタック的処理を行うことを念頭に作られているため、先頭での処理、末尾での処理ともに O(1) のオーダーで高速に実行できるとのことです。
使い方は、そのままキュー・スタック的処理を行う形になります。
以下、基本的な使い方を見ていきます。
オブジェクトの生成 基本編
オブジェクトの生成は、リストの生成時に list を使うのと同じように deque 関数を使います。
from collections import deque
# インスタンス生成
# 何も渡されなければ空のキューを生成する
d1 = deque()要素の追加
末尾や先頭への要素の追加は append や appendleft を使います。
# 末尾への要素の追加
d1.append(5)
d1.append(10)
print(d1) # => deque([5, 10])
# 先頭への要素の追加
d1.appendleft("first")
print(d1) # => deque(['first', 5, 10])要素の取り出し
末尾や先頭からの要素の取り出しは pop や popleft を使います。
# 末尾の要素の取り出し
d1.pop()
print(d1) # => deque(['first', 5])
# 先頭の要素の取り出し
d1.popleft()
print(d1) # => deque([5])複数要素の一括追加
複数の要素をまとめて追加する場合は extend や extendleft を使います。
# 末尾への複数要素の追加
d1.extend([11, 12, 13])
print(d1) # => deque([5, 11, 12, 13])
# 先頭への複数要素の追加 前から順番に追加されるので逆になる
d1.extendleft([-11, -12, -13])
print(d1) # => deque([-13, -12, -11, 5, 11, 12, 13])カウント
含まれる要素の数を数えたい場合には count を使います。
# 指定した要素がいくつ含まれているかのカウント
d1.extend([100] * 3)
print(d1.count(100)) # => 3要素を値で指定しての削除
要素を指定して削除する場合には remove を使います。該当する値がない場合には ValueError があげられます。
# 指定した要素がいくつ含まれているかのカウント
d1.remove(100) # => 成功した場合は戻り値 Noneオブジェクトの生成 応用編
オブジェクト生成に使う deque にイテラブルな要素を渡すと、各要素を持ったキューができあがります。
# list と同じようにイテラブルなオブジェクトを渡すことが可能
d2 = deque("abcd")
print(d2) # => deque(['a', 'b', 'c', 'd'])maxlen というオプション引数を渡すと、キューの最大長さを決めておくことが可能です。
# 最大長をあらかじめ決めておくことも可能
d3 = deque([], maxlen=5)
d3.extend([3] * 10)
d3.append(100)
print(d3) # => deque([3, 3, 3, 3, 100], maxlen=5)新たな要素が追加されたとき、長さが maxlen を越えるような場合は追加したのとは逆側の要素がところてん方式的に削除されます。
回転
中身を回転させたい（先頭から要素を取り出して末尾に回したい）場合には rotate を使います。
# 回転
d2 = deque("abcd")
d2.rotate(1)
print(d2) # => deque(['d', 'a', 'b', 'c'])通常のリストへの変換
通常のリストに戻したい場合には、そのまま list 関数に渡せばOKです。
# 通常のリストに戻す
d2_list = list(d2)
print(d2_list) # => ['d', 'a', 'b', 'c']ちなみに、文字列に戻したい場合も次のやり方で大丈夫かと思います。
# 通常の文字列に戻す
d2_string = "".join(list(d2))
print(d2_string) # => dabcdeque オブジェクトも list と同じくイテラブルなオブジェクトなので、 for ループに渡して処理することなんかも可能です。
インストール
デフォルトで標準ライブラリに入っているため、インストールは不要です。
以上です。
ちなみに deque の呼び方は「デック」だそうです。名前の由来も「 deque = Double Ended QUEue 」の略だと公式ドキュメントには書かれています。