queue　解答ページ | Programming Place Plus　C++編【標準ライブラリ】　第１１章

問題①

問題①　queue が内部で使用するコンテナとして、vector を選択できませんが、その理由を説明してください。また、選択できたとして、適切な選択となり得るでしょうか？

vector には、pop_frontメンバ関数がないことが理由です。実際のところ、queue の popメンバ関数を使わなければ、pop_front を呼び出そうとしないので、単に、

std::queue<int, std::vector<int> > iQueue;

このように、変数を定義するだけではエラーにはならないでしょう。とはいえ、pop できない queue に価値があるとも思えないので、事実上、選択できないと考えられます。

また、キューというデータ構造の特徴と、vector の実装を考えると、もし使えるとしても、非効率になってしまいます。これは、配列の先頭側から要素を取り出すので、後続の要素を手前にずらす必要があるためです。一般に、配列を使ってキューを実装する場合、リングバッファ構成にしますが（アルゴリズムとデータ構造編【データ構造】第６章）、vector はそうはなっていないので、不適格と言えます。