0

Cyclic Queue の実装では、テール ポインターはキューの最後の要素の 1 つ後ろの位置を指します。

|1|2|3|4|5| | |
 ^         ^
front      tail

なぜ？

最後の要素の 1 つ前ではなく、最後の要素を指すテール ポインターを使用して Cyclic Queue を実装できると思います。

4

2 に答える 2

1

実際、そのように実装できます。テール ポインターが最後の要素の 1 つ後ろの位置を指すようにすることには、特定の対称性があります。

  • front最初の (最も古い) 使用された要素を指す - 次に読み込まれる要素
  • tail最初の (最も古い) 未使用の要素を指す - 次に書き込まれる要素

いずれの場合も、満杯の循環キューと空の循環キューを区別するために、もう少し処理を行う必要があります。いくつかの代替手段 (自分のやり方を含む) については、ウィキペディアの循環バッファーに関する記事で説明されています。

于 2011-09-08T02:53:04.993 に答える
0

キューが空か満杯かを判断する方法の実装のようです。

http://en.wikipedia.org/wiki/Circular_buffer#Full_.2F_Empty_Buffer_Distinction

于 2011-09-08T02:51:55.723 に答える