Pythonのdeque（両端キュー）とは？基本操作と使い方を実例付きで解説

Pythonにおけるdeque（デック、両端キュー）は、スタックやキューのようなデータ構造の一つです。最大の特徴は、先頭と末尾の両端から要素の追加・削除ができる点にあります。これは他のデータ構造にはない柔軟性であり、両端での操作が必要な場面で非常に役立ちます。

dequeは標準ライブラリのcollectionsモジュールを使って実装されており、importするだけで簡単に利用できます。この記事では、dequeで使える主な操作を一つずつ、実際のコード例とともにわかりやすく解説します。

dequeで使える主な操作一覧

dequeには以下のような便利なメソッドが用意されています。

• append(x)：引数xをdequeの右端（末尾）に追加します。

• appendleft(x)：引数xをdequeの左端（先頭）に追加します。

• pop()：右端（末尾）から要素を1つ削除し、その値を返します。

• popleft()：左端（先頭）から要素を1つ削除し、その値を返します。

• extend(iterable)：リストなどのイテラブルなオブジェクトの要素をまとめて右端に追加します。

• extendleft(iterable)：イテラブルなオブジェクトの要素をまとめて左端に追加します。左側への追加は順番に挿入されるため、元の順序は逆順になりますので注意しましょう。

• reverse()：deque内の要素の並びを反転させます。

• rotate(n)：引数nの回数だけdequeを回転させます。正の数を指定すると右方向へ、負の数を指定すると左方向へ回転します。

サンプルコード

以下のプログラムでは、collectionsモジュールを使って上記の各操作を実際に実行しています。

import collections

de = collections.deque([10, 20, 30, 40])
print(de)

# 右端に追加
de.append(50)
print("\n右端に追加した後のdeque：")
print(de)

# 左端に追加
de.appendleft(60)
print("\n左端に追加した後のdeque：")
print(de)

# 右端から削除
de.pop()
print("\n右端から削除した後のdeque：")
print(de)

# 左端から削除
de.popleft()
print("\n左端から削除した後のdeque：")
print(de)

# 右端に複数追加
de.extend([70, 80])
print("\n末尾に拡張した後のdeque：")
print(de)

# 左端に複数追加
de.extendleft([100, 90])
print("\n先頭に拡張した後のdeque：")
print(de)

# 回転（左に2つ）
de.rotate(-2)
print("\n回転させた後のdeque：")
print(de)

# 反転
de.reverse()
print("\n反転させた後のdeque：")
print(de)

実行結果

上記のコードを実行すると、次のような出力が得られます。

deque([10, 20, 30, 40])
右端に追加した後のdeque：
deque([10, 20, 30, 40, 50])
左端に追加した後のdeque：
deque([60, 10, 20, 30, 40, 50])
右端から削除した後のdeque：
deque([60, 10, 20, 30, 40])
左端から削除した後のdeque：
deque([10, 20, 30, 40])
末尾に拡張した後のdeque：
deque([10, 20, 30, 40, 70, 80])
先頭に拡張した後のdeque：
deque([90, 100, 10, 20, 30, 40, 70, 80])
回転させた後のdeque：
deque([10, 20, 30, 40, 70, 80, 90, 100])
反転させた後のdeque：
deque([100, 90, 80, 70, 40, 30, 20, 10])

まとめ

dequeは、両端からの追加・削除が高速に行えるため、キュー処理、履歴管理、スライディングウィンドウの実装など、さまざまな場面で活躍します。通常のリスト（list）では先頭への挿入・削除はO(n)の計算量がかかりますが、dequeならO(1)で処理できるのが大きなメリットです。ぜひ日常のPythonプログラミングに取り入れてみてください。