Pythonの標準ライブラリには便利なデータ構造が数多く含まれていますが、その中でもcollectionsモジュールのdeque（デック）は知っておくと非常に役立つツールです。リストのように使えながら、両端での操作が高速に行えるため、特にキューやスタックとしての使用に最適です。
今回は、そんなdequeの基本的な使い方から、役立つメソッドや応用的な利用方法まで、実際のコードを交えながら紹介します！
基本的なdeque使い方
まず、dequeを使用するためには、collectionsモジュールからインポートする必要があります。例えば、リストのように使いながら両端での追加・削除が可能です。
from collections import deque
# 初期化
dq = deque([1, 2, 3])
print(dq) # deque([1, 2, 3])
# 要素の追加
dq.append(4) # 右端に追加
dq.appendleft(0) # 左端に追加
print(dq) # deque([0, 1, 2, 3, 4])
# 要素の削除
dq.pop() # 右端の要素を削除
dq.popleft() # 左端の要素を削除
print(dq) # deque([1, 2, 3])
dequeの便利メソッド
dequeには、リストと同じようなメソッドも多くありますが、両端の操作に特化した便利なメソッドが備わっています。
append(x)：右端に要素xを追加します。appendleft(x)：左端に要素xを追加します。pop()：右端の要素を削除して返します。popleft()：左端の要素を削除して返します。clear()：全ての要素を削除します。extend(iterable)：右端にイテラブルの要素を追加します。extendleft(iterable)：左端にイテラブルの要素を逆順で追加します。rotate(n)：n回右に回転させます（nが負なら左に回転）。「回転」というのはすべて右or左にズラすという意味です。右端、左端の値は反対側に移動します。
実例
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メソッドを使えば、リストの要素を回転させることができるので、順序を変える必要がある場面で重宝します。
dequeの応用例
キューとしての利用
dequeは、FIFO（先入れ先出し）キューとして利用するのに適しています。appendで右端に追加し、popleftで左端から要素を取り出すことで、効率的なキュー操作が可能です。
queue = deque()
# キューに要素を追加
queue.append("A")
queue.append("B")
queue.append("C")
# キューから要素を取り出し
print(queue.popleft()) # "A"
print(queue.popleft()) # "B"
print(queue.popleft()) # "C"
スタックとしての利用
逆に、LIFO（後入れ先出し）スタックとしても利用できます。この場合、appendで右端に追加し、popで右端から要素を取り出すようにします。
なお、スタックはappendとpopしか使っていないため、通常のlistでも簡単に実装できます。
(LIFOの使い道や他の実装方法についてはこちら)
stack = deque()
# スタックに要素を追加
stack.append("A")
stack.append("B")
stack.append("C")
# スタックから要素を取り出し
print(stack.pop()) # "C"
print(stack.pop()) # "B"
print(stack.pop()) # "A"
制限付きサイズのdeque（バッファとしての利用）
dequeには最大長を指定することが可能で、これにより古いデータを自動で削除しながら新しいデータを追加する「リングバッファ」として利用することができます。例えば、常に最新のデータだけを保持したい場合に便利です。
# 長さが3の固定サイズのdeque
dq = deque(maxlen=3)
dq.append(1)
dq.append(2)
dq.append(3)
print(dq) # deque([1, 2, 3], maxlen=3)
# 新しい要素を追加すると古い要素が自動で削除
dq.append(4)
print(dq) # deque([2, 3, 4], maxlen=3)
最近使った要素の追跡（簡易LRUキャッシュ）
dequeの最大長を設定することで、LRU（Least Recently Used）キャッシュを簡単に実装することも可能です。以下は、簡単なLRUキャッシュのコード例です。
def access_page(cache, page):
if page in cache:
cache.remove(page) # 既存ページは一度削除して最新位置に追加
elif len(cache) == cache.maxlen:
cache.popleft() # 古い要素を削除
cache.append(page)
# 長さが3のLRUキャッシュ
lru_cache = deque(maxlen=3)
access_page(lru_cache, 'A')
access_page(lru_cache, 'B')
access_page(lru_cache, 'C')
print(lru_cache) # deque(['A', 'B', 'C'], maxlen=3)
access_page(lru_cache, 'D')
print(lru_cache) # deque(['B', 'C', 'D'], maxlen=3)
access_page(lru_cache, 'C')
print(lru_cache) # deque(['B', 'D', 'C'], maxlen=3)
このように、固定サイズのdequeを用いることで、最近使われたページやデータを管理するキャッシュシステムもシンプルに作ることができます。
スライディングウィンドウの計算にも便利
例えば、スライディングウィンドウの最大値を求めるアルゴリズムなど、ウィンドウサイズが一定のデータ構造で効率的に計算を行いたい場合にもdequeが活躍します。
以下は、ウィンドウサイズ3で配列のスライディングウィンドウ最大値を求めるコード例です。
from collections import deque
def sliding_window_max(nums, k):
dq = deque() # ウィンドウ内のインデックスを保持するdeque
result = []
for i, num in enumerate(nums):
# ウィンドウ外の要素を削除
if dq and dq[0] < i - k + 1:
dq.popleft()
# デックの右端から、現在の値より小さい要素を削除
while dq and nums[dq[-1]] < num:
dq.pop()
# 現在のインデックスを追加
dq.append(i)
# ウィンドウがkのサイズに達したら、最大値を追加
if i >= k - 1:
result.append(nums[dq[0]])
return result
# 使用例
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(sliding_window_max(nums, k)) # [3, 3, 5, 5, 6, 7]
このコードでは、dequeを使ってスライディングウィンドウ内の最大値を効率よく計算しています。リストで同様の操作を行うと時間がかかりますが、dequeなら必要な操作を最小限に抑えられるため、パフォーマンスが向上します。
dequeの最大長を固定したうえでmaxを使用する方法の方がシンプルですが、計算効率はあまり高くありません。
詳しくはこちらの記事にて解説しております。
まとめ
collections.dequeは、リストに似た機能を持ちつつ、両端の操作に強みを持ったデータ構造です。キューやスタック、固定サイズバッファ、LRUキャッシュ、スライディングウィンドウなど、さまざまな場面で応用できるため、ぜひ使いこなしてみてください！
使い方を工夫することで、データの取り扱いが格段に効率的になりますよ！
