算法(4th ed)(114):基础——背包、队列和栈 5

阅读数:25 2019 年 11 月 2 日 12:27

算法(4th ed)(114):基础——背包、队列和栈 5

许多基础数据类型都和对象的集合有关。具体来说,数据类型的值就是一组对象的集合,所有操作都是关于添加、删除或是访问集合中的对象。在本节中,我们将学习三种这样的数据类型,分别是背包(Bag)、队列(Queue)和(Stack)。它们的不同之处在于删除或者访问对象的顺序不同。

背包、队列和栈数据类型都非常基础并且应用广泛。我们在本书的各种实现中也会不断用到它们。除了这些应用以外,本节中的实现和用例代码也展示了我们开发数据结构和算法的一般方式。

本节的第一个目标是说明我们对集合中的对象的表示方式将直接影响各种操作的效率。对于集合来说,我们将会设计适于表示一组对象的数据结构并高效地实现所需的方法。

本节的第二个目标是介绍泛型迭代。它们都是简单的 Java 概念,但能极大地简化用例代码。它们是高级的编程语言机制,虽然对于算法的理解并不是必需的,但有了它们我们能够写出更加清晰、简洁和优美的用例(以及算法的实现)代码。

本节的第三个目标是介绍并说明链式数据结构的重要性,特别是经典数据结构链表,有了它我们才能高效地实现背包、队列和栈。理解链表是学习各种算法和数据结构中最关键的第一步。

对于这三种数据结构,我们都会学习其 API 和用例,然后再讨论数据类型的值的所有可能的表示方法以及各种操作的实现。这种模式会在全书中反复出现(且数据结构会越来越复杂)。这里的实现是下文所有实现的模板,值得仔细研究。

评论

发布