Overview
Deque（両端キュー: Double-Ended Queue） は、「前後どちらからも高速に追加・削除できる」データ構造。
1.Dequeの基本
2.listとdequeの性能比較
3.Dequeの内部構造
4.Dequeの応用
5.典型問題を解いてみる
1. Dequeの基本
Pythonではcollections.dequeを使うと、高速な両端キューの操作が可能。
| 操作名 | 説明 | Pythonのdeque操作 |
計算量 |
|---|---|---|---|
| 右端に追加 | push back | append(x) |
O(1) |
| 左端に追加 | push front | appendleft(x) |
O(1) |
| 右端から削除 | pop back | pop() |
O(1) |
| 左端から削除 | pop front | popleft() |
O(1) |
| 要素数取得 | len(dq) |
O(1) | |
| 回転 | 右にn、左に-n | rotate(n) |
O(1) |
＜基本実装＞
from collections import deque
dq = deque()
dq.append(1) # 右端に追加
dq.appendleft(2) # 左端に追加
dq.pop() # 右端から削除
dq.popleft() # 左端から削除
2. listとdequeの性能比較
| 操作 | list | deque | どちらを使うべき？ |
|---|---|---|---|
| 末尾 append/pop | O(1) | O(1) | どちらでもOK |
| 先頭 append/pop | O(N) | O(1) | Deque 一択 |
| ランダムアクセス | O(1) | O(N) | list |
| 回転（rotate） | O(N) | O(1) | deque |
➡ 先頭の操作がある場合、list は使ってはいけない。deque が圧倒的に高速。
3. Dequeの内部構造
Python のdequeはブロックを繋いだ両端リンク構造（リングバッファ）を持つ。
- 先頭・末尾は常に$O(1)$で増減
- 再配置コストが小さい
-
appendleft/popleftが高速
➡ 「キュー」「スタック」「両端操作」「BFS」が超高速で動く理由がこれ。
4. Dequeの応用
(1) BFS（幅優先探索）
Deque は BFS と非常に相性が良く、競プロでは定番の組み合わせ。
from collections import deque
def bfs(start, graph): # graph は {node: [neighbors]} の形式を想定
dist = {start: 0}
dq = deque([start])
while dq:
v = dq.popleft()
for nv in graph[v]:
if nv not in dist:
dist[nv] = dist[v] + 1
dq.append(nv)
return dist
(2) スライディングウィンドウの最大値
ウィンドウの最大値を O(N) で求められる強力テクニック。
from collections import deque
def sliding_window_max(arr, k):
dq = deque()
res = []
for i, x in enumerate(arr):
while dq and arr[dq[-1]] < x:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
res.append(arr[dq[0]])
return res
(3) 回文判定
前後の操作が高速なため、回文判定のような対称性チェックに最適。
def is_palindrome(s):
dq = deque(s)
while len(dq) > 1:
if dq.popleft() != dq.pop():
return False
return True
(4) 0-1 BFS（最短経路）
重みが 0 or 1 のグラフで最短経路を求める最速アルゴリズム。
from collections import deque
def zero_one_bfs(graph, start):
INF = 10**18
N = len(graph)
dist = [INF] * N
dist[start] = 0
dq = deque([start])
while dq:
v = dq.popleft()
for nv, w in graph[v]: # w は 0 or 1
if dist[nv] > dist[v] + w:
dist[nv] = dist[v] + w
if w == 0:
dq.appendleft(nv)
else:
dq.append(nv)
return dist
5. 典型問題を解いてみる
例題1. 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"
print(is_palindrome(input()))
例題3. スライディングウィンドウ最大値
問題: N 個の数列 A が与えられ、各 K 要素のウィンドウごとに最大値を求めよ。
回答
from collections import deque
def sliding_window_max(arr, k):
dq = deque()
res = []
for i, x in enumerate(arr):
while dq and arr[dq[-1]] < x:
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. 0-1 BFS（最短経路）
回答
from collections import deque
def zero_one_bfs(graph, start):
INF = 10**18
N = len(graph)
dist = [INF] * N
dist[start] = 0
dq = deque([start])
while dq:
v = dq.popleft()
for nv, w in graph[v]: # w は 0 or 1
if dist[nv] > dist[v] + w:
dist[nv] = dist[v] + w
if w == 0:
dq.appendleft(nv)
else:
dq.append(nv)
return dist