両端キュー（りょうたんキュー、英: double-ended queue）またはデック（英: deque）は、計算機科学における抽象データ型の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つがある。
std::deque が用意されている。内部の実装方法は規定されていないが、通常は1つ以上の固定サイズ配列を用いて実装されている。両端だけでなくランダムアクセスをサポートしており、キューの中間部分も直接読み書きできる（ただし、キュー両端への挿入・削除がO(1)なのに対し、中間への挿入・削除はO(n)となる）。Deque インタフェースがあり、両端での追加・取出し機能を提供している。これを実装したクラスとして ArrayDeque や LinkedList がある。こちらも前者が動的配列実装、後者が連結リスト実装である。collections.deque が提供されている。SplDoublyLinkedList クラスがあり、両端キューデータ構造の実装に使える。それまでは配列の関数 array_shift/unshift/pop/push しか使えなかった。両端キューの使用例として A-Steal スケジューリングがある。これは、複数のプロセッサにタスクをスケジューリングするアルゴリズムである。プロセッサ毎に実行可能なスレッドを入れる両端キューがある。プロセッサが次のスレッドを実行するとき、対応する両端キューの先頭からスレッドを取出す。実行中のスレッドがforkした場合、そのスレッドは両端キューの先頭に追加され、新たに生成したスレッドを実行する。あるプロセッサに実行可能なスレッドが無くなった場合（対応する両端キューが空になった場合）、他のプロセッサからスレッドを貰ってくる（あるいは「盗んでくる (steal)」）ことができ、他のプロセッサの両端キューの末尾から要素を取出して、それを実行する。
