1.3 背包、队列和栈
Robert Sedgewick Kevin Wayne
许多基础数据类型都和对象的集合有关。具体来说，数据类型的值就是一组对象的集合，所有操作都是关于添加、删除或是访问集合中的对象。在本节中，我们将学习三种这样的数据类型，分别是背包（Bag）、队列（Queue）和栈（Stack）。它们的不同之处在于删除或者访问对象的顺序不同。
背包、队列和栈数据类型都非常基础并且应用广泛。我们在本书的各种实现中也会不断用到它们。除了这些应用以外，本节中的实现和用例代码也展示了我们开发数据结构和算法的一般方式。
本节的第一个目标是说明我们对集合中的对象的表示方式将直接影响各种操作的效率。对于集合来说，我们将会设计适于表示一组对象的数据结构并高效地实现所需的方法。
本节的第二个目标是介绍泛型和迭代。它们都是简单的 Java 概念，但能极大地简化用例代码。它们是高级的编程语言机制，虽然对于算法的理解并不是必需的，但有了它们我们能够写出更加清晰、简洁和优美的用例（以及算法的实现）代码。
本节的第三个目标是介绍并说明链式数据结构的重要性，特别是经典数据结构链表，有了它我们才能高效地实现背包、队列和栈。理解链表是学习各种算法和数据结构中最关键的第一步。
对于这三种数据结构，我们都会学习其 API 和用例，然后再讨论数据类型的值的所有可能的表示方法以及各种操作的实现。这种模式会在全书中反复出现（且数据结构会越来越复杂）。这里的实现是下文所有实现的模板，值得仔细研究。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了Java中背包、队列和栈这三种基础数据类型的实现及其API和用例。通过泛型，这些数据类型能够处理任意类型的数据，使得用例代码更加清晰、简洁和优美。文章还介绍了自动装箱和自动拆箱的概念，以及它们在处理原始数据类型和泛型之间的转换中的应用。对于理解数据结构和算法的实现方式以及Java编程语言的特性都具有重要意义。此外，文章还强调了链式数据结构的重要性，特别是链表的应用。通过具体的代码示例和图示，读者可以更直观地理解背包、队列和栈的操作特点和应用场景。此外，文章还介绍了Dijkstra的双栈算术表达式求值算法，展示了栈在计算机领域中的重要性。总体而言，本文内容涵盖了数据结构的基础知识和Java编程语言的特性，对于初学者和有一定编程基础的读者都具有一定的参考价值。文章通过详细的代码示例和清晰的解释，为读者提供了深入理解数据结构和算法实现的重要参考资料。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《算法（第 4 版）》
《算法（第 4 版）》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论