java - なぜ円形配列としてキューを実装するのですか?

Question

Queues のような FIFO を実装する場合、インストラクターは常に、通常の配列ではなく循環配列として表現するようアドバイスしています。なんで？

後者の場合、配列にガベージ データが含まれてしまうからでしょうか。

Answer 1

一定数の配列スロット/要素を使用している場合は、要素の順序を変更する必要がないため、循環配置でスロットをリサイクルする方が簡単です。Array-Like 配置で最初の Element が削除されるたびに、残りの Elements を 1 ポジション前に移動する必要があるため、head は ではありませんnull。循環キューでは、ポインターを最初の位置に増やすだけです。これにより、更新時の操作が少なくなり、パフォーマンスが向上します。

無制限/動的な数のスロットを持つキューを構築している場合、メモリを動的に解放して割り当てることができるため、これは問題ではありません。

Answer 2

例えをあげます。

露天商の行列を想像してみてください。人々は列の最後尾に加わり、前からサービスを受けます。各人にサービスが提供されると、キューに残っている人が順方向にシャッフルされ (通常、どれくらい時間がかかるかについてつぶやきます)、新しい人が最後に参加します。この例では、他の人が列に加わることができるように、人々は前に進む必要があります。そうしないと、キューの最後が常にベンダーから遠ざかってしまいます。したがって、この例では、サーバーはキューの先頭に留まり、先頭にいる人または誰もいない人を処理します。

ここで、人々が移動せず、代わりに列の先頭にサービスを提供した後、売り手自身が列に沿ってさらに移動し、実際には列の先頭に移動した場合を想像してください。最終的に100人にサービスを提供した後、サーバーは通りの途中にあり、500人を超えるとサーバーは次の通りに移動します...どこで停止しますか?

そのため、売り手は便宜上、人々がいつでも列の最後尾に加わることができる広い周回エリアをマッピングし、常に次の人に移動しますが、列は 1 か所にとどまります。彼は人々にサービスを提供する列を一周するだけです。確かに、彼は列に並んでいる人々にしかサービスを提供できませんが、十分に大きくすれば、需要に追いつくことができ、指定された販売エリアから移動する必要はありません.

この類推をコンピューターに戻します...最初の例では、キュー マネージャーがあり、アイテムが処理されると、バッファーに沿ってアイテムがシャッフルされます。2番目の例では、プログラムは配列に追加するメモリがなくなるまで実行されます = 固定サイズ (スペースによって定義または制限されます)。3 番目の例では、サーバーは2 番目の例のようにキューの先頭に移動しますが、配列は固定されており、非常に多くの項目しかキューに追加できませんが、それでもサービス FIFO を取得します。

tl;dr: リソースの効率的な管理。

Answer 3

nインデックス 0 が常に最初のアイテムであり、インデックスが常に最後のアイテムである配列によってサポートされる Queue を想像してください。キューからアイテムを削除するには、1 から n までのすべてのアイテムを前方にシフトして、インデックス 1 にあったものをインデックス 0 に配置する必要があります。またはキューでの頻繁な操作。

配列を循環バッファーとして扱うことにより、キューのヘッドが削除されたときに次のアイテムを指すことが、単一の割り当てと同じくらい簡単になり、明らかにはるかにパフォーマンスが向上します。

Answer 4

それは主にパフォーマンスとシンプルさの問題です。標準配列では、キューから要素を選択するたびにすべての要素をシフトする必要があります。循環配列を使用すると、現在のポインターとサイズを更新するだけで済みます...はるかに効率的です。