deque(collections)で実装する効率的なキューとスタック：リストとの違いを解説

2026年5月1日

基礎知識

Pythonでのデータ管理において、リストは非常に多機能で便利な存在です。

しかし、データの追加や削除の順序が重要となる「スタック」や「キュー」を扱う際、リストの使用が必ずしも最適とは限りません。

特に大量のデータを扱うアプリケーションでは、計算効率の差がパフォーマンスに直結します。そこで役立つのが、Python標準ライブラリの collections モジュールに含まれる deque です。

本記事では、deque を用いた効率的なキューとスタックの実装方法を、リストとの違いを交えて詳しく解説します。

データ構造の基礎：スタックとキューとは

プログラミングにおける基本的なデータ構造として、スタックとキューは頻繁に登場します。

これらはデータの保持方法ではなく、データの「取り出し方」にルールがある構造です。

スタック (Stack) の仕組み

スタックは、LIFO (Last-In, First-Out：後入れ先出し) と呼ばれる仕組みです。

最後に保存したデータが最初に読み出されます。

身近な例では、机に積み上げられた本や、ブラウザの「戻る」ボタンの履歴管理、プログラミングにおける関数のコールスタックなどが挙げられます。

キュー (Queue) の仕組み

キューは、FIFO (First-In, First-Out：先入れ先出し) と呼ばれる仕組みです。

最初に保存したデータが最初に読み出されます。

レジの待ち行列や、プリンターの印刷ジョブ、OSのタスクスケジューリングなどがこの形式を採用しています。

Pythonのリストによる実装とその限界

Pythonの list 型は非常に強力で、スタックやキューの挙動を模倣することが可能です。

しかし、特定の操作においてパフォーマンス上の問題が発生します。

リストをスタックとして使う場合

リストの末尾に対して操作を行う場合、パフォーマンスは非常に良好です。

Python

# リストをスタックとして利用する例
stack = []

# データの追加 (Push)
stack.append("A")
stack.append("B")
stack.append("C")

# データの取り出し (Pop)
item = stack.pop()
print(f"取り出したアイテム: {item}")
print(f"現在のスタック: {stack}")

実行結果

取り出したアイテム: C
現在のスタック: ['A', 'B']

リストの末尾への追加 append() と末尾からの削除 pop() は、平均して O(1) (定数時間) で動作します。

そのため、スタックとしてリストを利用することには大きな問題はありません。

リストをキューとして使う際の問題点

一方で、リストをキューとして使う（先頭からデータを取り出す）場合には、重大な欠点が生じます。

Python

# リストをキューとして利用する例
queue = ["A", "B", "C"]

# 先頭からデータを取り出す
first_item = queue.pop(0)
print(f"取り出したアイテム: {first_item}")
print(f"現在のキュー: {queue}")

実行結果

取り出したアイテム: A
現在のキュー: ['B', 'C']

この queue.pop(0) は、O(n) (線形時間) の計算量を必要とします。

なぜなら、リストの先頭要素を削除すると、それ以降にあるすべての要素を一つずつ左にずらす必要があるからです。

要素数が100万個あるリストの先頭を削除すると、99万9999個の要素を移動させる処理が発生し、プログラムの動作が著しく低下します。

collections.deque の導入

リストの欠点を克服するために設計されたのが、collections.deque (ダブルエンディッド・キュー) です。

deque とは何か

deque は「デック」と読み、双方向からの追加・削除が可能なデータ構造です。

内部的には「双方向連結リスト」に近い構造（実際にはブロック単位のリスト）で実装されており、先頭および末尾へのアクセスが常に O(1) で行えるよう最適化されています。

deque の基本的な使い方

まずは、deque のインポートと初期化方法を確認しましょう。

Python

from collections import deque

# 空のdequeを作成
d = deque()

# 初期値を持つdequeを作成
d = deque(["A", "B", "C"])

print(d)

実行結果

deque(['A', 'B', 'C'])

deque による効率的なスタックの実装

deque をスタックとして利用する場合、リストと同様のメソッド名を使用できます。

Python

from collections import deque

# スタックの初期化
stack = deque()

# データのプッシュ (末尾追加)
stack.append("Task1")
stack.append("Task2")
stack.append("Task3")

# データのポップ (末尾削除)
print(stack.pop())
print(stack.pop())

# 残りの状態確認
print(f"現在のスタックの状態: {stack}")

実行結果

Task3
Task2
現在のスタックの状態: deque(['Task1'])

リストと比較して、スタックとしての挙動に大きな違いはありませんが、deque はメモリ割り当てがブロック単位で行われるため、非常に巨大なスタックを扱う際のメモリ効率や再割り当てのコストにおいて、リストよりも予測可能なパフォーマンスを発揮します。

deque による効率的なキューの実装

deque の真価が発揮されるのがキューの実装です。

先頭からの取り出し (popleft)

リストでは低速だった先頭の削除が、deque では popleft() メソッドによって高速に行えます。

Python

from collections import deque

# キューの初期化
queue = deque(["User1", "User2", "User3"])

# 新規ユーザーの追加 (末尾)
queue.append("User4")

# 処理待ちユーザーの取り出し (先頭)
processed_user = queue.popleft()
print(f"処理されたユーザー: {processed_user}")

# 次のユーザーの取り出し
next_user = queue.popleft()
print(f"次のユーザー: {next_user}")

