【Pyhton】スタックやキューのように扱えるdeque(デック)の使い方

この記事では、スタックやキューのように扱えるdeque(デック)の使い方を解説します。

それでは、dequeの使い方を見ていきましょう！

dequeの初期化

dequeはcllectionsモジュールをインポートすることで使用可能です。

from collections import deque

dequeの書式は以下の通りです。

deque([iterable[, maxlen]])

試しに空のdequeを生成してみます。

from collections import deque

d = deque()
print(d)  # deque([])

iterable引数を指定することで初期値を渡すことができる。

from collections import deque

d = deque([1, 2, 3])
print(d)  # deque([1, 2, 3])

maxlen引数を指定することで最大サイズを設定できる。指定されなかったりNoneだった場合は任意のサイズまで大きくなる。

from collections import deque

d = deque([1, 2, 3], 2)
print(d)  # deque([2, 3], maxlen=2)

サイズを制限したdequeの要素が最大の時、新しい要素を追加すると追加した要素数分だけ反対側から要素が捨てられるので注意してください。

dequeに要素を追加する方法

右側に追加する

dequeの右側から要素を追加するには以下のようなメソッドを使います。

append(x)

xをdequeの右側に追加します。

from collections import deque

d = deque()
print(d)  # deque([])

d.append(1)
print(d)  # deque([1])

d.append(3.14)
print(d)  # deque([1, 3.14])

d.append('abc')
print(d)  # deque([1, 3.14, 'abc'])

extend(iterable)

iterableの要素を右側に追加する。

from collections import deque

d = deque()
print(d)  # deque([])

d.extend([1, 2])
print(d)  # deque([1, 2])

d.extend(('a', 'b'))
print(d)  # deque([1, 2, 'a', 'b'])

左側に追加する

dequeの左側から要素を追加するには以下のようなメソッドを使います。

appendleft(x)

xをdequeの右側に追加します。

from collections import deque

d = deque()
print(d)  # deque([])

d.appendleft(1)
print(d)  # deque([1])

d.appendleft(3.14)
print(d)  # deque([3.14, 1])

d.appendleft('abc')
print(d)  # deque(['abc', 3.14, 1])

extendleft(iterable)

iterableの要素を左側に追加する。iterableの要素自体も逆順で追加されることに注意してください。

from collections import deque

d = deque()
print(d)  # deque([])

d.extendleft([1, 2])
print(d)  # deque([2, 1])

d.extendleft(('a', 'b'))
print(d)  # deque(['b', 'a', 2, 1])

任意の場所に挿入する

インデックスを指定して要素を追加することもできます。

insert(i, x)

iの位置にxを挿入します。制限されていたサイズを挿入によって超えてしまうとIndexErrorが発生するので注意してください。
※ Python 3.5で追加。

from collections import deque

d = deque([1, 2, 3], 4)
print(d)  # deque([1, 2, 3], maxlen=4)

d.insert(1, 9)
print(d)  # deque([1, 9, 2, 3], maxlen=4)

d.insert(2, 10)
print(d)  # IndexError: deque already at its maximum size

dequeの要素を取り出す方法

pop()で右側から、popleft()で左側から要素を1つ取り出します。

from collections import deque

d = deque([1, 2, 3, 4, 5])
print(d)  # deque([1, 2, 3, 4, 5])

r = d.pop()
print(r, d)  # 5 deque([1, 2, 3, 4])

l = d.popleft()
print(l, d)  # 1 deque([2, 3, 4])

要素が存在しない場合は、どちらのメソッドもIndexErrorを発生させます。

dequeの要素を削除する方法

任意の要素を削除する

任意の値を指定して要素を削除できます。

remove(value)

最初に見つけたvalueを削除します。valueが見つからない場合はValueErrorが送出されます。

from collections import deque

d = deque([1, 2, 3, 2, 1])
print(d)  # deque([1, 2, 3, 2, 1])

d.remove(1)
print(d)  # deque([2, 3, 2, 1])

d.remove(2)
print(d)  # deque([3, 2, 1])

全ての要素を削除する

clear()

dequeの要素を全て削除します。

from collections import deque

d = deque([1, 2, 3, 2, 1])
print(d)  # deque([1, 2, 3, 2, 1])

