このページでは STL の deque（デック）の使い方について解説します。
deque（デック）とは ページの先頭へ
deque は、Double Ended Queue の略で、双方向キュー、両端キュー、待ち行列などとも呼ばれるデータ構造を実装した STL のコンテナです。機能としては、vector（可変長配列）を双方向に伸縮自在にしたようなものと思えばよいでしょう。
vector は push_back() で、配列の後端に要素を追加し、pop_back() で取り除くというものでしたが、deque はこれに加えて、push_front() で配列の前端に要素を追加し、pop_front() で取り除くという機能が使用可能です。
キューは、最初に入れたものが最初に取り出されるという意味の「First in/First out」の略で FIFO（ファイフォー）と呼ばれることがあります。
これに対し、スタックは最後に入れたものが最初に取り出されるという意味の「Last in/First out」の略で LIFO（リーフォー）と呼ばれることがあります。
deque は、FIFO/LIFO どちらにも使用可能なフレキシブルなデータ構造です。
その他、整数の添字で要素にアクセスできるという点も vector と同様です。
deque は、配列の機能も持っているということになります。
ナオ ： 質問ですけど、これって deque があれば vector も queue も stack も list も要らないってことですか?
店主 ： 少なくとも deque を使えば他のもので出来ることは何でも出来るよね。実力派なんだ。
ナオ ： じゃぁ、プログラムは全て deque を使って書けば良いってこと?
店主 ： そうしてみるかい?
典型的な使い方は次のようになります。下の実行結果の表示で deque の前端は左に、後端は右に表示されるので、コメント中の「左に追加」はdeque の前端に追加を表し、「右に追加」は deque の後端に追加の意味です。ちょっと長いですが、やっていることは単純ですので、眺めてみてください。コメントだけを読めば、何をやっているか 5 秒程度で把握できると思います。
#include <iostream>
#include <deque>
using namespace std;
void Print(deque<char>& rdeqc) {
cout << "size = " << rdeqc.size() << " ";
for (deque<char>::iterator itc = rdeqc.begin(); itc != rdeqc.end(); itc++) { cout << ", " << *itc; }
cout << endl;
}
int main() {
deque<char> deqc; Print(deqc); // オブジェクトを定義
deqc.push_back ('a'); Print(deqc); // 右に追加
deqc.push_back ('b'); Print(deqc); // 〃
deqc.push_back ('c'); Print(deqc); // 〃
deqc.push_front('A'); Print(deqc); // 左に追加
deqc.push_front('B'); Print(deqc); // 〃
deqc.push_front('C'); Print(deqc); // 〃
deqc.pop_front(); Print(deqc); // 左から削除
deqc.pop_back(); Print(deqc); // 右から削除
cout << "deqc[0] = " << deqc[0] << endl; // 添字でアクセス
cout << "deqc.front() = " << deqc.front() << endl; // 左端にアクセス
cout << "deqc.back() = " << deqc.back() << endl; // 右端にアクセス
deqc.front() = 'L'; Print(deqc); // 左端に書きこみ
deqc.back() = 'R'; Print(deqc); // 右端に書きこみ
return 0;
}
上記の実行結果は、次のようになります。
size = 0 size = 1 , a size = 2 , a, b size = 3 , a, b, c size = 4 , A, a, b, c size = 5 , B, A, a, b, c size = 6 , C, B, A, a, b, c size = 5 , B, A, a, b, c size = 4 , B, A, a, b deqc[0] = B deqc.front() = B deqc.back() = b size = 4 , L, A, a, b size = 4 , L, A, a, R
先端（左端）のインデクスは? ページの先頭へ
ここで言う先端（左端）のインデクスとは、上記の例で強調表示した、結果の左端 a, a, a, A, B, C, B, B, L, L をアクセスするための添字のことで、これは、常に 0 になります。
つまり、これらは全て deqc[0] でアクセスできます。deque の左端の添字は常に 0 と覚えておきましょう。
deque をいわゆるキュー（＝FIFO）として使用することも出来ますが、途中の要素にも（キューとしては裏技的に）添字演算子でアクセスできてしまい、ある意味無節操なため、ストイックにキューの機能だけを使いたければ、deque や list を純粋なキューとして使うために queue というコンテナアダプタが別途用意されていますのでこれを使うのが良いでしょう。
同様に deque をいわゆるスタック（＝LIFO）として使用するには、stack というコンテナアダプタが用意されていますので、これを使うのが良いでしょう。
deque に入れる自作クラスを作成するには ページの先頭へ
deque に入れる自作クラスには、簡単には、「デストラクタ」と「デフォルトコンストラクタ」と「コピーコンストラクタ」と「イコール演算子」を必要に応じて定義する必要があります。
deque に入れるクラスが満たすべき条件は、vector に入れるクラスと同じなので、詳しくはvector をご覧ください。
deque でどんどん右に移動していくと ページの先頭へ
ある程度の長さの deque<T> オブジェクトの、右端を伸ばし、左端を縮め、長さをある程度の大きさに保つようにしてどんどん右に進んでいくと、ちょっと考えると、メモリをどんどん食っていくように思われるのですが、
[][][][][]
[][][][][]
[][][][][]
[][][][][]
[][][][][] ---> どんどん移動すると
deque の中は、リングバッファになっているので、メモリが無限に食われることはありません。
ただし、バッファ領域の大きさを超える数の要素を追加すると、vector と同様にメモリが再配置されるため、deque の中の各要素へのポインタや参照は意味をなさなくなります。つまり、push_back() や push_front() を使ったら、その前に用意した要素へのポインタや参照ではもはや要素にアクセスすることは出来なくなると考える必要があります。ポインタや参照には旬があるということですね。
ナオ ： ところで deque って「デック」と読むんですね、「デキュー」じゃなくて。
店主 ： 発音をカタカナで書いたんじゃほぼ意味ないと言う気はするけど、そのようだね。英語では deque は両端という意味になるようだよ。ちなみに dequeue（デキュー）というと、キューから取り出すという意味になるんだ。
ナオ ： そうなんですか。
店主 ： そうなんですよ。
