キューが循環キューよりも好都合なユースケースですか？

Question

循環キューは明らかに優れています。なぜなら、要素をポップアウトすることによって残された空きスペースを使用するのに役立つからです。また、各ポップの後に要素の横方向シフトを行うために使用された可能性のある時間を節約する。

しかし循環キューを使用するよりもキューが優先されるユースケースはありますか？キューの

定義=私たちは、リニアアレイの実装となります。 FIFOと循環キュー=リングバッファの実装の無上書き

定義は、以下の通りです。 FIFOに従います。上書きはありません。

Answer 1

注：多くの言語でqueueは単なるインターフェイスであり、実装については何も言及していません。

リングバッファa.k.a、アレイベースの循環キューを使用して、あなたは完全なバッファにプッシュする状況に対処しなければなりません。あなたは可能性：

1. はスペースが
2. （再）メモリを割り当てて、すべてのコンテンツ
3. は特大のバッファを使用してコピーするので、このような状況もありますまで挿入
4. が
5. ブロックを最も古いエントリを上書き無視これらの各オプション欠点を持っている

起こることはありません。彼らと一緒に暮らすことができたり、バッファをいっぱいにしないことが分かっている場合は、リングバッファーを使用してください。

オプション3 & 4は、吃音を誘導します。あなたのユースケースによっては、より長くても安定したアクセス時間と信頼性が望ましく、がを超える場合はとなります。linked listなどの動的実装を選択すると、dequeのようになります。

使用例の例のように、あなたは安定したフレーム/サンプリングレートやスループットを達成するために持っていて、吃音を容認することはできませんタスク、以下のとおりです。

• リアルタイムのビデオとオーディオ処理
• リアルタイム
をレンダリングあなたが新しい仕事を押したときにスレッドが長すぎるためにブロックしたくないとき
• スレッド・プールをネットワーク
• 。

ただし、リニアアレイをベースにしたキューには同じような欠点があります。私は循環キュー上でリニアキューを選択する理由は見ません。 （やや高い実施の複雑さに加えて）

std::queue C++では、デフォルトで下地コンテナとしてdequeを使用します。 dequeは本質的に、小さなチャンクでメモリを割り当てて吃音を起こさないため、ほとんどのユースケースで良い基盤のように見える配列の動的配列です。