language-concepts - 循環キュー理論

Question

循環キューの概念を理解するのに助けが必要です。私はスタックオーバーフローに関するいくつかの投稿を読みましたが、私が抱えているメンタルブロックに答えている答えはありません。

たとえば、循環キューに 8 つのセルがあるとします。

        Head                              Tail
 empty|U    |   I  |   S  |   K  |   M  |   empty  |   empty 

F と P の 2 文字を挿入すると、キューが に変わります。

  Tail  Head                                
 empty|U    |   I  |   S  |   K  |   M  |   F  |   P 

3 つのエントリを削除するとどうなるでしょうか。

  Tail                                  Head                
 empty|  empty  |  empty   |  empty   |   K  |   M  |   F  |   P 

明らかに頭と尻尾が変わり、3 つの新しいスポットが利用可能になりました。しかし、適切な手段として、さらに 2 つのエントリを追加したいと思いました。

            Tail                Head                
 A|  B  |  empty   |  empty   |   K  |   M  |   F  |   P 

これが私の質問です

私はこれを正しく実装しましたか？LOL テールとヘッドが同じ位置、つまり「K」にあるようにキューを完全に埋めるとどうなりますか? この概念をもう少し詳細かつ明確に説明できる人がいれば、私はそれを高く評価します.

ありがとう！

Answer 1

あなたが正しいように私には見えます。頭と尾の整数値を表示することで、図をより明確にすることができます

循環キューには多くの説明と例があります。少し前にここで提供した回答に投稿したものよりも良い説明は見つかりませんでした。キューが空、余裕がある、または満杯の場合に、頭と尾がどのように表示されるかを説明します。

ダイアグラムの最後の行では、キューにさらに 2 つのアイテムを入れる余地があります。3 分の 1 を追加すると、tail = head になり、K が上書きされます。これは望ましくありません。

tail = head の場合、キューは空です。満杯のキューのテストは少し複雑です。完全な説明については、リンクを参照してください。