両端キュー（りょうたんキュー、）またはデック（）は、計算機科学における抽象データ型の1つで、先頭または末尾で要素を追加・削除できるキューである。head-tail linked list とも。"deque" を "dequeue" と書く場合もあるが、"dequeue" はキューから要素を取り出す操作（デキュー）も表すため、技術的な文書では避けるのが一般的である。それでも、一部のライブラリでは "dequeue" という用語を使っているし、アルフレッド・エイホ、ジョン・ホップクロフト、ジェフリー・ウルマンの書いた教科書 "Data Structures and Algorithms" でも使っている。また、DEQ や DQ という記法もある。両端キューはキューやFIFOとは異なる。キューやFIFOでは一方の端からのみ要素を追加し、もう一方の端からのみ要素を取り出す。この汎用データクラスにはいくつかの派生型が存在する。情報処理でよく使われるリスト状のデータ型として、キューとスタックがあるが、これらは両端キューを特殊化したものと言え、両端キューを使って実装できる。両端キューでは、以下のような操作が可能である。両端キューの効率的実装方法は2つある。ひとつは動的配列を修正したもので、もうひとつは双方向連結リストを使った実装である。動的配列による実装は、どちらの方向にも成長できる動的配列を使うもので、配列デック (array deque) とも呼ぶ。配列デックは動的配列でもあるため、定数時間でランダムアクセスが可能で参照の局所性もよいが、途中への挿入/削除が非効率だが両端での挿入/削除が定数時間になっている。典型的実装として以下の2つがある。両端キューの使用例として "A-Steal" スケジューリングがある。これは、複数のプロセッサにタスクをスケジューリングするアルゴリズムである。プロセッサ毎に実行可能なスレッドを入れる両端キューがある。プロセッサが次のスレッドを実行するとき、対応する両端キューの先頭からスレッドを取出す。実行中のスレッドがforkした場合、そのスレッドは両端キューの先頭に追加され、新たに生成したスレッドを実行する。あるプロセッサに実行可能なスレッドが無くなった場合（対応する両端キューが空になった場合）、他のプロセッサからスレッドを貰ってくる（あるいは「盗んでくる (steal)」）ことができ、他のプロセッサの両端キューの末尾から要素を取出して、それを実行する。

出典:wikipedia