1.3 背包、队列和栈
许多基础数据类型都和对象的集合有关。具体来说，数据类型的值就是一组对象的集合，所有操作都是关于添加、删除或是访问集合中的对象。
在本节中，我们将学习三种这样的数据类型，分别是背包（Bag）、队列（Queue）和栈（Stack）。它们的不同之处在于删除或者访问对象的顺序不同。
1.3.1 API
我们对集合型的抽象数据类型的讨论从定义它们的API开始.集合类的抽象数据类型的一个关键特性是我们应该可以用它们存储任意类型的数据，泛型能够做到这一点。
1.3.1.1 泛型
泛型，也叫做参数化类型。有了泛型，我们只需要一份API（和一次实现）就能够处理所有类型的数据，甚至是在未来定义的数据类型。
1.3.1.2 自动装箱
自动将一个原始数据类型转换为一个封装类型；自动将一个封装类型转换为一个原始数据类型被称为自动拆箱。
1.3.1.3 可迭代的集合类型
对于许多应用场景，用例的要求只是用某种方式处理集合中的每个元素，或者叫做迭代访问集合中的所有元素。
这种模式非常重要，在 Java 和其他许多语言中它都是一级语言特性。
1.3.1.4 背包（Bag）
背包是一种不支持从中删除元素的集合数据类型。它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素。
1.3.1.5 先进先出队列（Queue）
先进先出队列（或简称队列）是一种基于先进先出（FIFO）策略的集合类型。使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序：使它们入列顺序和出列顺序相同。
1.3.1.6 下压栈（Stack）
下压栈（或简称栈）是一种基于后进先出（LIFO）策略的集合类型。
1.3.1.7 算术表达式求值
E.W.Dijkstra 在 20 世纪 60 年代发明了一个非常简单的算法，用两个栈（一个用于保存运算符，一个用于保存操作数）完成了这个任务。（Dijkstra 的双栈算术表达式求值算法）
1.3.2 集合类数据类型的实现
1.3.2.1 定容栈
作为热身，我们先来看一种表示容量固定的字符串栈的抽象数据类型。
1.3.2.2 泛型
如何才能实现一个泛型的栈呢？把所有的 String 都替换为 Item（类型参数），用于表示用例将会使用的某种具体类型的象征性的占位符。
1.3.2.3 调整数组大小
选择用数组表示栈内容意味着用例必须预先估计栈的最大容量。方法核心是将栈移动到另一个大小不同的数组中。
1.3.2.4 对象游离
我们对 pop() 的实现中，被弹出的元素的引用仍然存在于数组中。这个元素实际上已经是一个孤儿了——它永远也不会再被访问了，但 Java 的垃圾收集器没法知道这一点，除非该引用被覆盖。即使用例已经不再需要这个元素了，数组中的引用仍然可以让它继续存在。这种情况（保存一个不需要的对象的引用）称为游离。
1.3.2.5 迭代
任意可迭代的集合数据类型中我们都需要实现：1. 集合数据类型必须实现一个 iterator() 方法并返回一个 Iterator 对象；Iterator 类必须包含两个方法：hasNext()（返回一个布尔值）和next()（返回集合中的一个泛型元素）。迭代器都是泛型的，因此我们可以使用参数类型 Item 来帮助用例遍历它们指定的任意类型的对象。
1.3.3 链表
定义。链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。在结构化存储数据集时，链表是数组的一种重要的替代方式。
1.3.3.1 结点记录
一个 Node 对象含有两个实例变量，类型分别为 Item（参数类型）和 Node。Item 是一个占位符，表示我们希望用链表处理的任意数据类型（我们将会使用 Java 的泛型使之表示任意引用类型）；Node 类型的实例变量显示了这种数据结构的链式本质。
1.3.3.2 构造链表
链表表示的是一列元素。可以用数组表示同一列元素，不同之处在于，在链表中向序列插入元素或是从序列中删除元素都更方便。
1.3.3.3 在表头插入结点
例如，要在首结点为first 的给定链表开头插入字符串not，我们先将first 保存在oldfirst 中，然后将一个新结点赋予 first，并将它的 item 域设为 not，next 域设为 oldfirst。
1.3.3.4 从表头删除结点
只需将 first 指向 first.next 即可。
1.3.3.5 在表尾插入结点
1.3.3.6 其他位置的插入和删除操作
已经展示了在链表中如何通过若干指令实现以下操作：在表头插入结点；从表头删除结点；在表尾插入结点。其他操作，例如以下几种，就不那么容易实现了：删除指定的结点；在指定结点前插入一个新结点。实现任意插入和删除操作的标准解决方案是使用双向链表，其中每个结点都含有两个链接，分别指向不同的方向。
1.3.3.7 链表的遍历
访问链表中的所有元素也有一个对应的方式：将循环的索引变量 x 初始化为链表的首结点，然后通过 x.item访问和 x 相关联的元素，并将 x 设为 x.next 来访问链表中的下一个结点，如此反复直到 x 为 null 为止。
1.3.3.8 栈的实现
它将栈保存为一条链表，栈的顶部即为表头，实例变量 first 指向栈顶。这样，当使用 push() 压入一个元素时，我们会按照 1.3.3.3 节所讨论的代码将该元素添加在表头；当使用pop() 删除一个元素时，我们会按照 1.3.3.4 节讨论的代码将该元素从表头删除。要实现 size() 方法，我们用实例变量 N 保存元素的个数，在压入元素时将 N 加 1，在弹出元素时将 N 减 1。要实现 isEmpty() 方法，只需检查 first 是否为 null。链表的使用达到了我们的最优设计目标：它可以处理任意类型的数据；所需的空间总是和集合的大小成正比；操作所需的时间总是和集合的大小无关。
1.3.3.9 队列的实现
基于链表数据结构实现 Queue API 也很简单，如算法 1.3 所示。它将队列表示为一条从最早插入的元素到最近插入的元素的链表，实例变量 first 指向队列的开头，实例变量last 指向队列的结尾。这样，要将一个元素入列（enqueue()），我们就将它添加到表尾（请见图 1.3.8 中讨论的代码，但是在链表为空时需要将 first和 last 都指向新结点）；要将一个元素出列（dequeue()），我们就删除表头的结点（代码和Stack 的pop() 方法相同，只是当链表为空时需要更新last 的值）。size() 和 isEmpty() 方法的实现和 Stack 相同。和 Stack 一样，Queue 的实现也使用了泛型参数 Item。Queue 的实现使用的数据结构和 Stack 相同——链表，但它实现了不同的添加和删除元素的算法，这也是用例所看到的后进先出和先进后出的区别所在。
1.3.3.10 背包的实现
用链表数据结构实现我们的 Bag API 只需要将 Stack中的 push() 改名为 add()，并去掉 pop() 的实现即可。Bag 的实现维护了一条链表，用于保存所有通过 add() 添加的元素。size() 和 isEmpty() 方法的代码和 Stack 中的完全相同。
1.3.4 综述
本节中学习的支持泛型和迭代的背包、队列和栈的实现所提供的抽象使我们能够编写简洁的用例程序来操作对象的集合。
深入理解这些抽象数据类型非常重要，原因有三：
- 第一，我们将以这些数据类型为基石构造本书中的其他更高级的数据结构；
- 第二，它们展示了数据结构和算法的关系以及同时满足多个有可能相互冲突的性能目标时所要面对的挑战；
- 第三，我们将要学习的若干算法的实现重点就是需要其中的抽象数据类型能够支持对对象集合的强大操作，这些实现正是我们的起点。
数据结构
我们现在拥有两种表示对象集合的方式，即数组和链表。Java 内置了数组，链表也很容易使用 Java 的标准方法实现。两者都非常基础，常常被称为顺序存储和链式存储。
在本书后面部分，我们会在各种抽象数据类型的实现中将多种方式结归并扩展这些基本的数据结构。其中一种重要的扩展就是各种含有多个链接的数据结构，如二叉树（由含有两个链接的结点组成）；另一个重要的扩展是复合型的数据结构（我们可以使用背包存储栈，用队列存储数组，等等），如，图（用数组的背包表示它）。用这种方式很容易定义任意复杂的数据结构，而我们重点研究抽象数据类型的一个重要原因就是试图控制这种复杂度。（我们在本节中研究背包、队列和栈时描述数据结构和算法的方式是全书的原型。）
识别目标并使用数据抽象解决问题
在研究一个新的应用领域时，我们将会按照以下步骤识别目标并使用数据抽象解决问题：
- 定义 API；
- 根据特定的应用场景开发用例代码；
- 描述一种数据结构（一组值的表示），并在 API 所对应的抽象数据类型的实现中根据它定义类的实例变量；
- 描述算法（实现一组操作的方式），并根据它实现类中的实例方法；
- 分析算法的性能特点。
