Overview

キュー（Queue）は「先入れ先出し（FIFO: First In, First Out）」のデータ構造。
「最初に追加されたデータが最初に取り出される」という特徴があり、
タスクスケジューリング・BFS（幅優先探索）・データストリーム処理などでよく使われる。
1.キューの基本
 2.キューの応用
 3.典型問題を解いてみる

1. キューの基本

Pythonでは collections.deque を使うと高速にキューを扱うことができる。

操作名	説明	Python のリスト操作
エンキュー（enqueue）	キューに要素を追加	`queue.append(x)`
デキュー（dequeue）	キューの先頭の要素を取り出す	`queue.popleft()`
先頭（front）	キューの先頭要素を参照（削除しない）	`queue[0]`
空判定（is_empty）	キューが空かを判定	'len(queue) == 0'

＜基本実装＞

from collections import deque

queue = deque()

# エンキュー（追加）
queue.append(1)
queue.append(2)
queue.append(3)

# デキュー（取り出し）
print(queue.popleft())  # 1
print(queue.popleft())  # 2

# キューの状態確認
print(queue)  # deque([3])

2. キューの応用

BFS（幅優先探索）

BFS ではキューを使う

from collections import deque

graph = {
    1: [2, 3],
    2: [4, 5],
    3: [],
    4: [],
    5: []
}

def bfs(start):
    queue = deque([start])
    visited = set()

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            queue.extend(graph.get(node, []))  # 隣接ノードを追加

bfs(1)  # 出力: 1 2 3 4 5

ラウンドロビン・スケジューリング

タスクの処理時間が均等に割り当てられるラウンドロビン方式をキューで実装する。
CPUスケジューリングの基本モデル。

dfrom collections import deque

def round_robin(tasks, quantum):
    queue = deque(tasks)
    
    while queue:
        task, time = queue.popleft()
        if time > quantum:
            queue.append((task, time - quantum))  # 時間を減らして再度追加
        print(f"Processing {task}")

tasks = [("A", 5), ("B", 3), ("C", 8)]
round_robin(tasks, 3)

スライディングウィンドウ

データの連続した部分（ウィンドウ）を効率的に扱うにはキューが役立つ。
問題: N 個の数列 A から、各 K 個の連続部分の最大値を求めよ。

from collections import deque

def sliding_window_max(arr, k):
    dq = deque()
    res = []

    for i, num in enumerate(arr):
        while dq and arr[dq[-1]] < num:
            dq.pop()
        dq.append(i)

        if dq[0] == i - k:
            dq.popleft()

        if i >= k - 1:
            res.append(arr[dq[0]])

    return res

A = [1, 3, -1, -3, 5, 3, 6, 7]
K = 3
print(sliding_window_max(A, K))  # 出力: [3, 3, 5, 5, 6, 7]

3. 典型問題を解いてみる

例題1. キューの基本操作

問題: N 個の操作（ENQUEUE x / DEQUEUE）が与えられる。キューを適切に管理し、DEQUEUE の際に取り出した値を出力せよ。

参考： ABC321 B - Simple Queue

回答　

from collections import deque

N = int(input())
queue = deque()

for _ in range(N):
    cmd = input().split()
    if cmd[0] == "ENQUEUE":
        queue.append(int(cmd[1]))
    elif cmd[0] == "DEQUEUE" and queue:
        print(queue.popleft())

例題2. 幅優先探索（BFS）

問題: グラフが与えられ、最短経路を BFS で求めよ。

参考： ABC319 C - Shortest Path with BFS

回答　

from collections import deque

N, M = map(int, input().split())
graph = {i: [] for i in range(1, N+1)}

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def bfs(start):
    queue = deque([start])
    visited = {start: 0}

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited[neighbor] = visited[node] + 1
                queue.append(neighbor)

    return visited

distances = bfs(1)
print(distances)

例題3. ラウンドロビンスケジューリング

問題: N 個のプロセスが Q 時間ごとに実行される。各プロセスの終了時刻を求めよ。

参考： ABC318 B - Round Robin Scheduling

回答　

from collections import deque

N, Q = map(int, input().split())
tasks = deque((i, int(input())) for i in range(N))

time = 0
while tasks:
    i, t = tasks.popleft()
    if t > Q:
        time += Q
        tasks.append((i, t - Q))
    else:
        time += t
        print(f"Process {i} finished at {time}")