1.3背包、队列和栈

1.3背包、队列和栈

        许多基础数据类型都和对象的集合有关。 具体来说，数据类型的值就是一组对象的集合 ，所有操作都是关于添加、删除或是访问集合中的对象 。而背包、队列、和栈。它们的不同之处在于删除或者访问对象的顺序不同。

1.3.1 API

         每份API 都含有一个无参数的构造函数、一个向集合中添加单个元素的方法 、一个测试集合是否为空的方法和一个返回集合大小的方法 。Stack 和Queue 都含有一个能够删除集合中的特定元素的方法 。 除了这些基本内容之外，我们将在以下几节中解释这几份 API 反映出的两种 Java 特性：泛型与迭代 。

1.3.1.1泛型

        集合类的抽象数据类型的一个关键特性是我们应该可以用它们存储任意类型的数据。一种特别的Java 机制能够做到这一点，它被称为泛型，也叫做参数化类型 。 泛型对编程语言的影响非常深刻，许多语言并没有这种机制（包括早期版本的 Java ）。 在这里我们对泛型的使用仅限于一点额外的 Java 语法，非常容易理解 。 在每份 API 中，类名后的＜Item＞记号将 Item 定义为一个类型参数，它是一个象征性的占位符，表示的是用例将会使用的某种具体数据类型 。 可以将 Stack < Item＞理解为某种元素的栈 。 在实现 Stack 时， 我们并不知道 Item 的具体类型，但用例可以用我们的栈处理任意类型的数据，甚至是在我们的实现之后才出现的数据类型 。 在创建栈时，用例会提供一种具体的数据类型：我们可以将 Item 替换为任意引用数据类型（ Item 出现的每个地方都是如此 ）。

        如果尝试向 stack 变量中添加一个 Date 对象（或是任何其他非String类型的数据）或者
向 queue 变量中添加一个String对象（或是任何其他非 Date 类型的数据）， 会得到一个编译时错误 。 如果没有泛型 ，我们必须为需要收集的每种数据类型定义（并实现）不同的 API。 有了泛型，我们只需要一份 API（ 和一次实现）就能够处理所有类型的数据。

1.3.1.2 自动装箱

        类型参数必须被实例化为引用类型 ，因此 Java 有一种特殊机制来使泛型代码能够处理原始数据类型。Java 的封装类型都是原始数据类型所对应的引用类型：Boolean 、Byte 、Character 、Double 、Float 、Integer、Long 和 Short 分别对应着 boolean 、byte 、char 、double 、float、int 、long 和 short 。 在处理赋值语句、方法的参数和算术或逻辑表达式时，Java 会 自动在引用类型和对应原始数据类型之间进行转换 。 在这里，这种转换有助于我们同时使用泛型和原始数据类型 。

        自动将一个原始数据类型转换为一个封装类型被称为自动装箱，自动将一个封装类型转快为一个原始数据类型被称为自动拆箱 。

