3

循環キューと循環単一リンクリストの明確な違いが欲しいですか？最初は、どちらもほぼ同じように見えますが...

4

3 に答える 3

9

循環キューまたは循環バッファ：キューを実装する方法です。たとえば、配列を使用してキューを実装するとします。あなたはあなたenqueue()とdequeue()メソッドを持っているでしょう。

基になる配列の長さが7で、ユーザーが5つの値をエンキューするとします。したがって、基になる配列の値は次のようになります。

            head                   tail
position:  | 0 | 1  | 2 | 3 | 4  |   5  |   6  |
value:     | 3 | 12 | 5 | 4 | 71 | free | free |

3ここで、ユーザーは要素をデキューして、位置から値を削除したいと考えています0。キューの実装者として、これを処理する方法を理解する必要があります。基本的な解決策は、すべての値を1つ下に移動して、基になる配列が次のようになるようにすることです。

            head               tail
position:  | 0  | 1 | 2 | 3  | 4    |   5  |   6  |
value:     | 12 | 5 | 4 | 71 | free | free | free |

ただし、何かをデキューするたびに、不必要に多くの値をコピーする必要がある場合があります。これを回避する1つの方法は、頭が0ではなく1の位置にあると言うことです。

                   head               tail
position:  |   0  | 1  | 2 | 3 | 4  |   5  |   6  |
value:     | free | 12 | 5 | 4 | 71 | free | free |

したがって、新しい要素を追加するたびに、それを（に追加するtail（そして位置をインクリメントするtail）だけです。要素を削除する場合は、を移動するだけheadです。このようにして、不要なコピーを行う必要はありません。

が配列の最後にtail到達すると、配列の最初にラップオーバーを開始します。つまり、キューは基になる配列上を「円」で移動します。たとえば、さらに数回エンキューおよびデキューすると、基になる配列は次のようになります。

                  tail                head
position:  | 0  |   1  |   2  |   3  | 4  | 5  | 6 |
value:     | 91 | free | free | free | 71 | 22 | 8 |

これで、テールが配列の先頭に回り込みました。

循環リンクリスト：頭が尾を指すリンクリスト。汎用の円形構造です。循環キュー/バッファを実装するために使用することも、他の目的で使用することもできます。

于 2012-08-08T15:13:54.607 に答える
1

これをチェックしてください: http://www.vias.org/cppcourse/chap20_05.html標準定義では循環キューが配列として実装されていることがわかります。

于 2012-08-08T15:00:43.570 に答える