dequeの使い方【Python】 - ebisukeプログラミング初心者脱出黙示録

Pythonの標準ライブラリcollectionsのdeque型による両端キューの使い方を記事にしていきます。

深さ優先探索や幅優先探索など様々な場面で活用できるので、しっかり覚えたいですね。

dequeの特徴

リストとdeque比較した場合、操作する要素の位置によって速度に大きな違いが出てきます。

リストの場合

先頭の要素を取り出すpop(0)や、先頭に要素を追加するinsert(0,x)でO(n)のコストが必要になります。

dequeの場合

先頭と末尾の要素の追加や削除を行うappend()、appendleft()、pop()、popleftがO(1)のコストで実行できます。

一方で中央部分ではO(n)と遅くなります。

したがって普段はリストを使用すればよいですが、幅優先探索などアクセスが両端のみの場合にdequeを使用することで高速に処理することができます。

dequeの使い方

dequeオブジェクトの作成

from collections import deque

que = deque()

print(type(que))

# <class 'collections.deque'>

deque()でdequeオブジェクトが作成できます。

両端への要素の追加

from collections import deque

que = deque()

que.append(1)
que.append(2)
que.append(3)

que.appendleft(4)
que.appendleft(5)
que.appendleft(6)


print(que)

# deque([6, 5, 4, 1, 2, 3])

append()で末尾へ、appendleft()で先頭へ要素を追加できます。

両端の要素の削除

from collections import deque

que = deque([1, 2, 3, 4, 5])

print(que.pop())

# 5

print(que)

# deque([1, 2, 3, 4])

print(que.popleft())

# 1

print(que)

# deque([2, 3, 4])

pop()で末尾の要素を取り出し、popleft()で先頭の要素を取り出すことができます。

そのほかの要素追加方法[extend / extendleft]

from collections import deque

que = deque([1, 2, 3, 4, 5])

que.extend([6, 7])

print(que)

# deque([1, 2, 3, 4, 5, 6, 7])

que.extendleft([8, 9])

print(que)

# deque([9, 8, 1, 2, 3, 4, 5, 6, 7])

複数の要素を追加するときはextend/leftを使用します。

extend()で末尾に、extendleft()で先頭に要素を追加します。

extendleftでは追加される順番に注意が必要です。

その他要素削除方法[remove / clear]

from collections import deque

que = deque([1, 2, 3, 4, 5, 3])

que.remove(3)

print(que)

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

que.clear()

print(que)

# deque([])

remove()では引数とおなじ要素を削除します。

該当する値が複数ある場合は初めの要素だけ削除されます。

clear()はすべての要素を削除し空のキューになります。

要素のローテーション

from collections import deque

que = deque([1, 2, 3, 4, 5])

que.rotate()

print(que)

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

que.rotate(-1)

print(que)

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

que.rotate(3)

print(que)

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