Overview

Deque（両端キュー: Double-Ended Queue）は、前後の両方で要素の追加・削除が可能なデータ構造。
1.Dequeの基本
 2.Dequeの応用
 3.典型問題を解いてみる

1. Dequeの基本

キューやスタックの機能を統合しており、データの処理を柔軟に行うことができる。
Pythonではcollections.dequeを使うと、高速な両端キューの操作が可能。

操作名	説明	Pythonの`deque`操作
前に追加（appendleft）	左端に要素を追加	`deque.appendleft(x)`
後ろに追加（append）	右端に要素を追加	`deque.append(x)`
前から削除（popleft）	左端の要素を削除	`deque.popleft()`
後ろから削除（pop）	右端の要素を削除	`deque.pop()`
長さ取得（len）	Deque の長さを取得	`len(deque)`
回転（rotate）	要素を右（+n）または左（-n）へシフト	`deque.rotate(n)`

＜基本実装＞

from collections import deque

dq = deque()

# 右端に追加
dq.append(1)
dq.append(2)

# 左端に追加
dq.appendleft(3)

# 右端と左端の要素を削除
print(dq.pop())      # 2
print(dq.popleft())  # 3

# Deque の状態
print(dq)  # deque([1])

ポイント:
・スタックやキューとしても使える
・appendleft と popleft を使うと左端でも操作できる

2. Dequeの応用

(1) スライディングウィンドウの最小・最大

Deque を使うと、スライディングウィンドウの最大値や最小値を $𝑂(𝑁)$で求めることができます。

例：N 個の整数から、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]

ポイント:
・単調デック（Monotonic Deque）を使い $𝑂(𝑁)$で解ける
・Deque を用いることで効率的に要素を管理

(2) 回転（rotate）

Deque はリストの回転を効率的に行える。

dq = deque([1, 2, 3, 4, 5])
dq.rotate(2)  # 右に2回回転
print(dq)  # deque([4, 5, 1, 2, 3])

ポイント:
・通常のリストの insert() を使うより速い。

(3) 文字列の回文判定

Dequeを使うと前後から比較しながら文字列の回文判定ができる。

def is_palindrome(s):
    dq = deque(s)
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return False
    return True

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False

ポイント:
・前後の文字を効率的に比較
・リストよりも削除が速い

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

例題1. バブルソートの基本実装

問題: N 個の整数が与えられる。それらをバブルソートで昇順に並べ替えよ。

参考： ABC333 B - Basic Bubble Sort

回答　

N = int(input())
A = list(map(int, input().split()))

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(*bubble_sort(A))

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

問題: N 個の操作（APPEND x / APPENDLEFT x / POP / POPLEFT）が与えられる。Deque を適切に管理し、操作を実行せよ。

参考： ABC321 B - Simple Deque

回答　

from collections import deque

N = int(input())
dq = deque()

for _ in range(N):
    cmd = input().split()
    if cmd[0] == "APPEND":
        dq.append(int(cmd[1]))
    elif cmd[0] == "APPENDLEFT":
        dq.appendleft(int(cmd[1]))
    elif cmd[0] == "POP" and dq:
        dq.pop()
    elif cmd[0] == "POPLEFT" and dq:
        dq.popleft()

print(*dq)

例題2. 回文判定

問題: 文字列 S が与えられる。Deque を使って回文かどうかを判定せよ。

参考： ABC319 C - Palindrome Check

回答　

from collections import deque

def is_palindrome(s):
    dq = deque(s)
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return "No"
    return "Yes"

S = input()
print(is_palindrome(S))

例題3. Deque を使ったスライディングウィンドウ最大値

問題: N 個の数列 A が与えられ、各 K 要素のウィンドウごとに最大値を求めよ。

参考： ABC318 B - Sliding Window Maximum

回答　

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
print(*sliding_window_max(A, K))

例題4. Deque を使った回転操作

問題: N 個の整数が与えられる。それを K 回右回転した後の配列を出力せよ。

参考： ABC322 C - Rotate List

回答　

from collections import deque

N, K = map(int, input().split())
A = deque(map(int, input().split()))

A.rotate(K)
print(*A)

例題5. 双方向探索

問題: グラフが与えられ、最短経路を BFS（幅優先探索）で求めよ。

参考： ABC320 B - Bidirectional BFS

回答　

from collections import deque

def bfs(start, graph):
    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

# 入力処理
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)

print(bfs(1, graph))