data-structures - 循環キューの欠点?

Question

最近、あるインタビューで、循環キューを使用することのデメリットを尋ねられました。私は何も考えられませんでした。インターネットを検索して見つけた唯一の答えは、線形キューよりも実装が難しいということです:)。他にデメリットはありますか？

Answer 1

循環キューの最大の欠点は、queue.length 要素しか格納できないことです。バッファとして使用している場合は、履歴の深さを制限しています。

もう 1 つの小さな欠点は、追加情報を保持せずに空のキューと満杯のキューを区別するのが難しいことです。

Answer 2

インタビュアーが求めていた答えは、おそらく、上記の質問には含まれていない追加のコンテキストに依存しています。

たとえば、循環キューは、高度な並行生産者/消費者システムの場合に考慮されることがよくあります。キューがいっぱいになると、キューの前後の操作が同じキャッシュ ラインを求めて競合する可能性があり、このようなコンテキストでは問題になる可能性があります。

あるいは、循環配列ベースのキューと比較して、ガベージ コレクション言語でロックフリーのリンク キューを作成するのがいかに簡単かについて、インタビュアーがあなたに話してほしかったのかもしれません。

あるいは、循環キューの代わりに定期的なシフトを伴う線形キューを使用すると、言語が提供するベクトル コンテナーをどのように活用できるかということだけかもしれません。

Answer 3

キューをトラバースするコードは、トラバースの終わりを検出するために最初のノードを追跡する必要があるように思えます。しかし、マルチスレッド環境では、別のスレッドが最初のノードを削除する可能性があり、これによりトラバース スレッドが無限ループに陥ります。そのため、トラバース スレッドは、キューを循環している間、最初のノードをロックしたままにしておく必要があります。