1

アルゴリズムに関するロバート・セドウィックの本のキューについて読んでいます

データ構造内のアイテム自体が配列インデックスである場合、そのようなアイテムを「インデックスアイテム」と呼びます。通常、さらに別の配列に保持されたM個のオブジェクトのセットがあり、より複雑なアルゴリズムの一部として一般化されたキュー構造を通過する必要があります。オブジェクトはインデックスによってキューに入れられ、削除されるときに処理されます。各オブジェクトは1回だけ正確に処理されます。通常、重複のないキュー内の配列インデックスは、この目標を直接達成します。

最後の文の私の質問「オブジェクトはインデックスによってキューに入れられ、削除されると処理されます。各オブジェクトは正確に1回処理されます」？2つのアレイではなく1つのアレイのみを使用していますか？

著者は、「通常、重複のないキュー内の配列インデックスは、この目標を直接達成する」とはどういう意味ですか。？

お時間を割いていただきありがとうございます

4

1 に答える 1

6

さて、著者は、配列に格納されているデータを処理するアルゴリズムタスクに対処したいと考えています。

       +-----+-----+---------+-----+
Data = | Foo | Bar | Grandma | Zip |
       +-----+-----+---------+-----+

このデータは、アルゴリズムによって決定されたある種の順序で処理する必要があり、次に処理したい項目のある種の「やること」キューがあります。実際のデータオブジェクトをコピーすることは、望ましくないか不可能な場合があります（オブジェクトが大きいか、コピーできない場合があります）。インデックスのキューはトリックを行います：

             --+---+---+--\
ToDo = [2] --> | 0 | 3 | -----> (1)
             --+---+---+--/

キューは、それData[1]が次に処理されるアイテムであることを示しています。Data[3]そしてData[0]待っています、そして私たちはそれData[2]が最新のタスクとしてやってくると決めました。

（たとえば、キュ​​ーはツリー構造の幅優先探索で使用されます。次にアクセスするノードを一方のキューからポップし、もう一方の側で将来の作業としてそのノードの子をプッシュします。各ノードには1回だけアクセスする必要があります。上記のインデックスキューを使用すると、実際のツリー要素をData配列に格納し、軽量インデックスのみで参照できます。）

于 2012-08-24T12:10:38.950 に答える