両側キュー(deque)とは
両側キュー(deque)とは、
です。
これにより、先頭からの要素の追加・削除（スタックの操作）と、末尾からの要素の追加・削除（キューの操作）の両方が可能になります。
両側キュー(deque)の実装方法
pythonでは、キュー(FIFO: First In, First Out)・スタック(LIFO: Last In, First Out)のいずれのデータ構造も標準ライブラリcollectionsで実装することができます。
そのため、collectionsライブラリを利用した両側キュー(deque)の実装を解説していきます。
まずは、deque関数にlistを渡すことで初期化します。
from collections import deque
# キュー・スタックの作成
my_deque = deque([1, 2, 3])
print(my_deque)deque([1, 2, 3])
末尾に要素を追加する
listと同様に、appendを使って末尾に要素を追加していきます。
# 値を追加
my_deque.append(4)
my_deque.append(5)
print(my_deque)deque([1, 2, 3, 4, 5])
末尾の要素を取り出す
popを使って末尾から要素を取り出すと、スタック(LIFO: Last In, First Out)として利用できます。
# スタックの先頭を取得
tmp = my_deque.pop()
print(my_deque)
print(tmp)deque([1, 2, 3, 4])
5
先頭の要素を取り出す
popleftを使うと先頭から要素を取り出すことができ、キュー(FIFO: First In, First Out)として利用できます。
# キューの先頭を取得
tmp = my_deque.popleft()
print(my_deque)
print(tmp)deque([2, 3, 4])
1
要素の参照
Listと同様に配列の添え字で要素を参照できます。
ただし、Listと違いdequeでは両端の値以外の参照コストが大きくなっているので、注意が必要です。
# スタックの先頭の値を参照
print(my_deque[-1])4# キューの先頭の値を参照
print(my_deque[0])2
dequeはListと同様にlen関数を使って、サイズを取得することもできます。
# 要素数を取得
print(my_deque)
print(len(my_deque))deque([2, 3, 4])
3
dequeとListの違い
dequeはListと似ていますが、得意・不得意な操作があり用途によって使い分けることが望ましいです。
dequeとListにおける各操作の計算量は以下のようになります。
| list |
deque |
|||
| 先頭に追加 |
insert | O(n) | appendleft | O(1) |
| 末尾に追加 | append | O(1) | append | O(1) |
| 先頭要素の取り出し | pop(0) | O(n) | popleft | O(1) |
| 末尾要素の取り出し | pop() | O(1) | pop | O(1) |
| 中央の要素の参照 | list[k] | O(1) | deque[k] | O(n) |
dequeでは、popleft（右端への追加と左端からの削除）とappendleftによる先頭への操作が高効率となっています。
しかし、先頭以外の要素へのアクセス効率が悪くなっています。
そのためインデックスを使ったアクセスには適していません。
末尾の要素にアクセスする計算量はdequeでもListでも実は変わらないので、スタック(LIFO: Last In, First Out)としての利用であればどちらでも構いません。
また、dequeはListよりもメモリ効率が高く、特に大量の要素を追加・削除する場合に優れています。
dequeはリングバッファ（circular buffer）として実装されており、内部的にはブロック単位でメモリを割り当てることで、要素の追加・削除が効率的に行えます。
dequeとListの使い分け
dequeとListの使い分けは以下のようになります。
スタック・キューの関連ライブラリの整理
スタック・キューを実装するライブラリはcollections以外にもqueueライブラリが存在します。
| 分野 | queue | collections |
| スタック | queue.LifoQueue | collections.deque |
| キュー | queue.Queue | collections.deque |
collectionsモジュールのdequeとqueueモジュールのQueueクラスは、両方ともキュー（queue）を扱うためのものですが、2点違いがあります。
スレッドセーフ性
スレッドセーフ性は、キューが複数のスレッドからの操作に対応しているかどうかの違いです。
collections.dequeはスレッドセーフではなく、複数のスレッドから同時にアクセスすると競合状態が発生する可能性があります。
一方で、queue.Queueはスレッドセーフなので、複数のスレッドから同時にアクセスしても安全です。
これはthreadingモジュールを用いたマルチスレッドプログラミングに適しています。
キューの機能(単一キュー・双方向キュー)
要素の取り出し方法の違いもあります。
collections.dequeは双方向キューであり、両端への高効率な要素の追加と削除が可能です。
queueライブラリでは単一のキューであり、要素の取り出し方は1方向からとなっています。
queue.Queueを使った場合はFIFO（先入れ先出し）の原則に従い、queue.LifoQueueを使った場合はLIFO（後入れ先出し）の原則に従います。
参考文献
コメント