女性向けエンジニアスクール
3秒でわかる
先に入れたものから先に取り出す、順番待ちの列そのままのデータ構造。届いた処理をためて順にさばく仕組みや、幅優先探索の土台になります。
30秒図解
もう少し詳しく
どういうものか
キューは、追加は末尾、取り出しは先頭から行うデータ構造です。最初に入れた要素が最初に出るので、先入れ先出し（FIFO）と呼ばれます。追加をエンキュー、取り出しをデキューと言います。レジの行列とまったく同じ振る舞いで、途中の要素を直接見たり抜いたりする操作は基本的に用意されていません。
なぜ必要か
処理が到着する速さと、処理をさばける速さは一致しません。注文が一度に300件届いても、メール送信は1秒に数件しか流せない、といった差はどこにでもあります。キューを間にはさむと、届いた順に貯めておいて、さばける速さで取り出せます。取りこぼしがなく、順序も保たれます。
幅優先探索でもキューが本体になります。今の階層のノードを全部キューに入れてから順に取り出すことで、近い場所から順に探索できます。
具体例
from collections import deque
queue = deque()
queue.append("注文A") # エンキュー
queue.append("注文B")
queue.append("注文C")
print(queue.popleft()) # 注文A 先に入れたものから出る
print(queue.popleft()) # 注文B
print(len(queue)) # 1
# 幅優先探索。近いノードから順に見る
def bfs(graph, start):
visited = {start}
order = []
q = deque([start])
while q:
node = q.popleft()
order.append(node)
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt)
q.append(nxt)
return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs(graph, "A")) # ['A', 'B', 'C', 'D']つまずきやすいところ
Python でリストをキュー代わりに使い、list.pop(0) で取り出す書き方をよく見かけます。これは先頭を抜くたびに残り全部を1つずつ前へずらすため、要素数に比例した時間がかかります。1万件を処理すると差がはっきり出ます。両端の出し入れが定数時間の collections.deque を使います。
もうひとつは、空のキューから取り出す場合の扱いです。popleft() は空だと IndexError になるので、while q のように残りがあるかを先に確かめるか、例外を受け止めます。
似た用語との違い
| 語 | 取り出す順 | 使いどころ |
|---|---|---|
| キュー | 先に入れたものから | 順番待ちの処理、幅優先探索 |
| スタック | 後に入れたものから | 関数呼び出し、戻る操作、深さ優先探索 |
| 優先度つきキュー | 優先度の高いものから | 最短経路、締切の近い仕事から処理 |
| デック | 両端どちらからでも | 上の3つの土台として使える |
覚え方
キューは行列、スタックは積んだ皿です。行列は前から、皿は上から取ります。
