両端キュー

両端キュー（Deque）とは

両端キュー（double-ended queue, またはdeque）は、計算機科学における抽象データ型の一つで、その名の通り、データの追加と削除を両端から行えるキューのことです。head-tail linked listとも呼ばれます。

名称について

dequeはdequeueと書かれることもありますが、dequeueはキューから要素を取り出す操作も意味するため、技術文書ではdequeを使用するのが一般的です。ただし、一部のライブラリや教科書ではdequeueの用語も使われています。また、DEQやDQと表記されることもあります。

キューとの違いと派生型

通常のキュー（FIFO）では、要素の追加は一方の端から、取り出しはもう一方の端からしかできません。これに対し、両端キューは両端での追加と取り出しが可能です。この汎用性から、以下のような派生型が存在します。

入力制限型デック: 要素の取り出しは両端で可能だが、追加は片方からしか行えない。
出力制限型デック: 要素の追加は両端で可能だが、取り出しは片方からしか行えない。

情報処理でよく使われるキューやスタックは、両端キューを特殊化したものと捉えることができ、両端キューを用いて実装可能です。

操作

両端キューでは、以下の操作が可能です。

両端への要素の追加: キューの先頭と末尾の両方へ要素を追加できます。
両端からの要素の削除: キューの先頭と末尾の両方から要素を削除できます。
先頭要素の参照: キューの先頭にある要素を参照できます。
末尾要素の参照: キューの末尾にある要素を参照できます。

実装

両端キューを効率的に実装する方法は主に2つあります。

1. 動的配列: 配列のサイズを必要に応じて動的に変更する方式です。配列デックとも呼ばれます。ランダムアクセスが可能で、参照の局所性も高いですが、中間への挿入や削除は効率が悪いという欠点があります。ただし、両端での挿入・削除は定数時間で可能です。
リングバッファを用いる方法: リングバッファに両端キューの内容を格納し、満杯時にサイズを拡大します。サイズ拡大の頻度を減らせますが、インデックスのために余分な命令が必要になります。
配列の中央から配置する方法: 配列の中央から両端キューの内容を配置し、端まで満杯になったときにサイズを拡大します。サイズ拡大の頻度は増えますが、片端のみに追加する場合はメモリの無駄が多くなる可能性があります。
2. 双方向連結リスト: 各要素が前後の要素へのポインタを持つリスト構造です。要素の挿入・削除が高速に行えます。ただし、ランダムアクセスはできません。

言語サポート

多くのプログラミング言語で両端キューがサポートされています。

C++: Standard Template Library (STL) に `std::deque` として提供されています。通常、固定サイズの配列を用いて実装されています。ランダムアクセスも可能ですが、中間部分への挿入・削除は効率が悪いです。
Java: Collections Framework に `Deque` インターフェースがあり、`ArrayDeque` や `LinkedList` がその実装クラスとして提供されています。
Python: `collections.deque` が提供されています。
PHP: SPL extension の `SplDoublyLinkedList` クラスが両端キューの実装に利用できます。

計算量

双方向連結リストによる実装では、全ての操作の時間計算量はO(1)です。動的配列の場合、追加操作の最悪時間計算量はO(n)ですが、償却時間計算量はO(1)となります。

使用例

両端キューは、A-Stealスケジューリングなどのアルゴリズムで利用されます。このアルゴリズムでは、各プロセッサが実行可能なスレッドを両端キューに格納し、空いたプロセッサが他のプロセッサからスレッドを「盗んで」実行することで、並列処理の効率を高めます。

関連項目

キュー
優先度付きキュー

外部リンク

SGI STL Documentation: deque
Code Project: An In-Depth Study of the STL Deque Container
Diagram of a typical STL deque implementation
deque implementation in flash actionscript 3 open source library

もう一度検索