[Python] deque

Deque (double ended qeque)

日本語では両端キューと訳され、先頭または末尾に対して追加(PUSH)、取り出し(POP)が行えるデータ構造を Deque といいます。

Python で使えるデータ構造

Python の標準ライブラリで提供されている deque クラスの使い方を紹介します。

左側に要素を追加する

appendleft(x) で左側に要素を追加できます。

>>> from collections import deque
>>> data = deque([5, 17, 22, 45])
>>> data
deque([5, 17, 22, 45])
>>> data.appendleft(12)
deque([12, 5, 17, 22, 45])

左側に複数の要素を追加する

extendleft(iterable) で左側に複数の要素を追加できます。
iterable の先頭から順番に追加されていくため、順序が逆になることに注意してください。

>>> from collections import deque
>>> data = deque([5, 17, 22, 45])
>>> data
deque([5, 17, 22, 45])
>>> data.extendleft([1, 2, 3])
>>> data
deque([3, 2, 1, 5, 17, 22, 45])

左側から要素を取り出す

popleft() で左側から要素を取り出し、返り値として返します。

>>> from collections import deque
>>> data = deque([12, 5, 17, 22, 45])
>>> data
deque([12, 5, 17, 22, 45])
>>> value = data.popleft()
>>> value
deque([5, 17, 22, 45])

左側の要素を確認する

インデックスは左側から 0, 1, … を指すようになっています。

>>> from collections import deque
>>> data = deque([12, 5, 17, 22, 45])
>>> data[0]
12
>>> data[1]
5

右側に要素を追加する

append(x) で右側に要素を追加できます。

>>> from collections import deque
>>> data = deque([5, 17, 22, 45])
>>> data
deque([5, 17, 22, 45])
>>> data.append(12)
>>> data
deque([5, 17, 22, 45, 12])

右側に複数の要素を追加する

extend(iterable) で右側に複数の要素を追加できます。

>>> from collections import deque
>>> data = deque([5, 17, 22, 45])
>>> data
deque([5, 17, 22, 45])
>>> data.extend([1, 2, 3])
>>> data
deque([5, 17, 22, 45, 1, 2, 3])

右側から要素を取り出す

pop(x) で右側から要素を取り出し、返り値として返します。

>>> from collections import deque
>>> data = deque([12, 5, 17, 22, 45])
>>> data
deque([12, 5, 17, 22, 45])
>>> value = data.pop()
>>> value
45
>>> data
deque([12, 5, 17, 22])

末尾の要素を確認する

インデックスは左側から 0, 1, … を指すようになっています。

>>> from collections import deque
>>> data = deque([12, 5, 17, 22, 45])
>>> data[-1]
45
>>> data[-2]
22

初期化する。

>>> from collections import deque
>>> data = deque([12, 5, 17, 22, 12])
>>> data
deque([12, 5, 17, 22, 12])
>>> data.clear()
>>> data
deque([])

ある値が存在する位置を調べる。

index(x[, start[, stop]]) で値 x が存在するインデックスを返します。
start, stop を指定すると start <= index < stop の範囲で検索します。 存在しない場合は、ValueError が発生します。

>>> from collections import deque
>>> data = deque([12, 5, 17, 22, 12])
>>> data.index(12, 1, 5)
4
>>> data.index(40)
ValueError: 40 is not in deque

値を挿入する。

insert(i, x) で値 x をインデックス i の前に挿入できます。

>>> from collections import deque
>>> data = deque([12, 5, 17, 22, 45])
>>> data.insert(1, 10)
>>> data
deque([12, 10, 5, 17, 22, 45])

値を削除する。

remove(value) で最初に見つかった値 value を削除します。
見つからない場合は、ValueError が発生します。

>>> from collections import deque
>>> data = deque([12, 5, 17, 22, 12])
>>> data.remove(12)
>>> data
deque([5, 17, 22, 45])

等しい要素の数を数える。

count(value) で value と等しい要素を数えます。

>>> from collections import deque
>>> data = deque([12, 5, 17, 22, 12])
>>> data.count(12)
2

要素数を調べる。

len() で要素数を取得できます。

>>> from collections import deque
>>> data = deque([12, 5, 17, 22, 12])
>>> len(data)
5

並びを反転させる。

reverse() で並びを反転させます。

>>> data = deque([12, 5, 17, 22, 45])
>>> data
deque([12, 5, 17, 22, 45])
>>> data.reverse()
>>> data
deque([45, 22, 17, 5, 12])

元の deque は変更せず、それを反転させた新たな deque を得たい場合は reversed() を使います。
返すのは逆順にアクセスしていく iterater なので、deque(iterable) を使い逆順の deque を作成します。

>>> data = deque([12, 5, 17, 22, 45])
>>> rev_iter = reversed(data)
>>> rev_iter
<_collections._deque_reverse_iterator object at 0x000001E2F8E50EF8>
>>> deque(rev_iter)
deque([45, 22, 17, 5, 12])

deque の長さを制限する。

deque([iterable[, maxlen]]) で maxlen を指定した場合、deque の長さが制限されます。
append()、leftappend()、extend()、leftextend() で要素を追加して maxlen より要素数が多くなった場合は追加した側と反対側の端にある要素が捨てられます。
insert(i, x) では、追加してあふれる場合は IndexError が発生して追加できません。

>>> data = deque([5, 17, 22, 45], 4)
>>> data.appendleft(12)
>>> data
# 左に追加して溢れたので、右端の 45 が捨てられた。
deque([12, 5, 17, 22], maxlen=4)

コメントを残す

メールアドレスが公開されることはありません。