Pythonアルゴリズム

Pythonのキュー(queue)

このレッスンでは、collections.dequeを使って、先入れ先出しの効率的なキューを実装します。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

印刷ジョブ、サポートの問い合わせ、プログラム間のメッセージは、届いた順に処理しなければなりません。キューはその順番を保ち、Python で正しい道具を選べば、何百万件でも速く動きます。

身近なたとえ

キューはチケット売り場の行列のようなものです。新しい人は最後尾に並び、先頭の人から対応されます。誰も割り込まないので、全員が来た順に対応されます。

チケットの行列からコードへ
deque(["first", "second"])🚶🚶 すでに2人が待っている
queue.append("third")🚶 新しい人が最後尾に並ぶ
queue.popleft()🎫 先頭の人が対応される
list(queue)👀 まだ待っている人
先入れ先出し:来た順が対応する順です。
ひと言でいうと

キューは先入れ先出し(FIFO)のコレクションで、要素は最後尾に追加し、先頭から取り出します。

重要なポイント

  1. deque(["first", "second"]) はすでに2つの要素を持つキューを作ります。
  2. queue.append("third") は最後尾に要素を追加します。
  3. queue.popleft() は先頭の要素を取り出して返し、ここでは "first" です。
  4. deque は先頭からすばやく取り出せますが、リストでは残りの全要素をずらす必要があります。

どんな場面で使う?

  • タスクや要求を届いた順に処理する。
  • グラフや格子での幅優先探索。
  • メッセージやイベントなど、作る側と使う側の間のバッファー。

使わなくてよいとき

  • 最も新しい要素を先に出すべき場合:スタックを使います。
  • 要素に優先度がある場合:優先度付きキューには heapq を使います。
  • 複数のスレッドがキューを共有する場合:queue.Queue がロックを処理してくれます。

動きで理解する

enqueueとdequeueを試すと、要素が到着した順番どおりに出ていくことがわかります。

サンプルコード

コードを実行 →
main.py
from collections import deque

queue = deque(["first", "second"])
queue.append("third")

print("served:", queue.popleft())
print("waiting:", list(queue))
この例の実行ボタンを作成

実行結果

served: first
waiting: ['second', 'third']

コードの解説

dequeでは、append()で右側に要素を追加し、popleft()で左側から取り出せます。どちらもO(1)です。普通のリストで先頭の要素を削除すると、後ろの要素をすべて前に詰める必要があるためO(n)かかります。そのため、キューにはdequeのほうが適しています。

値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。

発展問題

下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。

  1. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

リストと pop(0) を使う

pop(0) は残りの全要素をずらすので、長いキューでは遅くなります。

問題
queue = ["first", "second"]
queue.pop(0)
修正
queue = deque(["first", "second"])
queue.popleft()

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