両端キュー

両端キュー（りょうたんキュー、）またはデック（）は、計算機科学における抽象データ型の1つで、先頭または末尾で要素を追加・削除できるキューであるDonald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.。head-tail linked list とも。

 名称について 
 を  と書く場合もある。ただし、 はキューから要素を取り出す操作（デキュー）も表すため、技術的な文書では避けるのが一般的である。

それでも、一部のライブラリや、アルフレッド・エイホ、ジョン・ホップクロフト、ジェフリー・ウルマンの書いた教科書 Data Structures and Algorithms でも  という用語を使っている。

また、DEQ や DQ という記法もある。

 キューとの違いと派生型 
両端キューはキューやFIFOとは異なる。キューやFIFOでは一方の端からのみ要素を追加し、もう一方の端からのみ要素を取り出す。この汎用データクラスにはいくつかの派生型が存在する。

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

情報処理でよく使われるリスト状のデータ型として、キューとスタックがあるが、これらは両端キューを特殊化したものと言え、両端キューを使って実装できる。

 操作 
両端キューでは、以下のような操作が可能である。
 操作  C++  Java  Perl  PHP  Python  Ruby  JavaScript 末尾に要素を追加  push_back  offerLast  push  array_push  append  push  push 先頭に要素を追加  push_front  offerFirst  unshift  array_unshift  appendleft  unshift  unshift 末尾の要素を取出す  pop_back  pollLast  pop  array_pop  pop  pop  pop 先頭の要素を取出す  pop_front  pollFirst  shift  array_shift  popleft  shift  shift 末尾の要素を調べる  back  peekLast  $_[-1]  end  <obj>[-1]  last  <obj>[<obj>.length - 1] 先頭の要素を調べる  front  peekFirst  $_[0]  reset  <obj>[0]  first  <obj>[0]

 実装 
両端キューの効率的実装方法は2つある。ひとつは動的配列を修正したもので、もうひとつは双方向連結リストを使った実装である。

動的配列による実装は、どちらの方向にも成長できる動的配列を使うもので、配列デック (array deque) とも呼ぶ。配列デックは動的配列でもあるため、定数時間でランダムアクセスが可能で参照の局所性もよいが、途中への挿入/削除が非効率だが両端での挿入/削除が定数時間になっている。典型的実装として以下の2つがある。
 リングバッファに両端キューの内容を格納し、バッファが満杯になったときだけサイズを拡大する。これはサイズ拡大の頻度を減らすことができるが、インデックスのために余分な分岐命令を必要とする。
 配列の真ん中から両端キューの内容を配置していき、どちらかの端まで満杯になったときにサイズを拡大する。この場合、サイズ拡大の頻度は多くなるし、一方の端でのみ追加する場合はメモリ空間を無駄にする割合が大きい。

 言語サポート 
C++
Standard Template Library にクラステンプレートとして std::deque が用意されている。内部の実装方法は規定されていないが、通常は1つ以上の固定サイズ配列を用いて実装されているスコット・メイヤーズ、『Effective STL STLを効果的に使いこなす50の鉄則』、ピアソン・エデュケーション、2002年、第7章、ISBN 4-89471-410-8。両端だけでなくランダムアクセスをサポートしており、キューの中間部分も直接読み書きできる（ただし、キュー両端への挿入・削除がO(1)なのに対し、中間への挿入・削除はO(n)となる）。

Java 6
Collections Framework に  インタフェースがあり、両端での追加・取出し機能を提供している。これを実装したクラスとして  や  がある。こちらも前者が動的配列実装、後者が連結リスト実装である。

Python 2.4/3
collections.deque が提供されている。

PHP 5.3
SPL extension に SplDoublyLinkedList クラスがあり、両端キューデータ構造の実装に使える。それまでは配列の関数 array_shift/unshift/pop/push しか使えなかった。

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

 使用例 
両端キューの使用例として A-Steal スケジューリングがある See p.22.。これは、複数のプロセッサにタスクをスケジューリングするアルゴリズムである。プロセッサ毎に実行可能なスレッドを入れる両端キューがある。プロセッサが次のスレッドを実行するとき、対応する両端キューの先頭からスレッドを取出す。実行中のスレッドがforkした場合、そのスレッドは両端キューの先頭に追加され、新たに生成したスレッドを実行する。あるプロセッサに実行可能なスレッドが無くなった場合（対応する両端キューが空になった場合）、他のプロセッサからスレッドを貰ってくる（あるいは「盗んでくる (steal)」）ことができ、他のプロセッサの両端キューの末尾から要素を取出して、それを実行する。

 関連項目 
キュー
優先度付きキュー

 脚注 

 外部リンク 
 SGI STL Documentation: deque<T, Alloc>
 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

Category:データ構造
Category:抽象データ型