容量に上限があるキューを実現するためには、リングバッファを用いるのが最も効率的です。
しかし、ポインタの操作を含むコードを自分で書くのは間違いのもとです。効率を最優先する場合以外は、ライブラリを使うほうが良いです。
C++の場合、std::deque*1を使うと以下の意味でそれほど効率が落ちることはありません。
- 挿入のたびにメモリ確保が走ることはない（
std::listのような連結リストではこの要件を満たせない） - 挿入または削除のたびに要素の移動が発生することはない（
std::vectorには効率の良いpop_frontが存在せず、erase(vec.begin())などとするとこの要件を満たせない）
正しく実装されたリングバッファと比べて、劣る点は以下の点です。
- かなり多くのメモリを要求する（libstdc++の実装では、少なくとも8192バイト*2必要です）
- TLBをたくさん占有する（非常に小さいリングバッファであれば一つのページ内に収まります。一方、
std::dequeで作った場合、デフォルトのアロケータはページ境界を無視して4096バイト取るため、四つのページを使用することが多いです） - キャッシュヒットしにくい（大きな領域を事実上使い捨てていくことになるためです）
*1:std::queueとしないほうが、デバッグの時に中身を出力できて楽です。
*2:https://ja.cppreference.com/w/cpp/container/deque によれば一つのチャンクが4096バイトで、リングバッファを運用するためには二チャンク必要なためです。実際計測してみるとそうなっています。
