はじめに
dequeは「double-ended queue」の略で、両端からの追加・削除が高速なデータ構造です。リストでは先頭操作が遅いですが、deque なら O(1) で実行できます。
deque とは
from collections import deque
# リスト: 先頭追加は O(n) - 全要素をシフト
lst = [1, 2, 3]
lst.insert(0, 0) # 遅い
# deque: 先頭追加も O(1)
dq = deque([1, 2, 3])
dq.appendleft(0) # 速い
基本操作
作成
from collections import deque
# 空のdeque
dq = deque()
# リストから作成
dq = deque([1, 2, 3])
# 文字列から作成
dq = deque("abc")
print(list(dq)) # ['a', 'b', 'c']
# 最大長を指定（古い要素は自動削除）
dq = deque(maxlen=3)
要素の追加
dq = deque([2, 3, 4])
# 右端（末尾）に追加
dq.append(5)
print(dq) # deque([2, 3, 4, 5])
# 左端（先頭）に追加
dq.appendleft(1)
print(dq) # deque([1, 2, 3, 4, 5])
複数要素の追加
dq = deque([3, 4])
# 右端に複数追加
dq.extend([5, 6])
print(dq) # deque([3, 4, 5, 6])
# 左端に複数追加（逆順で追加される）
dq.extendleft([2, 1])
print(dq) # deque([1, 2, 3, 4, 5, 6])
要素の削除
dq = deque([1, 2, 3, 4, 5])
# 右端から削除
val = dq.pop()
print(val) # 5
print(dq) # deque([1, 2, 3, 4])
# 左端から削除
val = dq.popleft()
print(val) # 1
print(dq) # deque([2, 3, 4])
値による削除
dq = deque([1, 2, 3, 2, 4])
# 最初に見つかった値を削除
dq.remove(2)
print(dq) # deque([1, 3, 2, 4])
全削除
dq = deque([1, 2, 3])
dq.clear()
print(dq) # deque([])
回転操作
dq = deque([1, 2, 3, 4, 5])
# 右に回転（正の値）
dq.rotate(2)
print(dq) # deque([4, 5, 1, 2, 3])
# 左に回転（負の値）
dq.rotate(-2)
print(dq) # deque([1, 2, 3, 4, 5])
rotate(2) の動き:
[1, 2, 3, 4, 5]
↓
[4, 5, 1, 2, 3] ← 右端の2要素が左端に移動
インデックスアクセス
dq = deque([1, 2, 3, 4, 5])
# インデックスアクセス（O(n) なので注意）
print(dq[0]) # 1
print(dq[-1]) # 5
print(dq[2]) # 3
注意: deque のインデックスアクセスは O(n) です。頻繁にインデックスアクセスする場合はリストの方が適しています。
検索
dq = deque([1, 2, 3, 2, 4])
# 要素数をカウント
print(dq.count(2)) # 2
# インデックスを取得
print(dq.index(3)) # 2
# 存在確認
print(3 in dq) # True
反転とコピー
dq = deque([1, 2, 3])
# 反転（破壊的）
dq.reverse()
print(dq) # deque([3, 2, 1])
# コピー
dq2 = dq.copy()
print(dq2) # deque([3, 2, 1])
maxlen - 最大長の制限
# 最大3要素
dq = deque(maxlen=3)
dq.append(1)
dq.append(2)
dq.append(3)
print(dq) # deque([1, 2, 3], maxlen=3)
# 4つ目を追加すると最古（左端）が消える
dq.append(4)
print(dq) # deque([2, 3, 4], maxlen=3)
# 左端に追加すると右端が消える
dq.appendleft(0)
print(dq) # deque([0, 2, 3], maxlen=3)
list との比較
| 操作 | list | deque |
|---|---|---|
末尾追加 append
|
O(1) | O(1) |
| 先頭追加 | O(n) | O(1) |
末尾削除 pop()
|
O(1) | O(1) |
先頭削除 pop(0)
|
O(n) | O(1) |
| インデックスアクセス | O(1) | O(n) |
| スライス | ◎ | × |
ベンチマーク
from collections import deque
import time
n = 100000
# リストの先頭追加
lst = []
start = time.time()
for i in range(n):
lst.insert(0, i)
print(f"list: {time.time() - start:.3f}秒")
# dequeの先頭追加
dq = deque()
start = time.time()
for i in range(n):
dq.appendleft(i)
print(f"deque: {time.time() - start:.3f}秒")
# 結果例:
# list: 2.5秒
# deque: 0.01秒
実践例
キュー（FIFO）
from collections import deque
queue = deque()
# エンキュー（末尾に追加）
queue.append("タスク1")
queue.append("タスク2")
queue.append("タスク3")
# デキュー（先頭から取り出し）
while queue:
task = queue.popleft()
print(f"処理中: {task}")
# 処理中: タスク1
# 処理中: タスク2
# 処理中: タスク3
スタック（LIFO）
from collections import deque
stack = deque()
# プッシュ
stack.append("操作1")
stack.append("操作2")
stack.append("操作3")
# ポップ（最後に入れたものから取り出し）
while stack:
op = stack.pop()
print(f"取り消し: {op}")
# 取り消し: 操作3
# 取り消し: 操作2
# 取り消し: 操作1
履歴管理
from collections import deque
# 直近5件の履歴を保持
history = deque(maxlen=5)
pages = ["/home", "/about", "/products", "/contact", "/help", "/faq"]
for page in pages:
history.append(page)
print(f"訪問: {page}")
print(f" 履歴: {list(history)}")
# 最終的な履歴（古いものは自動削除）
print(f"履歴: {list(history)}")
# ['/about', '/products', '/contact', '/help', '/faq']
よくある間違い
1. インデックスアクセスの多用
from collections import deque
dq = deque(range(10000))
# NG: O(n) のインデックスアクセスを多用
for i in range(len(dq)):
_ = dq[i] # 遅い
# OK: イテレートする
for item in dq:
_ = item # 速い
2. スライスを使おうとする
dq = deque([1, 2, 3, 4, 5])
# NG: dequeはスライスをサポートしない
# dq[1:3] # TypeError
# OK: リストに変換してスライス
list(dq)[1:3] # [2, 3]
まとめ
| 操作 | メソッド | 計算量 |
|---|---|---|
| 右端追加 | append(x) |
O(1) |
| 左端追加 | appendleft(x) |
O(1) |
| 右端削除 | pop() |
O(1) |
| 左端削除 | popleft() |
O(1) |
| 回転 | rotate(n) |
O(k) |
| 最大長制限 | deque(maxlen=n) |
- |
次回は deque の実践的なパターンを学びます(仮)！