HOWTO · Python
Python でのキューの実装
この記事では、Python でのキュー データ構造の 3つの実装について説明します。 また、最適なキューの実装と、Python プログラムで使用する必要がある実装についても説明します。
このページの内容
キューは先入れ先出し（FIFO）の順序で項目を保持します。新しい項目は末尾に追加し、先頭の項目を取り出します。Pythonでは、この動作をモデル化する方法がいくつかあります。この記事では、リストと連結リストでキューを実装し、標準ライブラリの collections.deque を使う方法も紹介します。
キューの動作と基本操作
先頭は次に取り出される項目、末尾は次に項目を追加する位置です。たとえば、キューに 1, 2, 3 が入っている場合、1 が先頭で、3 が末尾です。4 を追加すると 1, 2, 3, 4 になり、1回取り出すと 1 が返されて、2, 3, 4 が残ります。
次の短い実行可能な例では、末尾への追加と先頭からの取り出しを示します。提供されたパケットにはこのコードの実行時の観測結果がないため、出力が確認済みであるとは記載していません。
このセクションのコードと表示されるラベルや出力は英語のままです。
queue = []
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
removed = queue.pop(0)
print(removed)
print(queue)
キューのインターフェースには、次の4つの操作があると便利です。enqueueは項目を追加し、dequeueは先頭の項目を取り出して返します。空チェックは項目が残っているかを調べ、長さの取得は項目数を返します。以下の実装では、空のキューからdequeueを呼び出すと (False, None) を返し、成功時には (True, item) を返します。成功フラグを返すことで、実際の項目としての None と、キューが空である状態を区別できます。
Pythonのリストでキューを実装する
リストは、簡潔な学習用の例を作るのに向いています。末尾に項目を追加し、pop(0) で先頭の項目を取り出します。コードはシンプルですが、先頭から削除すると残りの項目が移動するため、キューが大きくなるにつれてdequeueに線形時間がかかります。この例では None を含む、あらゆるPythonオブジェクトを扱えます。
次の例を実行してください。
このセクションのコードと表示されるラベルや出力は英語のままです。
class ListQueue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.items:
return False, None
return True, self.items.pop(0)
def is_empty(self):
return len(self.items) == 0
def __len__(self):
return len(self.items)
queue = ListQueue()
queue.enqueue("first")
queue.enqueue("second")
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
先頭インデックスを使うリストなら、項目を取り出すたびに残りの要素を移動せずに済みます。ただし、リストを圧縮するまで削除済みの項目が保持されます。この方法では、論理上のキュー位置とリストのインデックスを対応させる追加の管理が必要です。また、領域を安全にリセットまたは圧縮する処理も必要になります。一般的なFIFO用途では、通常 collections.deque のほうがわかりやすいでしょう。
連結リストでキューを実装する
単方向連結キューでは、各項目をノードに格納し、そのノードの next 参照が末尾側のノードを指します。両端への参照を保持します。enqueueでは新しいノードを rear の後ろにつなぎ、dequeueでは front を次のノードへ進めます。最後のノードを取り出したときは rear もクリアしてください。そうしないと、次のenqueueで古いノードを経由して追加しようとする可能性があります。この実装ではenqueueとdequeueは定数時間ですが、ノード数を数えるため、長さの取得には線形時間がかかります。
このセクションのコードと表示されるラベルや出力は英語のままです。
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedQueue:
def __init__(self):
self.front = None
self.rear = None
def enqueue(self, item):
node = Node(item)
if self.rear is None:
self.front = self.rear = node
else:
self.rear.next = node
self.rear = node
def dequeue(self):
if self.front is None:
return False, None
item = self.front.value
self.front = self.front.next
if self.front is None:
self.rear = None
return True, item
def is_empty(self):
return self.front is None
def __len__(self):
count = 0
current = self.front
while current is not None:
count += 1
current = current.next
return count
queue = LinkedQueue()
queue.enqueue(10)
queue.enqueue(20)
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
不変条件として、キューが空のときに限り、両方の参照が None になります。空でない場合、front は次に取り出す項目を指し、rear.next は None です。この不変条件を保つことで、項目が1つだけの状態と、空になった後に再び使う場合の両方を正しく扱えます。
キューにはcollections.dequeを使う
一般的なFIFO用途では、Pythonの collections.deque が実用的な既定の選択肢です。右端に追加し、popleft() で左端から取り出します。両端での操作は効率よく行えるよう設計されており、len() と真偽値チェックを使えば、残りのインターフェースも簡潔にできます。空のdequeに対して popleft() を呼び出すと IndexError が発生するため、このラッパーでは事前に空かどうかを確認し、ほかの例と同じ成功フラグ形式で結果を返します。
このセクションのコードと表示されるラベルや出力は英語のままです。
from collections import deque
class DequeQueue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.items:
return False, None
return True, self.items.popleft()
def is_empty(self):
return not self.items
def __len__(self):
return len(self.items)
queue = DequeQueue()
queue.enqueue("first")
queue.enqueue("second")
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
deque は collections モジュールが提供するクラスです。ここでは公開インターフェースを使い、内部表現についての推測には頼らないでください。容量の上限や、プロデューサースレッドとコンシューマースレッド間の連携が必要な場合は、代わりにPythonの queue モジュールにある専用のキュークラスを検討してください。
各実装を比較する
| 実装 | enqueue | dequeue | 長さ | 実用上のトレードオフ |
|---|---|---|---|---|
append() と pop(0) を使うリスト |
償却 O(1) | O(n) | O(1) | 小さく理解しやすい一方、先頭から取り出すと後続の項目が移動します。 |
| 単方向連結リスト | O(1) | O(1) | この例では O(n) | ポインターの仕組みを学べますが、ノードとポインターの管理が必要です。 |
collections.deque |
O(1) | O(1) | O(1) | 簡潔なFIFO操作が使える標準ライブラリの選択肢です。 |
連結リストの計算量は、キューが front と rear の両方を保持する場合のものです。項目数を記録していないため、長さを数えるには各ノードをたどる必要があります。別途カウンターを持てば長さを定数時間で取得できますが、その分、すべての操作で更新する不変条件が増えます。ほとんどのプログラムでは collections.deque を選びましょう。キューが小さい場合や先頭からの取り出しを繰り返さない場合はリストを使い、データ構造を学ぶ場合やノード単位の動作が特に役立つ場合は連結リストを実装してください。
