両端キュー

両端キュー（りょうたんキュー、英: double-ended queue）またはデック（英: deque）は、計算機科学における抽象データ型の1つで、先頭または末尾で要素を追加・削除できるキューである^[1]。head-tail linked list とも。

名称について[編集]

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

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

また、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つ以上の固定サイズ配列を用いて実装されている^[2]。両端だけでなくランダムアクセスをサポートしており、キューの中間部分も直接読み書きできる（ただし、キュー両端への挿入・削除がO(1)なのに対し、中間への挿入・削除はO(n)となる）。

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

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

脚注[編集]

^ 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.
^ スコット・メイヤーズ、『Effective STL STLを効果的に使いこなす50の鉄則』、ピアソン・エデュケーション、2002年、第7章、ISBN 4-89471-410-8
^ Eitan Frachtenberg, Uwe Schwiegelshohn (2007). Job Scheduling Strategies for Parallel Processing: 12th International Workshop, JSSPP 2006. Springer. ISBN 3540710345 See p.22.

外部リンク[編集]

[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.

[2] スコット・メイヤーズ、『Effective STL STLを効果的に使いこなす50の鉄則』、ピアソン・エデュケーション、2002年、第7章、ISBN 4-89471-410-8

[3] Eitan Frachtenberg, Uwe Schwiegelshohn (2007). Job Scheduling Strategies for Parallel Processing: 12th International Workshop, JSSPP 2006. Springer. ISBN 3540710345 See p.22.

[1]

[2]

[3]