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 個の整数が与えられる。それらをバブルソートで昇順に並べ替えよ。
回答
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 を適切に管理し、操作を実行せよ。
回答
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 を使って回文かどうかを判定せよ。
回答
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 要素のウィンドウごとに最大値を求めよ。
回答
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 回右回転した後の配列を出力せよ。
回答
from collections import deque
N, K = map(int, input().split())
A = deque(map(int, input().split()))
A.rotate(K)
print(*A)
例題5. 双方向探索
問題: グラフが与えられ、最短経路を 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))