Pythonのdequeでキュー・スタック・両端キューを効率的に扱う方法
Pythonのcollectionsモジュールのdeque（デック）は、両端での高速な追加・削除が可能なデータ構造です。キュー、スタック、両端キューとして活用でき、リストよりも効率的な操作を実現できます。
dequeとは
deque（double-ended queue）は、両端で要素の追加・削除がO(1)で実行できるデータ構造です。通常のリストでは先頭への挿入がO(n)ですが、dequeなら高速に処理できます。
from collections import deque
# dequeの作成
dq = deque([1, 2, 3])
print(dq) # deque([1, 2, 3])
キューとしての使用
FIFOでの要素処理を効率的に実装：
from collections import deque
# キューの実装
queue = deque()
# 要素の追加（enqueue）
queue.append('A')
queue.append('B')
queue.append('C')
print(queue) # deque(['A', 'B', 'C'])
# 要素の取り出し（dequeue）
item = queue.popleft()
print(item) # A
print(queue) # deque(['B', 'C'])
スタックとしての使用
LIFOでの要素処理：
from collections import deque
# スタックの実装
stack = deque()
# 要素のプッシュ
stack.append('X')
stack.append('Y')
stack.append('Z')
print(stack) # deque(['X', 'Y', 'Z'])
# 要素のポップ
item = stack.pop()
print(item) # Z
print(stack) # deque(['X', 'Y'])
両端キューとしての使用
両端での操作を活用：
from collections import deque
# 両端キューの実装
dq = deque(['B', 'C'])
# 左端に追加
dq.appendleft('A')
print(dq) # deque(['A', 'B', 'C'])
# 右端に追加
dq.append('D')
print(dq) # deque(['A', 'B', 'C', 'D'])
# 左端から削除
left_item = dq.popleft()
print(left_item) # A
# 右端から削除
right_item = dq.pop()
print(right_item) # D
print(dq) # deque(['B', 'C'])
便利なメソッド
rotate（回転）
from collections import deque
dq = deque([1, 2, 3, 4, 5])
# 右に2つ回転
dq.rotate(2)
print(dq) # deque([4, 5, 1, 2, 3])
# 左に1つ回転
dq.rotate(-1)
print(dq) # deque([5, 1, 2, 3, 4])
extend（複数要素の追加）
from collections import deque
dq = deque([1, 2])
# 右端に複数要素追加
dq.extend([3, 4, 5])
print(dq) # deque([1, 2, 3, 4, 5])
# 左端に複数要素追加
dq.extendleft(['A', 'B'])
print(dq) # deque(['B', 'A', 1, 2, 3, 4, 5])
maxlenによる固定長deque
循環バッファとして使用：
from collections import deque
# 最大3要素のdeque
circular = deque(maxlen=3)
# 要素を追加
for i in range(5):
circular.append(i)
print(f"追加後: {circular}")
# 出力:
# 追加後: deque([0], maxlen=3)
# 追加後: deque([0, 1], maxlen=3)
# 追加後: deque([0, 1, 2], maxlen=3)
# 追加後: deque([1, 2, 3], maxlen=3)
# 追加後: deque([2, 3, 4], maxlen=3)
実践的な活用例
BFS（幅優先探索）
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
print(node)
queue.extend(graph[node] - visited)
# 使用例
graph = {
'A': {'B', 'C'},
'B': {'A', 'D'},
'C': {'A', 'E'},
'D': {'B'},
'E': {'C'}
}
bfs(graph, 'A')
履歴管理
from collections import deque
class History:
def __init__(self, maxlen=10):
self.history = deque(maxlen=maxlen)
def add(self, item):
self.history.append(item)
def recent(self, n=5):
return list(self.history)[-n:]
def undo(self):
return self.history.pop() if self.history else None
# 使用例
hist = History(maxlen=3)
hist.add("action1")
hist.add("action2")
hist.add("action3")
print(hist.recent()) # ['action1', 'action2', 'action3']
滑動窓の実装
from collections import deque
def sliding_window_max(nums, k):
dq = deque()
result = []
for i, num in enumerate(nums):
# 窓から出る要素を削除
while dq and dq[0] <= i - k:
dq.popleft()
# 現在の要素より小さい要素を削除
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
# 使用例
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3)) # [3, 3, 5, 5, 6, 7]
パフォーマンス比較
listとdequeの性能差：
import time
from collections import deque
# リストでの先頭挿入
def list_insert_test(n):
lst = []
start = time.time()
for i in range(n):
lst.insert(0, i)
return time.time() - start
# dequeでの先頭挿入
def deque_insert_test(n):
dq = deque()
start = time.time()
for i in range(n):
dq.appendleft(i)
return time.time() - start
n = 10000
list_time = list_insert_test(n)
deque_time = deque_insert_test(n)
print(f"リスト: {list_time:.4f}秒")
print(f"deque: {deque_time:.4f}秒")
まとめ
dequeは両端での高速操作が必要な場面で威力を発揮するデータ構造です。キュー、スタック、循環バッファとして活用でき、アルゴリズムの効率化に大きく貢献します。
特にBFSや滑動窓アルゴリズム、履歴管理などの実装では、listよりもdequeを選択することで大幅なパフォーマンス向上が期待できます。
■プロンプトだけでオリジナルアプリを開発・公開してみた！！
■AI時代の第一歩！「AI駆動開発コース」はじめました！
テックジム東京本校で先行開始。
■テックジム東京本校
「武田塾」のプログラミング版といえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
より早く、より安く、しかも対面型のプログラミングスクールです。
＜短期講習＞5日で5万円の「Pythonミニキャンプ」開催中。
＜月1開催＞放送作家による映像ディレクター養成講座
＜オンライン無料＞ゼロから始めるPython爆速講座
