1

我正在阅读 robert sedwick 关于算法的书中的队列

当数据结构中的项本身是数组索引时，我们将此类项称为“索引项”。通常，我们有一组 M 个对象，保存在另一个数组中，我们需要通过一个通用队列结构作为更复杂算法的一部分。对象按索引入队，取出时处理，每个对象都精确处理一次。通常，队列中没有重复的数组索引直接实现了这个目标。

我在最后一句中的问题“对象按索引放入队列并在删除时进行处理，并且每个对象都将被精确处理一次”？我们只使用一个数组而不是两个数组？

作者所说的“通常没有重复的队列中的数组索引直接实现了这个目标”是什么意思。?

感谢您的时间和帮助

4

1 回答 1

6

好吧，作者想要解决处理存储在数组中的数据的算法任务：

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

我们需要以某种由我们的算法确定的顺序来处理这些数据，并且我们接下来要处理某种“待办事项”队列。复制实际数据对象可能是不可取的或不可能的（对象可能很大或不可复制）。索引队列可以解决问题：

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

队列告诉我们这Data[1]是下一个要处理的项目。Data[3]并且Data[0]正在等待，我们刚刚决定将其Data[2]作为最近的任务。

（例如，队列用于树结构的广度优先搜索：您从一侧的队列中弹出下一个要访问的节点，并将该节点的子节点作为未来工作推入另一侧。每个节点都应该被访问一次。上面的索引队列允许你将实际的树元素存储在Data数组中，并且只通过轻量级索引来引用它们。）

于 2012-08-24T12:10:38.950 回答