1.3.1.3 可迭代的集合类型

        对于许多应用场景，用例的要求只是用某种方式处理集合中的每个元素，或者叫做迭代访问集合中的所有元素 。 这种模式非常重要，在 Java 和其他许多语言中它都是一级语言特性（不只是库，编程语言本身就含有特殊的机制来支持它）。 有了它，我们能够写出清晰简洁的代码且不依赖于集合类型的具体实现。

        这种语法叫做foreach 语句 ： 可以将 for语句看做对于集合中的每个交易 t(foreach），执行以下代码段。 这段用例代码不需要知道集合的表示或实现的任何细节，它只想逐个处理集合中的元素。 相同的for语句也可以处理交易的Bag 对象或是任何可迭代的集合。
        Stack 和 Queue 的 API 的唯一不同之处只是它们的名称和方法名 。 在这里，只有自然语言的描述才能说明选择被删除元素（或是在 foreach 语句中下一个被处理的元素）的规则 。 这些规则的差异是 API 的重要组成部分，而且显然对用例代码的开发十分重要 。

1.3.1.4 背包

        背包是一种不支持从中删除元素的集合数据类型一一它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素（用例也可以检查背包是否为空或者获取背包中元素的数量）。 迭代的顺序不确定且与用例无关。 要理解背包的概念，可以想象一个非常喜欢收集弹子球的人 。 他将所有的弹子球都放在一个背包里 ， 一次一个，并且会不时在所有的弹子球中寻找某一颗拥有某种特点的弹子球 。 使用Bag的 API ，用例可以将元素添加进背包并根据需要随时使用 foreach 语句访问所有的元素 。 用例也可以使用栈或是队列，但使用 Bag 可以说明元素的处理顺序不重要 。

1.3.1.5 先进先出队列

        先进先出队列（或简称队列）是一种基于先进先出（ FIFO ）策略的集合类型。按照任务产生的顺序完成它们的策略我们每天都会遇到：在剧院门前排队的人们、在收费站前排队的汽车或是计算机上某种软件中等待处理的任务 。 任何服务性策略的基本原则都是公平 。 在提到公平时大多数人的第一个想法就是应该优先服务等待最久的人，这正是先进先出策略的准则 。 队列是许多日常现象的自然模型，它也是无数应用程序的核心 。 当用例使用 foreach 语句迭代访问队列中的元素时 ，元素的处理顺序就是它们被添加到队列中的顺序 。 在应用程序中使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序 ： 使它们入列顺序和出列顺序相同 。 队列能够将整数按照文件中的顺序放人数组中（如果该顺序并不重要， 也可以使用 Bag 对象）。

1.3.1.6 下压栈

        下压裁（或简称栈）是一种基于后进先出( LIFO ）策略的集合类型，当你的邮件在桌上放成一叠时 ，使用的就是栈。 新邮件来到时你将它们放在最上面，当你有空时你会一封一封地从上到下阅读它们 。 现在人们应付
的纸质品比以前少得多，但计算机上的许多常用程序遵循相同的组织原则 。 例如，许多人仍然用栈的方式存放电子邮件一一在收信时将邮件压入( push ）最顶端 ， 在取信时从最顶端将它们弹出( pop），且第一封一定是最新的邮件（后进，先出）。这种策略的好处是我们能够及时看到感兴趣的邮件 ， 坏处是如果不把栈清空，某些较早的邮件可能永远也不会被阅读 。 你在网上冲浪时很可能会遇到楼的另一个例子 。 点击一个超链接，浏览器会显示一个新的页面（并将它压人一个栈）你可以不断点击超链接井前问新页面，但总是可以通过点击“回退”按钮重新访问以前的页面（从栈中弹出 ）。 栈的后进先 出策略正好能够提供你所需要的行为 。 当用例使用 foreach 语句迭代遍历找中的元素时，元素的处理顺序和它们被压入的顺序正好相反。 在应用程序中使用核迭代器的一个典型原因是在用集合保存元素的同时颠倒它们的相对顺序 。

1.3.1.7 算术表达式求值

(1+2((2+3)* (4* 5)))Java系统如何完成这些运算的？
★ 将操作数压入操作数栈；
★ 将运算符压人运算符栈；
★ 忽略左括号 ；
★ 在遇到右括号时 ，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈 。
        在处理完最后一个右括号之后，操作数栈上只会有一个值，它就是表达式的值。每当算法遇到一个被括号包围并由一个运算符和两个操作数组成的子表达式时，它都将运算符和操作数的计算结果压入操作数枝 。 这样的结果就好像在输入中用这个值代替了该子表达式，因此用这个值代替子表达式得到的结果和原表达式相同 。 我们可以反复应用这个规律并得到一个最终值。

1.3.2 集合类数据类型的实现

1.3.2.1 定容栈

        实现一份 AP I 的第一步就是选择数据的表示方式 。它的实例变量为一个用于保存栈中的元素的数组 a [ ] ， 和一个用于保存栈中的元素数量的整数 N 。 要删除一个元素 ，我们将 N 减1并返回 a[N ］ 。 要添加一个元素， 我们将a [ N ］ 设为新元素并将 N 加1 。 这些操作能够保证以下性质：★ 数组中的元素顺序和它们被插入的顺序相同 ；
★ 当 N 为 0 时栈为空；
★ 栈的顶部位于 a[N-1] （如果栈非空）

1.3.2.2泛型

        Item 是一个类型参数，用于表示用例将会使用的某种具体类型的象征性的占位符 。可以将 FixedCapacityStack<ltem＞理解为某种元素的栈。在实现FixedCapacityStack 时， 我们并不知道 Item 的实际类型，但用例只要能在创建栈时提供具体的数据类型，它就能用栈处理任意数据类型 。 实际的类型必须是引用类型，但用例可以依靠自动装箱将原始数据类型转换为相应的封装类型 。Java 会使用类型参数 Item 来检查类型不匹配的错误一一尽管具体的数据类型还不知道，赋予 Item 类型变量的值也必须是 Item 类型的，等等 。 **而在Java中创建泛型数组是不允许的。**需要使用类型转换 a=(Item[ ]) new Object[cap];

1.3.2.3 调整数组的大小

        选择用数组表示栈 内容意味着用例必须预先估计栈的最大容量。 在 Java 中，数组一旦创建，其大小是无法改变的，因此栈使用的空间只能是这个最大容量的一部分 。 选择大容量的用例在栈为空或几乎为空时会浪费大盐的内存 。

对象游离

        Java 的垃圾收集策略是回收所有无法被访问的对象的内存 。 在我们对 pop （）的实现中 ，被弹出的元素的引用仍然存在于数组中 。 这个元素实际上已经是一个孤儿了一一它永远也不会再被访问 了 ， 但 Java 的垃圾收集据没法知道这一点 ，除非该引用被覆盖 。 即使用例已经不再需要
这个元素了 ， 数组中的引用仍然可以让它继续存在 。 这种情况（保存一个不需要的对象的引用）称为游离。避免对象游离很容易，只需将被弹出的数组元素的值设为 null 即可，这将覆盖无用的引用并使系统可以在用例使用完被弹出的元素后回收它的内存。

1.3.2.5 迭代

在任意可迭代的集合数据类型中我们都需要实现的东西：
★ 集合数据类型必须实现一个 iterator（） 方法并返回一个 Iterator对象 ；
★ Iterator类必须包含两个方法 ：hasNext() （返回一个布尔值）和next() （返回集合中的一个泛型元素）
        迭代器都是泛型的，因此可以使用参数类型Item来帮助用例遍历它们指定的任意类型的对象。什么是迭代器？它是一个实现了 hasNext（）和next() 方法的类的对象。我们无需改变任何用例代码就可以随意切换不同的表示方法 。 更重要的是，从用例的角度来来说，无需知晓类的实现细节用例也能使用迭代 。

1.3.3链表

        链表是一种递归的数据结构 ， 它或者为空（ null ），或者是指向一个结点（ node ）的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。
        在这个定义中，结 点是一个可能含有任意类型数据的抽象实体，它所包含的指向结点的应用显示了它在构造链表之中的作用 。

1.3.3.1 结点记录

        一个 Node 对象含有两个实例变革，类型分别为 Item （参数类型）和 Node 。 我们会在需要使用 Node 类的类中定义它并将它标记为 private ，因为它不是为用例准备的 。 和任意数据类型一样，我们通过 new Node （）触发（无参数的）构造函数来创建一个 Node 类型的对象。 调用的结果是一个指向 Node 对象的引用，它的实例变量均被初始化为 null。Item 是一个占位符，表示我们希望用链表处理的任意数据类型（我们将会使用 Java 的泛型使之表示任意引用类型）；Node 类型的实例变量显示了这种数据结构的链式本质 。 为了强调我们在组织数据时只使用了Node 类，我们没有定义任何方法且会在代码中直接引用实例变量 ： 如果 first 是一个指向某个Node 对象的变量，我们可以使用 first.item 和 first.next 访问它的实例变量 。 这种类型的类有时也被称为记录 。 它们实现的不是抽象数据类型，因为我们会直接使用其实例变量 。 但是在我们的实现中，Node 和它的用例代码都会被封装在相同的类中且无法被该类的用例访问。

1.3.3.2 构造链表

        （注意：third.next仍然是 null，即对象创建时它被初始化的值 。）结果是，third 是一条链表（它是一个结点的引用，且该结点指向null ，即一个空链表）, second 也是一条链表（它是一个结点的引用，且该结点含有一个指向third 的引
用，而 third 是一条链表），first也是一条链表（它是一个结点的引用，且该结点含有一个指向 second 的引用，而 second 是一条链表）。
        链表表示的是一列元素 。 first 表示的序列是 to 、be 、of。 我们也可以用一个数组来表示一列元素 。

1.3.3.3 在表头插入结点

1.3.3.4 从表头删除结点

        假设希望删除一条链表的首结点 。 这个操作更简单：只需将 first 指向 first.next 即可 。 一般来说可能会希望在赋值之前得到该元素的值，因为一旦改变了 first 的值，就再也无法访问它曾经指向的结点了 。 曾经的结点对象变成了一个孤儿 ，Java 的内存管理系统最终将回收它所占用的内存。 和以前一样 ， 这个操作只含有一条赋值语句，因此它的运行时间和链表的长度无关。