キュー

キュー#

キュー（Queue） はデータの中で最初に入ったものが最初に取り出される、 先入れ先出し（First In First Out: FIFO） のデータ構造

キューの末尾に要素を追加することを エンキュー（enqueue） といい、
キューの先頭から要素を取り出すことを デキュー（dequeue） という。

実装例#

Pythonでは、シンプルなキューとして collections パッケージのdequeが存在する。

また queueパッケージのQueueというクラスも存在する。

collections.dequeue はスレッドセーフではなく、 queue.Queue はスレッドセーフなのが主な違い

from collections import deque

q = deque()
q.append("A")
q.append("B")

print(q.popleft())  # A
print(q.popleft())  # B

A
B

from queue import Queue

q = Queue()
q.put("A")
q.put("B")

print(q.get())
print(q.get())

A
B

計算量#

キューは内部的に連結リスト（または双方向キュー）で実装されるため、先頭・末尾へのアクセスがO(1)になる。

操作	計算量	説明
`enqueue`	\(O(1)\)	末尾への追加
`dequeue`	\(O(1)\)	先頭からの取り出し
peek（先頭参照）	\(O(1)\)	先頭要素の参照（取り出しなし）
`is_empty`	\(O(1)\)	空かどうかの確認
サイズ取得	\(O(1)\)	要素数の取得
探索	\(O(n)\)	特定の要素を見つけるには全走査が必要

Pythonの queue.Queue は内部で collections.deque を使用しており、enqueue・dequeueともに償却 \(O(1)\)。

利用例#

例1: タスクの順番処理#

受け付けた順にタスクを処理する。新しいタスクは末尾に追加し、処理は先頭から行う。

from collections import deque

queue = deque()

# タスクを受け付ける
for task in ["タスクA", "タスクB", "タスクC"]:
    queue.append(task)

# 受け付けた順に処理
while queue:
    task = queue.popleft()
    print(f"処理中: {task}")

処理中: タスクA
処理中: タスクB
処理中: タスクC

例2: 最短ステップ数（BFS）#

スタート地点からゴールまで何ステップで到達できるか求める。
1ステップで +1 か +2 だけ進める場合に、位置 0 から位置 n まで最短何ステップかかるか。

from collections import deque

def min_steps(goal):
    queue = deque([(0, 0)])  # (現在地, ステップ数)
    visited = {0}

    while queue:
        pos, steps = queue.popleft()
        if pos == goal:
            return steps
        for next_pos in [pos + 1, pos + 2]:
            if next_pos <= goal and next_pos not in visited:
                visited.add(next_pos)
                queue.append((next_pos, steps + 1))

print(min_steps(5))   # 3  (0→2→4→5)
print(min_steps(10))  # 5  (0→2→4→6→8→10)

3
5

キュー

Contents