print(f"待機列の状態: {queue}")

実行結果

処理されたユーザー: User1
次のユーザー: User2
待機列の状態: deque(['User3', 'User4'])

popleft() は、要素を移動させることなくポインタの操作のみで完結するため、データ量が増えても処理時間が一定です。

これは大規模なデータストリーム処理において必須の特性と言えます。

リストと deque の計算量の比較

ここで、リストと deque の主要な操作における計算量 (Big O記法) を比較表にまとめます。

操作内容	リスト (list)	デック (deque)
末尾への追加 (`append`)	O(1)	O(1)
先頭への追加 (`insert(0)/appendleft`)	O(n)	O(1)
末尾の削除 (`pop()`)	O(1)	O(1)
先頭の削除 (`pop(0)/popleft`)	O(n)	O(1)
任意位置の参照 (`obj[i]`)	O(1)	O(n)

この表からわかる通り、deque は両端の操作に特化しています。

一方で、「特定のインデックスにある要素にアクセスする」 操作については、リストの方が圧倒的に高速です。

deque は内部が連結された構造であるため、真ん中あたりの要素にアクセスするには先頭か末尾から順番に辿る必要があります。

したがって、「ランダムアクセスを多用する場合はリスト」「両端の追加・削除がメインなら deque」 という使い分けが重要になります。

deque の便利な応用機能

deque には、単なるキューやスタック以上の便利な機能が備わっています。

最大長の制限 (maxlen)

deque の初期化時に maxlen 引数を指定することで、保持する要素の最大数を制限できます。

Python

from collections import deque

# 最大3つのログを保持するバッファ
recent_logs = deque(maxlen=3)

recent_logs.append("Log 1")
recent_logs.append("Log 2")
recent_logs.append("Log 3")
print(f"フル状態: {recent_logs}")

# 新しいログを追加すると、最も古いものが自動的に消える
recent_logs.append("Log 4")
print(f"追加後の状態: {recent_logs}")

実行結果

フル状態: deque(['Log 1', 'Log 2', 'Log 3'], maxlen=3)
追加後の状態: deque(['Log 2', 'Log 3', 'Log 4'], maxlen=3)

この機能は、直近の履歴のみを保持したい場合や、スライディングウィンドウアルゴリズムを実装する際に非常に有用です。

要素の回転 (rotate)

rotate() メソッドを使用すると、要素を効率的にシフトさせることができます。

Python

from collections import deque

d = deque([1, 2, 3, 4, 5])

# 右に2つ回転
d.rotate(2)
print(f"右に2回転: {d}")

# 左に1つ回転 (負の値を指定)
d.rotate(-1)
print(f"左に1回転: {d}")

実行結果

右に2回転: deque([4, 5, 1, 2, 3])
左に1回転: deque([5, 1, 2, 3, 4])

実践的な活用シーン

実際にどのような場面で deque を選ぶべきか、具体的なケースを紹介します。

幅優先探索 (BFS)

グラフやツリーの探索アルゴリズムの一つである幅優先探索では、探索候補のノードをキューで管理します。

この際、リストを使用するとノード数が増えるにつれて急激にパフォーマンスが悪化するため、必ず deque を使用します。

Python

from collections import deque

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        node = queue.popleft() # ここでdequeの高速性が活きる
        print(f"訪問中: {node}")

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# グラフ構造の例
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [], 'E': [], 'F': []
}

bfs(graph, 'A')

リアルタイムデータ処理

IoTデバイスからのセンサーデータやWebサービスのアクセスログなど、絶え間なく流れてくるデータを一定期間だけ保持して解析する場合、maxlen を設定した deque が最適です。

メモリを固定しながら最新の状態を追いかけることができます。

履歴管理 (Undo機能)

エディタの「元に戻す (Undo)」機能を実装する場合、操作履歴をスタックに保存します。

最新の100件まで保持し、古いものから捨てるという仕様であれば、deque(maxlen=100) を使うことで、複雑な削除ロジックを書かずに済みます。

スレッドセーフティについて

Pythonの deque は、スレッドセーフな実装になっています。

append や popleft といった単一の操作は、PythonのGIL (Global Interpreter Lock) のおかげでアトミックに行われます。

つまり、複数のスレッドから同時に同じ deque オブジェクトの末尾に追加したり、先頭から取り出したりしても、内部データが壊れる心配がほとんどありません。

マルチスレッド環境でのデータ共有用キューとしても、非常に扱いやすい特性を持っています。

まとめ

Pythonの collections.deque は、スタックやキューを効率的に扱うための必須ツールです。

リストとの最大の違いは、「先頭要素の操作」に対するパフォーマンスにあります。

リストが O(n) かかる操作を、deque は O(1) でこなします。

記事の内容を振り返ると、以下のポイントが重要です。

スタック操作はリストでも問題ないが、deque でも実装可能。
キュー操作はリストでは遅いため、必ず deque を使用する。
ランダムアクセス (「n番目の要素を見る」など) が多い場合は、リストの方が適している。
maxlen を使えば、古いデータを自動で破棄する固定長バッファが簡単に作れる。

用途に合わせて適切なデータ構造を選択することは、クリーンで高速なコードを書くための第一歩です。

今後、順序を伴うデータの集合を扱う際は、ぜひ deque の活用を検討してみてください。