d.clear()
print(d)  # deque([])

dequeの要素を検索する方法

任意の要素を格納しているかどうか

dequeはin演算子をサポートしています。

from collections import deque

d = deque([1, 2, 3])

num = 2
 
if num in d:
    print(f"{num}を格納している")

実行結果

2を格納している

任意の要素の数

count(x)

deque内にあるxと等しい要素の数を返します。
※ Python 3.2で追加。

from collections import deque

d = deque([1, 2, 3, 2, 1])
print(d)  # deque([1, 2, 3, 2, 1])

c = d.count(1)
print(c)  # 2

c = d.count(2)
print(c)  # 2

c = d.count(3)
print(c)  # 1

c = d.count(4)
print(c)  # 0

任意の要素の位置

index(x[, start[, stop]])

deque内にある最初に見つけたxのインデックスを返します。startとstopで検索範囲を指定できます。xが見つからない場合はValueErrorを発生させます。
※ Python 3.5で追加。

from collections import deque

d = deque([1, 2, 3, 1, 2, 3])
print(d)  # deque([1, 2, 3, 1, 2, 3])

index = d.index(1)
print(index)  # 0

# startを指定
index = d.index(1, 2)
print(index)  # 3

dequeの要素を並び替える方法

要素を逆順にする

reverse()

deque内の要素を逆順にします。
※ Python 3.2で追加。

from collections import deque

d = deque([1, 2, 3])
print(d)  # deque([1, 2, 3])

d.reverse()
print(d)  # deque([3, 2, 1])

要素を回す

rotate(n=1)

deque内の要素をnの数だけ右周りでずらします。負の値が指定された場合、左周りで要素をずらします。

from collections import deque

d = deque([1, 2, 3])
print(d)  # deque([1, 2, 3])

d.rotate(1)
print(d)  # deque([3, 1, 2])

d.rotate(-1)
print(d)  # deque([1, 2, 3])

dequeをコピーする方法

dequeは浅いコピーと深いコピーのどちらもサポートしています。

浅い (shallow) コピーと深い (deep) コピーの違いが関係するのは、複合オブジェクト (リストやクラスインスタンスのような他のオブジェクトを含むオブジェクト) だけです:
浅いコピー (shallow copy) は新たな複合オブジェクトを作成し、その後 (可能な限り) 元のオブジェクト中に見つかったオブジェクトに対する 参照 を挿入します。
深いコピー (deep copy) は新たな複合オブジェクトを作成し、その後元のオブジェクト中に見つかったオブジェクトの コピー を挿入します。

引用先: copy --- 浅いコピーおよび深いコピー操作 — Python 3.11.1 ドキュメント

浅いコピー

copy()

dequeの浅いコピーを作成します。
※ Python 3.5で追加。

from collections import deque

d = deque([1, 2, 3])
print(d)  # deque([1, 2, 3])

c = d.copy()
print(c)  # deque([1, 2, 3])

copyモジュールのcopy()関数もサポートしています。

深いコピー

深いコピーを生成するにはcopyモジュールのdeepcopy()関数を使います。

from collections import deque
import copy

d = deque([1, 2, 3])
print(d)  # deque([1, 2, 3])

c = copy.deepcopy(d)
print(c)  # deque([1, 2, 3])

dequeの演算

dequeは、足し算(__add__())、掛け算(__mul__())などをサポートしています。
※ Python 3.5から追加。

from collections import deque

d1 = deque([1, 2, 3])
d2 = deque(['a', 'b'])

print(d1 + d2)  # deque([1, 2, 3, 'a', 'b'])
print(d1 * 2)   # deque([1, 2, 3, 1, 2, 3])

まとめ

この記事では、dequeの使い方についてまとめました。

スタックやキューが必要な時は両端の要素を高速で扱えるdeque(デック)を使いましょう。ただし、要素を両端以外から取得する場合はリストよりも遅いので素直にリストを使ってください。

また、複数のスレッド間で情報を安全に交換できるQueueも用意されています。

LinkQueue(キュー)の種類と使い方

それでは今回の内容はここまでです。ではまたどこかで〜( ・∀・)ﾉ