- 算法（第4版）
- (美)Robert Sedgewick Kevin Wayne
- 21904字
- 2021-03-31 13:02:36
1.3 背包、队列和栈
许多基础数据类型都和对象的集合有关。具体来说，数据类型的值就是一组对象的集合，所有操作都是关于添加、删除或是访问集合中的对象。在本节中，我们将学习三种这样的数据类型，分别是背包（Bag）、队列（Queue）和栈（Stack）。它们的不同之处在于删除或者访问对象的顺序不同。
背包、队列和栈数据类型都非常基础并且应用广泛。我们在本书的各种实现中也会不断用到它们。除了这些应用以外，本节中的实现和用例代码也展示了我们开发数据结构和算法的一般方式。
本节的第一个目标是说明我们对集合中的对象的表示方式将直接影响各种操作的效率。对于集合来说，我们将会设计适于表示一组对象的数据结构并高效地实现所需的方法。
本节的第二个目标是介绍泛型和迭代。它们都是简单的Java概念，但能极大地简化用例代码。它们是高级的编程语言机制，虽然对于算法的理解并不是必需的，但有了它们我们能够写出更加清晰、简洁和优美的用例（以及算法的实现）代码。
本节的第三个目标是介绍并说明链式数据结构的重要性，特别是经典数据结构链表，有了它我们才能高效地实现背包、队列和栈。理解链表是学习各种算法和数据结构中最关键的第一步。
对于这三种数据结构，我们都会学习其API和用例，然后再讨论数据类型的值的所有可能的表示方法以及各种操作的实现。这种模式会在全书中反复出现（且数据结构会越来越复杂）。这里的实现是下文所有实现的模板，值得仔细研究。
1.3.1 API
照例，我们对集合型的抽象数据类型的讨论从定义它们的API开始，如表1.3.1所示。每份API都含有一个无参数的构造函数、一个向集合中添加单个元素的方法、一个测试集合是否为空的方法和一个返回集合大小的方法。Stack和Queue都含有一个能够删除集合中的特定元素的方法。除了这些基本内容之外，我们将在以下几节中解释这几份API反映出的两种Java特性：泛型与迭代。
表1.3.1 泛型可迭代的基础集合数据类型的API
1.3.1.1 泛型
集合类的抽象数据类型的一个关键特性是我们应该可以用它们存储任意类型的数据。一种特别的Java机制能够做到这一点，它被称为泛型，也叫做参数化类型。泛型对编程语言的影响非常深刻，许多语言并没有这种机制（包括早期版本的Java）。在这里我们对泛型的使用仅限于一点额外的Java语法，非常容易理解。在每份API中，类名后的＜Item＞记号将Item定义为一个类型参数，它是一个象征性的占位符，表示的是用例将会使用的某种具体数据类型。可以将Stack＜Item＞理解为某种元素的栈。在实现Stack时，我们并不知道Item的具体类型，但用例可以用我们的栈处理任意类型的数据，甚至是在我们的实现之后才出现的数据类型。在创建栈时，用例会提供一种具体的数据类型：我们可以将Item替换为任意引用数据类型（Item出现的每个地方都是如此）。这种能力正是我们所需要的。例如，可以编写如下代码来用栈处理String对象：
Stack＜String＞ stack = new Stack＜String＞();
stack.push("Test");
...
String next = stack.pop();
并在以下代码中使用队列处理Date对象：
Queue＜Date＞ queue = new Queue＜Date＞(); queue.enqueue(new Date(12, 31, 1999)); ... Date next = queue.dequeue();
如果你尝试向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会自动在引用类型和对应的原始数据类型之间进行转换。在这里，这种转换有助于我们同时使用泛型和原始数据类型。例如：
Stack＜Integer＞ stack = new Stack＜Integer＞(); stack.push(17); // 自动装箱 (int -＞ Integer) int i = stack.pop(); // 自动拆箱 (Integer -＞ int)
自动将一个原始数据类型转换为一个封装类型被称为自动装箱，自动将一个封装类型转换为一个原始数据类型被称为自动拆箱。在这个例子中，当我们将一个原始类型的值17传递给push()方法时，Java将它的类型自动转换（自动装箱）为Integer。pop()方法返回了一个Integer类型的值，Java在将它赋予变量i之前将它的类型自动转换（自动拆箱）为了int。
1.3.1.3 可迭代的集合类型
对于许多应用场景，用例的要求只是用某种方式处理集合中的每个元素，或者叫做迭代访问集合中的所有元素。这种模式非常重要，在Java和其他许多语言中它都是一级语言特性（不只是库，编程语言本身就含有特殊的机制来支持它）。有了它，我们能够写出清晰简洁的代码且不依赖于集合类型的具体实现。例如，假设用例在Queue中维护一个交易集合，如下：
Queue＜Transaction＞ collection = new Queue＜Transaction＞();
如果集合是可迭代的，用例用一行语句即可打印出交易的列表：
for (Transaction t : collection)
{ StdOut.println(t); }
这种语法叫做foreach语句：可以将for语句看做对于集合中的每个交易t(foreach)，执行以下代码段。这段用例代码不需要知道集合的表示或实现的任何细节，它只想逐个处理集合中的元素。相同的for语句也可以处理交易的Bag对象或是任何可迭代的集合。很难想象还有比这更加清晰和简洁的代码。你将会看到，支持这种迭代需要在实现中添加额外的代码，但这些工作是值得的。
有趣的是，Stack和Queue的API的唯一不同之处只是它们的名称和方法名。这让我们认识到无法简单地通过一列方法的签名说明一个数据类型的所有特点。在这里，只有自然语言的描述才能说明选择被删除元素（或是在foreach语句中下一个被处理的元素）的规则。这些规则的差异是API的重要组成部分，而且显然对用例代码的开发十分重要。
1.3.1.4 背包
背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素（用例也可以检查背包是否为空或者获取背包中元素的数量）。迭代的顺序不确定且与用例无关。要理解背包的概念，可以想象一个非常喜欢收集弹子球的人。他将所有的弹子球都放在一个背包里，一次一个，并且会不时在所有的弹子球中寻找某一颗拥有某种特点的弹子球。使用Bag的API，用例可以将元素添加进背包并根据需要随时使用foreach语句访问所有的元素。用例也可以使用栈或是队列，但使用Bag可以说明元素的处理顺序不重要。下面代码框所示的Stats类是Bag的一个典型用例。它的任务是简单地计算标准输入中的所有double值的平均值和样本标准差。如果标准输入中有N个数字，那么平均值为它们的和除以N，样本标准差为每个值和平均值之差的平方之和除以N-1之后的平方根。在这些计算中，数的计算顺序和结果无关，因此我们将它们保存在一个Bag对象中并使用foreach语法来计算每个和。注意：不需要保存所有的数也可以计算标准差（就像我们在Accumulator中计算平均值那样——请见练习1.2.18）。用Bag对象保存所有数字是更复杂的统计计算所必需的。
图1.3.1 背包的操作（另见彩插）
以下代码框列出的是常用的背包用例。
背包的典型用例
public class Stats
{
public static void main(String[] args)
{
Bag＜Double＞ numbers = new Bag＜Double＞();
while (! StdIn.isEmpty())
numbers.add(StdIn.readDouble());
int N = numbers.size();
double sum = 0.0;
for (double x : numbers)
sum += x;
double mean = sum/N;
sum = 0.0;
for (double x : numbers)
sum += (x - mean)＊(x - mean);
double std = Math.sqrt(sum/(N-1));
StdOut.printf("Mean: %.2f\n", mean);
StdOut.printf("Std dev: %.2f\n", std);
}
}
使用方法
% java Stats 100 99 101 120 98 107 109 81 101 90 Mean: 100.60 Std dev: 10.51
1.3.1.5 先进先出队列
先进先出队列（或简称队列）是一种基于先进先出（FIFO）策略的集合类型，如图1.3.2所示。按照任务产生的顺序完成它们的策略我们每天都会遇到：在剧院门前排队的人们、在收费站前排队的汽车或是计算机上某种软件中等待处理的任务。任何服务性策略的基本原则都是公平。在提到公平时大多数人的第一个想法就是应该优先服务等待最久的人，这正是先进先出策略的准则。队列是许多日常现象的自然模型，它也是无数应用程序的核心。当用例使用foreach语句迭代访问队列中的元素时，元素的处理顺序就是它们被添加到队列中的顺序。在应用程序中使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序：使它们入列顺序和出列顺序相同。例如，下页的用例是我们的In类的静态方法readInts()的一种实现。这个方法为用例解决的问题是用例无需预先知道文件的大小即可将文件中的所有整数读入一个数组中。我们首先将所有的整数读入队列中，然后使用Queue的size()方法得到所需数组的大小，创建数组并将队列中的所有整数移动到数组中。队列之所以合适是因为它能够将整数按照文件中的顺序放入数组中（如果该顺序并不重要，也可以使用Bag对象）。这段代码使用了自动装箱和拆箱来转换用例中的int原始数据类型和队列的Integer封装类型。
图1.3.2 一个典型的先进先出队列
Queue的用例
1.3.1.6 下压栈
下压栈（或简称栈）是一种基于后进先出（LIFO）策略的集合类型，如图1.3.3所示。当你的邮件在桌上放成一叠时，使用的就是栈。新邮件来到时你将它们放在最上面，当你有空时你会一封一封地从上到下阅读它们。现在人们应付的纸质品比以前少得多，但计算机上的许多常用程序遵循相同的组织原则。例如，许多人仍然用栈的方式存放电子邮件——在收信时将邮件压入（push）最顶端，在取信时从最顶端将它们弹出（pop），且第一封一定是最新的邮件（后进，先出）。这种策略的好处是我们能够及时看到感兴趣的邮件，坏处是如果你不把栈清空，某些较早的邮件可能永远也不会被阅读。你在网上冲浪时很可能会遇到栈的另一个例子。点击一个超链接，浏览器会显示一个新的页面（并将它压入一个栈）。你可以不断点击超链接并访问新页面，但总是可以通过点击“回退”按钮重新访问以前的页面（从栈中弹出）。栈的后进先出策略正好能够提供你所需要的行为。当用例使用foreach语句迭代遍历栈中的元素时，元素的处理顺序和它们被压入的顺序正好相反。在应用程序中使用栈迭代器的一个典型原因是在用集合保存元素的同时颠倒它们的相对顺序。例如，右侧的用例Reverse将会把标准输入中的所有整数逆序排列，同样它也无需预先知道整数的多少。在计算机领域，栈具有基础而深远的影响，下一节我们会仔细研究一个例子，以说明栈的重要性。
图1.3.3 下压栈的操作
1.3.1.7 算术表达式求值
我们要学习的另一个栈用例同时也是展示泛型的应用的一个经典例子。我们在1.1节中最初学习的几个程序之一就是用来计算算术表达式的值的，例如：
Stack的用例
( 1 + ( ( 2 + 3 ) ＊ ( 4 ＊ 5 ) ) )
如果将4乘以5，把3加上2，取它们的积然后加1，就得到了101。但Java系统是如何完成这些运算的呢？不需要研究Java系统的构造细节，我们也可以编写一个Java程序来解决这个问题。它接受一个输入字符串（表达式）并输出表达式的值。为了简化问题，首先来看一下这份明确的递归定义：算术表达式可能是一个数，或者是由一个左括号、一个算术表达式、一个运算符、另一个算术表达式和一个右括号组成的表达式。简单起见，这里定义的是未省略括号的算术表达式，它明确地说明了所有运算符的操作数——你可能更熟悉形如1 + 2 ＊ 3的表达式，省略了括号，而采用优先级规则。我们将要学习的简单机制也能处理优先级规则，但在这里我们不想把问题复杂化。为了突出重点，我们支持最常见的二元运算符＊、+、-和/，以及只接受一个参数的平方根运算符sqrt。我们也可以轻易支持更多数量和种类的运算符来计算多种大家熟悉的数学表达式，包括三角函数、指数和对数函数。我们的重点在于如何解析由括号、运算符和数字组成的字符串，并按照正确的顺序完成各种初级算术运算操作。如何才能够得到一个（由字符串表示的）算术表达式的值呢？E.W.Dijkstra在20世纪60年代发明了一个非常简单的算法，用两个栈（一个用于保存运算符，一个用于保存操作数）完成了这个任务，其实现过程见下页，求值算法的轨迹如图1.3.4所示。
图1.3.4 Dijkstra的双栈算术表达式求值算法的轨迹
表达式由括号、运算符和操作数（数字）组成。我们根据以下4种情况从左到右逐个将这些实体送入栈处理：
❏将操作数压入操作数栈；
❏将运算符压入运算符栈；
❏忽略左括号；
❏在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。
在处理完最后一个右括号之后，操作数栈上只会有一个值，它就是表达式的值。这种方法乍一看有些难以理解，但要证明它能够计算得到正确的值很简单：每当算法遇到一个被括号包围并由一个运算符和两个操作数组成的子表达式时，它都将运算符和操作数的计算结果压入操作数栈。这样的结果就好像在输入中用这个值代替了该子表达式，因此用这个值代替子表达式得到的结果和原表达式相同。我们可以反复应用这个规律并得到一个最终值。例如，用该算法计算以下表达式得到的结果都是相同的：
( 1 + ( ( 2 + 3 ) ＊ ( 4 ＊ 5 ) ) ) ( 1 + ( 5 ＊ ( 4 ＊ 5 ) ) ) ( 1 + ( 5 ＊ 20 ) ) ( 1 + 100 ) 101
本页中的Evaluate类是该算法的一个实现。这段代码是一个简单的“解释器”：一个能够解释给定字符串所表达的运算并计算得到结果的程序。
Dijkstra的双栈算术表达式求值算法
public class Evaluate
{
public static void main(String[] args)
{
Stack＜String＞ ops = new Stack＜String＞();
Stack＜Double＞ vals = new Stack＜Double＞();
while (! StdIn.isEmpty())
{ // 读取字符，如果是运算符则压入栈
String s = StdIn.readString();
if (s.equals("(")) ;
else if (s.equals("+")) ops.push(s);
else if (s.equals("-")) ops.push(s);
else if (s.equals("＊")) ops.push(s);
else if (s.equals("/")) ops.push(s);
else if (s.equals("sqrt")) ops.push(s);
else if (s.equals(")"))
{ // 如果字符为")"，弹出运算符和操作数，计算结果并压入栈
String op = ops.pop();
double v = vals.pop();
if (op.equals("+")) v = vals.pop() + v;
else if (op.equals("-")) v = vals.pop() - v;
else if (op.equals("＊")) v = vals.pop() ＊ v;
else if (op.equals("/")) v = vals.pop() / v;
else if (op.equals("sqrt")) v = Math.sqrt(v);
vals.push(v);
} // 如果字符既非运算符也不是括号，将它作为double值压入栈
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}
这段Stack的用例使用了两个栈来计算表达式的值。它展示了一种重要的计算模型：将一个字符串解释为一段程序并执行该程序得到结果。有了泛型，我们只需实现Stack一次即可使用String值的栈和Double值的栈。简单起见，这段代码假设表达式没有省略任何括号，数字和字符均以空白字符相隔。
1.3.2 集合类数据类型的实现
在讨论Bag、Stack和Queue的实现之前，我们会先给出一个简单而经典的实现，然后讨论它的改进并得到表1.3.1中的API的所有实现。
1.3.2.1 定容栈
作为热身，我们先来看一种表示容量固定的字符串栈的抽象数据类型，如表1.3.2所示。它的API和Stack的API有所不同：它只能处理String值，它要求用例指定一个容量且不支持迭代。实现一份API的第一步就是选择数据的表示方式。对于FixedCapacityStackOfStrings，我们显然可以选择String数组。由此我们可以得到表1.3.2中底部的实现，它已经是简单得不能再简单了（每个方法都只有一行）。它的实例变量为一个用于保存栈中的元素的数组a[]，和一个用于保存栈中的元素数量的整数N。要删除一个元素，我们将N减1并返回a[N]。要添加一个元素，我们将a[N]设为新元素并将N加1。这些操作能够保证以下性质：
表1.3.2 一种表示定容字符串栈的抽象数据类型
❏数组中的元素顺序和它们被插入的顺序相同；
❏当N为0时栈为空；
❏栈的顶部位于a[N-1]（如果栈非空）。
和以前一样，用恒等式的方式思考这些条件是检验实现正常工作的最简单的方式。请你务必完全理解这个实现。做到这一点的最好方法是检验一系列操作中栈内容的轨迹，如表1.3.3所示。测试用例会从标准输入读取多个字符串并将它们压入一个栈，当遇到-时它会将栈的内容弹出并打印结果。这种实现的主要性能特点是push和pop操作所需的时间独立于栈的长度。许多应用会因为这种简洁性而选择它。但几个缺点限制了它作为通用工具的潜力，我们要改进的也是这一点。经过一些修改（以及Java语言机制的一些帮助），我们就能给出一个适用性更加广泛的实现。这些努力是值得的，因为这个实现是本书中其他许多更强大的抽象数据类型的模板。
表1.3.3 FixedCapacityStackOfStrings的测试用例的轨迹
1.3.2.2 泛型
FixedCapacityStackOfStrings的第一个缺点是它只能处理String对象。如果需要一个double值的栈，你就需要用类似的代码实现另一个类，也就是把所有的String都替换为double。这还算简单，但如果我们需要Transaction类型的栈或者Date类型的队列等，情况就很棘手了。如1.3.1.1节的讨论所示，Java的参数类型（泛型）就是专门用来解决这个问题的，而且我们也看过了几个用例的代码（请见1.3.1.4节、1.3.1.5节、1.3.1.6节和1.3.1.7节）。但如何才能实现一个泛型的栈呢？表1.3.4中的代码展示了实现的细节。它实现了一个FixedCapacityStack类，该类和FixedCapacityStackOfStrings类的区别仅在于加粗部分的代码——我们把所有的String都替换为Item（一个地方除外，会在稍后讨论）并用下面这行代码声明了该类：
表1.3.4 一种表示泛型定容栈的抽象数据类型
public class FixedCapacityStack＜Item＞
Item是一个类型参数，用于表示用例将会使用的某种具体类型的象征性的占位符。可以将FixedCapacityStack＜Item＞理解为某种元素的栈，这正是我们想要的。在实现FixedCapacityStack时，我们并不知道Item的实际类型，但用例只要能在创建栈时提供具体的数据类型，它就能用栈处理任意数据类型。实际的类型必须是引用类型，但用例可以依靠自动装箱将原始数据类型转换为相应的封装类型。Java会使用类型参数Item来检查类型不匹配的错误——尽管具体的数据类型还不知道，赋予Item类型变量的值也必须是Item类型的，等等。在这里有一个细节非常重要：我们希望用以下代码在FixedCapacityStack的构造函数的实现中创建一个泛型的数组：
a = new Item[cap];
由于某些历史和技术原因（不在本书讲解范围之内），创建泛型数组在Java中是不允许的。我们需要使用类型转换：
a = (Item[]) new Object[cap];
这段代码才能够达到我们所期望的效果（但Java编译器会给出一条警告，不过可以忽略它），我们在本书中会一直使用这种方式（Java系统库中类似抽象数据类型的实现中也使用了相同的方式）。
1.3.2.3 调整数组大小
选择用数组表示栈内容意味着用例必须预先估计栈的最大容量。在Java中，数组一旦创建，其大小是无法改变的，因此栈使用的空间只能是这个最大容量的一部分。选择大容量的用例在栈为空或几乎为空时会浪费大量的内存。例如，一个交易系统可能会涉及数十亿笔交易和数千个交易的集合。即使这种系统一般都会限制每笔交易只能出现在一个集合中，但用例必须保证所有集合都有能力保存所有的交易。另一方面，如果集合变得比数组更大那么用例有可能溢出。为此，push()方法需要在代码中检测栈是否已满，我们的API中也应该含有一个isFull()方法来允许用例检测栈是否已满。我们在此省略了它的实现代码，因为我们希望用例从处理栈已满的问题中解脱出来，如我们的原始Stack API所示。因此，我们修改了数组的实现，动态调整数组a[]的大小，使得它既足以保存所有元素，又不至于浪费过多的空间。实际上，完成这些目标非常简单。首先，实现一个方法将栈移动到另一个大小不同的数组中：
private void resize(int max)
{ // 将大小为N ＜ = max的栈移动到一个新的大小为max的数组中
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i ＜ N; i++)
temp[i] = a[i];
a = temp;
}
现在，在push()中，检查数组是否太小。具体来说，我们会通过检查栈大小N和数组大小a.length是否相等来检查数组是否能够容纳新的元素。如果没有多余的空间，我们会将数组的长度加倍。然后就可以和从前一样用a[N++] = item插入新元素了：
public void push(Item item)
{ // 将元素压入栈顶
if (N == a.length) resize(2＊a.length);
a[N++] = item;
}
类似，在pop()中，首先删除栈顶的元素，然后如果数组太大我们就将它的长度减半。只要稍加思考，你就明白正确的检测条件是栈大小是否小于数组的四分之一。在数组长度被减半之后，它的状态约为半满，在下次需要改变数组大小之前仍然能够进行多次push()和pop()操作。
public Item pop()
{ // 从栈顶删除元素
Item item = a[--N];
a[N] = null; // 避免对象游离（请见下节）
if (N ＞ 0 && N == a.length/4) resize(a.length/2);
return item;
}
在这个实现中，栈永远不会溢出，使用率也永远不会低于四分之一（除非栈为空，那种情况下数组的大小为1）。我们会在1.4节中详细分析这种实现方法的性能特点。
push()和pop()操作中数组大小调整的轨迹见表1.3.5。
表1.3.5 一系列push()和pop()操作中数组大小调整的轨迹
1.3.2.4 对象游离
Java的垃圾收集策略是回收所有无法被访问的对象的内存。在我们对pop()的实现中，被弹出的元素的引用仍然存在于数组中。这个元素实际上已经是一个孤儿了——它永远也不会再被访问了，但Java的垃圾收集器没法知道这一点，除非该引用被覆盖。即使用例已经不再需要这个元素了，数组中的引用仍然可以让它继续存在。这种情况（保存一个不需要的对象的引用）称为游离。在这里，避免对象游离很容易，只需将被弹出的数组元素的值设为null即可，这将覆盖无用的引用并使系统可以在用例使用完被弹出的元素后回收它的内存。
1.3.2.5 迭代
本节开头已经提过，集合类数据类型的基本操作之一就是，能够使用Java的foreach语句通过迭代遍历并处理集合中的每个元素。这种方式的代码既清晰又简洁，且不依赖于集合数据类型的具体实现。在讨论迭代的实现之前，我们先看一段能够打印出一个字符串集合中的所有元素的用例代码：
Stack＜String＞ collection = new Stack＜String＞();
...
for (String s : collection)
StdOut.println(s);
...
这里，foreach语句只是while语句的一种简写方式（就好像for语句一样）。它本质上和以下while语句是等价的：
Iterator＜String＞ i = collection.iterator();
while (i.hasNext())
{
String s = i.next();
StdOut.println(s);
}
这段代码展示了一些在任意可迭代的集合数据类型中我们都需要实现的东西：
❏集合数据类型必须实现一个iterator()方法并返回一个Iterator对象；
❏ Iterator类必须包含两个方法：hasNext()（返回一个布尔值）和next()（返回集合中的一个泛型元素）。
在Java中，我们使用接口机制来指定一个类所必须实现的方法（请见1.2.5.4节）。对于可迭代的集合数据类型，Java已经为我们定义了所需的接口。要使一个类可迭代，第一步就是在它的声明中加入implements Iterable＜Item＞，对应的接口（即java.lang.Iterable）为：
public interface Iterable＜Item＞
{
Iterator＜Item＞ iterator();
}
然后在类中添加一个方法iterator()并返回一个迭代器Iterator＜Item＞。迭代器都是泛型的，因此我们可以使用参数类型Item来帮助用例遍历它们指定的任意类型的对象。对于一直使用的数组表示法，我们需要逆序迭代遍历这个数组，因此我们将迭代器命名为ReverseArrayIterator，并添加了以下方法：
public Iterator＜Item＞ iterator()
{ return new ReverseArrayIterator(); }
迭代器是什么？它是一个实现了hasNext()和next()方法的类的对象，由以下接口所定义（即java.util.Iterator）：
public interface Iterator＜Item＞
{
boolean hasNext();
Item next();
void remove();
}
尽管接口指定了一个remove()方法，但在本书中remove()方法总为空，因为我们希望避免在迭代中穿插能够修改数据结构的操作。对于ReverseArrayIterator，这些方法都只需要一行代码，它们实现在栈类的一个嵌套类中：
private class ReverseArrayIterator implements Iterator＜Item＞
{
private int i = N;
public boolean hasNext() { return i ＞ 0; }
public Item next() { return a[--i]; }
public void remove() { }
}
请注意，嵌套类可以访问包含它的类的实例变量，在这里就是a[]和N（这也是我们使用嵌套类实现迭代器的主要原因）。从技术角度来说，为了和Iterator的结构保持一致，我们应该在两种情况下抛出异常：如果用例调用了remove()则抛出UnsupportedOperationException，如果用例在调用next()时i为0则抛出NoSuchElementException。因为我们只会在foreach语法中使用迭代器，这些情况都不会出现，所以我们省略了这部分代码。还剩下一个非常重要的细节，我们需要在程序的开头加上下面这条语句：
import java.util.Iterator;
因为（某些历史原因）Iterator不在java.lang中（尽管Iterable是java.lang的一部分）。现在，使用foreach处理该类的用例能够得到的行为和使用普通的for循环访问数组一样，但它无须知道数据的表示方法是数组（即实现细节）。对于我们在本书中学习的和Java库中所包含的所有类似于集合的基础数据类型的实现，这一点非常重要。例如，我们无需改变任何用例代码就可以随意切换不同的表示方法。更重要的是，从用例的角度来来说，无需知晓类的实现细节用例也能使用迭代。
算法1.1是Stack API的一种能够动态改变数组大小的实现。用例能够创建任意类型数据的栈，并支持用例用foreach语句按照后进先出的顺序迭代访问所有栈元素。这个实现的基础是Java的语言特性，包括Iterable和Iterator，但我们没有必要深究这些特性的细节，因为代码本身并不复杂，并且可以用做其他集合数据类型的实现的模板。
例如，我们在实现Queue的API时，可以使用两个实例变量作为索引，一个变量head指向队列的开头，一个变量tail指向队列的结尾，如表1.3.6所示。在删除一个元素时，使用head访问它并将head加1；在插入一个元素时，使用tail保存它并将tail加1。如果某个索引在增加之后越过了数组的边界则将它重置为0。实现检查队列是否为空、是否充满并需要调整数组大小的细节是一项有趣而又实用的编程练习（请见练习1.3.14）。
表1.3.6 ResizingArrayQueue的测试用例的轨迹
在算法的学习中，算法1.1十分重要，因为它几乎（但还没有）达到了任意集合类数据类型的实现的最佳性能：
❏每项操作的用时都与集合大小无关；
❏空间需求总是不超过集合大小乘以一个常数。
ResizingArrayStack的缺点在于某些push()和pop()操作会调整数组的大小：这项操作的耗时和栈大小成正比。下面，我们将学习一种克服该缺陷的方法，使用一种完全不同的方式来组织数据。
算法1.1下压（LIFO）栈（能够动态调整数组大小的实现）
import java.util.Iterator;
public class ResizingArrayStack＜Item＞ implements Iterable＜Item＞
{
private Item[] a = (Item[]) new Object[1]; // 栈元素
private int N = 0; // 元素数量
public boolean isEmpty() { return N == 0; }
public int size() { return N; }
private void resize(int max)
{ // 将栈移动到一个大小为max的新数组
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i ＜ N; i++)
temp[i] = a[i];
a = temp;
}
public void push(Item item)
{ // 将元素添加到栈顶
if (N == a.length) resize(2＊a.length);
a[N++] = item;
}
public Item pop()
{ // 从栈顶删除元素
Item item = a[--N];
a[N] = null; // 避免对象游离（请见1.3.2.4节）
if (N ＞ 0 && N == a.length/4) resize(a.length/2);
return item;
}
public Iterator＜Item＞ iterator()
{ return new ReverseArrayIterator(); }
private class ReverseArrayIterator implements Iterator＜Item＞
{ // 支持后进先出的迭代
private int i = N;
public boolean hasNext() { return i ＞ 0; }
public Item next() { return a[--i]; }
public void remove() { }
}
}
这份泛型的可迭代的Stack API的实现是所有集合类抽象数据类型实现的模板。它将所有元素保存在数组中，并动态调整数组的大小以保持数组大小和栈大小之比小于一个常数。
1.3.3 链表
现在我们来学习一种基础数据结构的使用，它是在集合类的抽象数据类型实现中表示数据的合适选择。这是我们构造非Java直接支持的数据结构的第一个例子。我们的实现将成为本书中其他更加复杂的数据结构的构造代码的模板。所以请仔细阅读本节，即使你已经使用过链表。
定义。链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。
在这个定义中，结点是一个可能含有任意类型数据的抽象实体，它所包含的指向结点的应用显示了它在构造链表之中的作用。和递归程序一样，递归数据结构的概念一开始也令人费解，但其实它的简洁性赋予了它巨大的价值。
1.3.3.1 结点记录
在面向对象编程中，实现链表并不困难。我们首先用一个嵌套类来定义结点的抽象数据类型：
private class Node
{
Item item;
Node next;
}
一个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 构造链表
现在，根据递归定义，我们只需要一个Node类型的变量就能表示一条链表，只要保证它的值是null或者指向另一个Node对象且该对象的next域指向了另一条链表即可。例如，要构造一条含有元素to、be和or的链表，我们首先为每个元素创造一个结点：
Node first = new Node(); Node second = new Node(); Node third = new Node();
并将每个结点的item域设为所需的值（简单起见，我们假设在这些例子中Item为String）：
first.item = "to"; second.item = "be"; third.item = "or";
然后设置next域来构造链表：
first.next = second; second.next = third;
（注意：third.next仍然是null，即对象创建时它被初始化的值。）结果是，third是一条链表（它是一个结点的引用，该结点指向null，即一个空链表）, second也是一条链表（它是一个结点的引用，且该结点含有一个指向third的引用，而third是一条链表）, first也是一条链表（它是一个结点的引用，且该结点含有一个指向second的引用，而second是一条链表）。图1.3.5所示的代码以不同的顺序完成了这些赋值语句。
图1.3.5 用链接构造一条链表
链表表示的是一列元素。在我们刚刚考察过的例子中，first表示的序列是to、be、or。我们也可以用一个数组来表示一列元素。例如，可以用以下数组表示同一列字符串：
String[] s = { "to", "be", "or" };
不同之处在于，在链表中向序列插入元素或是从序列中删除元素都更方便。下面，我们来学习完成这些任务的代码。
在追踪使用链表和其他链式结构的代码时，我们会使用可视化表示方法：
❏用长方形表示对象；
❏将实例变量的值写在长方形中；
❏用指向被引用对象的箭头表示引用关系。
这种表示方式抓住了链表的关键特性。方便起见，我们用术语链接表示对结点的引用。简单起见，当元素的值为字符串时（如我们的例子所示），我们会将字符串写在长方形之内，而非使用1.2节中所讨论的更准确的方式表示字符串对象和字符数组。这种可视化的表示方式使我们能够将注意力集中在链表上。
1.3.3.3 在表头插入结点
首先，假设你希望向一条链表中插入一个新的结点。最容易做到这一点的地方就是链表的开头。例如，要在首结点为first的给定链表开头插入字符串not，我们先将first保存在oldfirst中，然后将一个新结点赋予first，并将它的item域设为not, next域设为oldfirst。以上过程如图1.3.6所示。这段在链表开头插入一个结点的代码只需要几行赋值语句，所以它所需的时间和链表的长度无关。
图1.3.6 在链表的开头插入一个新结点
1.3.3.4 从表头删除结点
接下来，假设你希望删除一条链表的首结点。这个操作更简单：只需将first指向first. next即可。一般来说你可能会希望在赋值之前得到该元素的值，因为一旦改变了first的值，就再也无法访问它曾经指向的结点了。曾经的结点对象变成了一个孤儿，Java的内存管理系统最终将回收它所占用的内存。和以前一样，这个操作只含有一条赋值语句，因此它的运行时间和链表的长度无关。此过程如图1.3.7所示。
图1.3.7 删除链表的首结点
1.3.3.5 在表尾插入结点
如何才能在链表的尾部添加一个新结点？要完成这个任务，我们需要一个指向链表最后一个结点的链接，因为该结点的链接必须被修改并指向一个含有新元素的新结点。我们不能在链表代码中草率地决定维护一个额外的链接，因为每个修改链表的操作都需要添加检查是否要修改该变量（以及作出相应修改）的代码。例如，我们刚刚讨论过的删除链表首结点的代码就可能改变指向链表的尾结点的引用，因为当链表中只有一个结点时，它既是首结点又是尾结点！另外，这段代码也无法处理链表为空的情况（它会使用空链接）。类似这些情况的细节使链表代码特别难以调试。在链表结尾插入新结点的过程如图1.3.8所示。
图1.3.8 在链表的结尾插入一个新结点
1.3.3.6 其他位置的插入和删除操作
总的来说，我们已经展示了在链表中如何通过若干指令实现以下操作，其中我们可以通过first链接访问链表的首结点并通过last链接访问链表的尾结点：
❏在表头插入结点；
❏从表头删除结点；
❏在表尾插入结点。
其他操作，例如以下几种，就不那么容易实现了：
❏删除指定的结点；
❏在指定结点前插入一个新结点。
例如，我们怎样才能删除链表的尾结点呢？last链接帮不上忙，因为我们需要将链表尾结点的前一个结点中的链接（它指向的正是last）值改为null。在缺少其他信息的情况下，唯一的解决办法就是遍历整条链表并找出指向last的结点（请见下文以及练习1.3.19）。这种解决方案并不是我们想要的，因为它所需的时间和链表的长度成正比。实现任意插入和删除操作的标准解决方案是使用双向链表，其中每个结点都含有两个链接，分别指向不同的方向。我们将实现这些操作的代码留做练习（请见练习1.3.31）。我们的所有实现都不需要双向链表。
1.3.3.7 遍历
要访问一个数组中的所有元素，我们会使用如下代码来循环处理a[]中的所有元素：
for (int i = 0; i ＜ N; i++)
{
// 处理a[i]
}
访问链表中的所有元素也有一个对应的方式：将循环的索引变量x初始化为链表的首结点，然后通过x.item访问和x相关联的元素，并将x设为x.next来访问链表中的下一个结点，如此反复直到x为null为止（这说明我们已经到达了链表的结尾）。这个过程被称为链表的遍历，可以用以下循环处理链表的每个结点的代码简洁表达，其中first指向链表的首结点：
for (Node x = first; x ! = null; x = x.next)
{
// 处理x.item
}
这种方式和迭代遍历一个数组中的所有元素的标准方式一样自然。在我们的实现中，它是迭代器使用的基本方式，它使用例能够迭代访问链表的所有元素而无需知道链表的实现细节。
1.3.3.8 栈的实现
有了这些预备知识，给出我们的Stack API的实现就很简单了，如94页的算法1.2所示。它将栈保存为一条链表，栈的顶部即为表头，实例变量first指向栈顶。这样，当使用push()压入一个元素时，我们会按照1.3.3.3节所讨论的代码将该元素添加在表头；当使用pop()删除一个元素时，我们会按照1.3.3.4节讨论的代码将该元素从表头删除。要实现size()方法，我们用实例变量N保存元素的个数，在压入元素时将N加1，在弹出元素时将N减1。要实现isEmpty()方法，只需检查first是否为null（或者可以检查N是否为0）。该实现使用了泛型的Item——你可以认为类名后的＜Item＞表示的是实现中所出现的所有Item都会替换为用例所提供的任意数据类型的名称（请见1.3.2.2节）。我们暂时省略了关于迭代的代码并将它们留到算法1.4中继续讨论。图1.3.9显示了我们所常用的测试用例的轨迹（测试用例代码放在了图后面）。链表的使用达到了我们的最优设计目标：
图1.3.9 stack的开发用例的轨迹
❏它可以处理任意类型的数据；
❏所需的空间总是和集合的大小成正比；
❏操作所需的时间总是和集合的大小无关。
Stack的测试用例
这份实现是我们对许多算法的实现的原型。它定义了链表数据结构并实现了供用例使用的方法push()和pop()，仅用了少量代码就取得了所期望的效果。算法和数据结构是相辅相成的。在本例中，算法的实现代码很简单，但数据结构的性质却并不简单，我们用了好几页纸来说明这些性质。这种数据结构的定义和算法的实现的相互作用很常见，也是本书中我们对抽象数据类型的实现重点。
算法1.2下压堆栈（链表实现）
public class Stack＜Item＞ implements Iterable＜Item＞
{
private Node first; // 栈顶（最近添加的元素）
private int N; // 元素数量
private class Node
{ // 定义了结点的嵌套类
Item item;
Node next;
}
public boolean isEmpty() { return first == null; } // 或：N == 0
public int size() { return N; }
public void push(Item item)
{ // 向栈顶添加元素
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}
public Item pop()
{ //从栈顶删除元素
Item item = first.item;
first = first.next;
N--;
return item;
}
// iterator()的实现请见算法1.4
// 测试用例main()的实现请见本节前面部分
}
这份泛型的Stack实现的基础是链表数据结构。它可以用于创建任意数据类型的栈。要支持迭代，请添加算法1.4中为Bag数据类型给出的加粗部分的代码。
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。这里我们省略了支持迭代的代码并将它们留到算法1.4中继续讨论。下面所示的是一个开发用例，它和我们在Stack中使用的用例很相似，它的轨迹如算法1.3所示。Queue的实现使用的数据结构和Stack相同——链表，但它实现了不同的添加和删除元素的算法，这也是用例所看到的后进先出和先进后出的区别所在。和刚才一样，我们用链表达到了最优设计目标：它可以处理任意类型的数据，所需的空间总是和集合的大小成正比，操作所需的时间总是和集合的大小无关。
Queue的测试用例
算法1.3先进先出队列
public class Queue＜Item＞ implements Iterable＜Item＞
{
private Node first; // 指向最早添加的结点的链接
private Node last; // 指向最近添加的结点的链接
private int N; // 队列中的元素数量
private class Node
{ // 定义了结点的嵌套类
Item item;
Node next;
}
public boolean isEmpty() { return first == null; } // 或： N == 0.
public int size() { return N; }
public void enqueue(Item item)
{ // 向表尾添加元素
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
N++;
}
public Item dequeue()
{ // 从表头删除元素
Item item = first.item;
first = first.next;
if (isEmpty()) last = null;
N--;
return item;
}
// iterator()的实现请见算法1.4
// 测试用例main()的实现请见前面
}
这份泛型的Queue实现的基础是链表数据结构。它可以用于创建任意数据类型的队列。要支持迭代，请添加算法1.4中为Bag数据类型给出的加粗部分的代码。
Queue的开发用例的轨迹如图1.3.10所示。
图1.3.10 Queue的开发用例的轨迹
在结构化存储数据集时，链表是数组的一种重要的替代方式。这种替代方案已经有数十年的历史。事实上，编程语言历史上的一块里程碑就是McCathy在20世纪50年代发明的LISP语言，而链表则是这种语言组织程序和数据的主要结构。在练习中你会发现，链表编程也会遇到各种问题，且调试十分困难。在现代编程语言中，安全指针、自动垃圾回收（请见1.2节答疑部分）和抽象数据类型的使用使我们能够将链表处理的代码封装在若干个类中，正如本文所述。
1.3.3.10 背包的实现
用链表数据结构实现我们的Bag API只需要将Stack中的push()改名为add()，并去掉pop()的实现即可，如算法1.4所示（也可以用相同的方法实现Queue，但需要的代码更多）。在这份实现中，加粗部分的代码可以通过遍历链表使Stack、Queue和Bag变为可迭代的。对于Stack，链表的访问顺序是后进先出；对于Queue，链表的访问顺序是先进先出；对于Bag，它正好也是后进先出的顺序，但顺序在这里并不重要。如算法1.4中加粗部分的代码所示，要在集合数据类型中实现迭代，第一步就是要添加下面这行代码，这样我们的代码才能引用Java的Iterator接口：
import java.util.Iterator;
第二步是在类的声明中添加这行代码，它保证了类必然会提供一个iterator()方法：
implements Iterable＜Item＞
iterator()方法本身只是简单地从实现了Iterator接口的类中返回一个对象：
public Iterator＜Item＞ iterator()
{ return new ListIterator(); }
这段代码保证了类必然会实现方法hasNext()、next()和remove()供用例的foreach语法使用。要实现这些方法，算法1.4中的嵌套类ListIterator维护了一个实例变量current来记录链表的当前结点。hasNext()方法会检测current是否为null, next()方法会保存当前元素的引用，将current变量指向链表中的下个结点并返回所保存的引用。
算法1.4背包
import java.util.Iterator;
public class Bag＜Item＞ implements Iterable<Item>
{
private Node first; //链表的首结点
private class Node
{
Item item;
Node next;
}
public void add(Item item)
{ // 和Stack的push()方法完全相同
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
}
public Iterator<Item> iterator()
{ return new ListIterator(); }
private class ListIterator implements Iterator<Item>
{
private Node current = first;
public boolean hasNext()
{ return current ! = null; }
public void remove() { }
public Item next()
{
Item item = current.item;
current = current.next;
return item;
}
}
}
这份Bag的实现维护了一条链表，用于保存所有通过add()添加的元素。size()和isEmpty()方法的代码和Stack中的完全相同，因此在此处省略。迭代器会遍历链表并将当前结点保存在current变量中。我们可以将加粗的代码添加到算法1.2和算法1.3中使Stack和Queue变为可迭代的，因为它们背后的数据结构是相同的，只是Stack和Queue的链表访问顺序分别是后进先出和先进先出而已。
1.3.4 综述
在本节中，我们所学习的支持泛型和迭代的背包、队列和栈的实现所提供的抽象使我们能够编写简洁的用例程序来操作对象的集合。深入理解这些抽象数据类型非常重要，这是我们研究算法和数据结构的开始。原因有三：第一，我们将以这些数据类型为基石构造本书中的其他更高级的数据结构；第二，它们展示了数据结构和算法的关系以及同时满足多个有可能相互冲突的性能目标时所要面对的挑战；第三，我们将要学习的若干算法的实现重点就是需要其中的抽象数据类型能够支持对对象集合的强大操作，这些实现正是我们的起点。
数据结构
我们现在拥有两种表示对象集合的方式，即数组和链表（如表1.3.7所示）。Java内置了数组，链表也很容易使用Java的标准方法实现。两者都非常基础，常常被称为顺序存储和链式存储。在本书后面部分，我们会在各种抽象数据类型的实现中将多种方式结归并扩展这些基本的数据结构。其中一种重要的扩展就是各种含有多个链接的数据结构。例如，3.2节和3.3节的重点就是被称为二叉树的数据结构，它由含有两个链接的结点组成。另一个重要的扩展是复合型的数据结构：我们可以使用背包存储栈，用队列存储数组，等等。例如，第4章的主题是图，我们可以用数组的背包表示它。用这种方式很容易定义任意复杂的数据结构，而我们重点研究抽象数据类型的一个重要原因就是试图控制这种复杂度。
表1.3.7 基础数据结构
我们在本节中研究背包、队列和栈时描述数据结构和算法的方式是全书的原型（本书中的数据结构示例见表1.3.8）。在研究一个新的应用领域时，我们将会按照以下步骤识别目标并使用数据抽象解决问题：
表1.3.8 本书所给出的数据结构举例
❏定义API；
❏根据特定的应用场景开发用例代码；
❏描述一种数据结构（一组值的表示），并在API所对应的抽象数据类型的实现中根据它定义类的实例变量；
❏描述算法（实现一组操作的方式），并根据它实现类中的实例方法；
❏分析算法的性能特点。
在下一节中，我们会详细研究最后一步，因为它常常能够决定哪种算法和实现才是解决现实应用问题的最佳选择。
答疑
问 并不是所有编程语言都支持泛型，甚至Java的早期版本也不支持。有其他替代方案吗？
答 如正文所述，一种替代方法是为每种类型的数据都实现一个不同的集合数据类型。另一种方法是构造一个Object对象的栈，并在用例中使用pop()时将得到的对象转换为所需的数据类型。这种方式的问题在于类型不匹配错误只能在运行时发现。而在泛型中，如果你的代码将错误类型的对象压入栈中，比如这样：
Stack＜Apple＞ stack = new Stack＜Apple＞(); Apple a = new Apple(); ... Orange b = new Orange(); ... stack.push(a); ... stack.push(b); // 编译时错误
会得到一个编译时错误：
push(Apple) in Stack＜Apple＞ cannot be applied to (Orange)
能够在编译时发现错误足以说服我们使用泛型。
问 为什么Java不允许泛型数组？
答 专家们仍然在争论这一点。你可能也需要成为专家才能理解它！对于初学者，请先了解共变数组（covariant array）和类型擦除（type erasure）。
问 如何才能创建一个字符串栈的数组？
答 使用类型转换，比如：
Stack＜String＞[] a = (Stack＜String＞[]) new Stack[N];
警告：这段类型转换的用例代码和1.3.2.2节所示的有所不同。你可能会以为需要使用Object而非Stack。在使用泛型时，Java会在编译时检查类型的安全性，但会在运行时抛弃所有这些信息。因此在运行时语句右侧就变成了Stack＜Object＞[]或者只剩下了Stack[]，因此我们必须将它们转化为Stack＜String＞[]。
问 在栈为空时调用pop()会发生什么？
答 这取决于实现。对于我们在算法1.2中给出的实现，你会得到一个NullPointerException异常。对于我们在本书的网站上给出的实现，我们会抛出一个运行时异常以帮助用户定位错误。一般来说，在应用广泛的代码中这类检查越多越好。
问 既然有了链表，为什么还要学习如何调整数组的大小？
答 我们还将会学习若干抽象数据类型的示例实现，它们需要使用数组来实现一些链表难以实现的操作。ResizingArrayStack是控制它们的内存使用的样板。
问 为什么将Node声明为嵌套类？为什么使用private ？
答 将Node声明为私有的嵌套类之后，我们可以将Node的方法和实例变量的访问范围限制在包含它的类中。私有嵌套类的一个特点是只有包含它的类能够直接访问它的实例变量，因此无需将它的实例变量声明为public或是private。专业背景较强的读者注意：非静态的嵌套类也被称为内部类，因此从技术上来说我们的Node类也是内部类，尽管非泛型的类也可以是静态的。
问 当我输入javac Stack.java编译算法1.2和其他程序时，我发现了Stack.class和Stack$Node.class两个文件。第二个文件是做什么用的？
答 第二个文件是为内部类Node创建的。Java的命名规则会使用$分隔外部类和内部类。
问 Java标准库中有栈和队列吗？
答 有，也没有。Java有一个内置的库，叫做java.util.Stack，但你需要栈的时候请不要使用它。它新增了几个一般不属于栈的方法，例如获取第i个元素。它还允许从栈底添加元素（而非栈顶），所以它可以被当做队列使用！尽管拥有这些额外的操作看起来可能很有用，但它们其实是累赘。我们使用某种数据类型不仅仅是为了获得我们能够想象的各种操作，也是为了准确地指定我们所需要的操作。这么做的主要好处在于系统能够防止我们执行一些意外的操作。java.util.Stack的API是宽接口的一个典型例子，我们通常会极力避免出现这种情况。
问 是否允许用例向栈或队列中添加空（null）元素？
答 在Java中实现集合类数据类型时这个问题是很常见的。我们的实现（以及Java的栈和队列库）允许插入null值。
问 如果用例在迭代中调用push()或者pop(), Stack的迭代器应该怎么办？
答 作为一个快速出错的迭代器，它应该立即抛出一个java.util.ConcurrentModificationException异常。请见练习1.3.50。
问 我们能够用foreach循环访问数组吗？
答 可以（尽管数组没有实现Iterable接口）。以下代码将会打印所有命令行参数：
public static void main(String[] args)
{ for (String s : args) StdOut.println(s); }
问 我们能够用foreach循环访问字符串吗？
答 不行，String没有实现Iterable接口。
问 为什么不实现一个单独的Collection数据类型并实现添加元素、删除最近插入的元素、删除最早插入的元素、删除随机元素、迭代、返回集合元素数量和其他我们可能需要的方法？这样我们就能在一个类中实现所有这些方法并可以应用于各种用例。
答 再次强调一遍，这又是一个宽接口的例子。Java在java.util.ArrayList和java.util.LinkedList类中实现了类似的设计。避免使用它们的一个原因是这样无法保证高效实现所有这些方法。在本书中，我们总是以API作为设计高效算法和数据结构的起点，而设计只含有几个操作的接口显然比设计含有许多操作的接口更简单。我们坚持窄接口的另一个原因是它们能够限制用例的行为，这将使用例代码更加易懂。如果一段用例代码使用Stack＜String＞，而另一段用例代码使用Queue＜Transaction＞，我们就可以知道后进先出的访问顺序对于前者很重要，而先进先出的访问顺序对于后者很重要。
练习
1.3.1 为FixedCapacityStackOfStrings添加一个方法isFull()。
1.3.2 给定以下输入，java Stack的输出是什么？
it was - the best - of times - - - it was - the - -
1.3.3 假设某个用例程序会进行一系列入栈和出栈的混合栈操作。入栈操作会将整数0到9按顺序压入栈；出栈操作会打印出返回值。下面哪种序列是不可能产生的？
a. 4 3 2 1 0 9 8 7 6 5 b. 4 6 8 7 5 3 2 9 0 1 c. 2 5 6 7 4 8 9 3 1 0 d. 4 3 2 1 0 5 6 7 8 9 e. 1 2 3 4 5 6 9 8 7 0 f. 0 4 6 5 3 8 1 7 2 9 g. 1 4 7 9 8 6 5 3 0 2 h. 2 1 4 3 6 5 8 7 9 0
1.3.4 编写一个Stack的用例Parentheses，从标准输入中读取一个文本流并使用栈判定其中的括号是否配对完整。例如，对于[()]{}{[()()]()}程序应该打印true，对于 [(])则打印false。
1.3.5 当N为50时下面这段代码会打印什么？从较高的抽象层次描述给定正整数N时这段代码的行为。
Stack＜Integer＞ stack = new Stack＜Integer＞();
while (N ＞ 0)
{
stack.push(N % 2);
N = N / 2;
}
for (int d : stack) StdOut.print(d);
StdOut.println();
答：打印N的二进制表示（当N为50时打印110010）。
1.3.6 下面这段代码对队列q进行了什么操作？
Stack＜String＞ stack = new Stack＜String＞();
while (! q.isEmpty())
stack.push(q.dequeue());
while (! stack.isEmpty())
q.enqueue(stack.pop());
1.3.7 为Stack添加一个方法peek()，返回栈中最近添加的元素（而不弹出它）。
1.3.8 给定以下输入，给出DoublingStackOfStrings的数组的内容和大小。
it was - the best - of times - - - it was - the - -
1.3.9 编写一段程序，从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式。
例如，给定输入：
1 + 2 ) ＊ 3-4 ) ＊ 5-6 ) ) )
你的程序应该输出：
( ( 1 + 2 ) ＊ ( ( 3-4 ) ＊ ( 5-6 ) ) )
1.3.10 编写一个过滤器InfixToPostfix，将算术表达式由中序表达式转为后序表达式。
1.3.11 编写一段程序EvaluatePostfix，从标准输入中得到一个后序表达式，求值并打印结果（将上一题的程序中得到的输出用管道传递给这一段程序可以得到和Evaluate相同的行为）。
1.3.12 编写一个可迭代的Stack用例，它含有一个静态的copy()方法，接受一个字符串的栈作为参数并返回该栈的一个副本。注意：这种能力是迭代器价值的一个重要体现，因为有了它我们无需改变基本API就能够实现这种功能。
1.3.13 假设某个用例程序会进行一系列入列和出列的混合队列操作。入列操作会将整数0到9按顺序插入队列；出列操作会打印出返回值。下面哪种序列是不可能产生的？
a. 0 1 2 3 4 5 6 7 8 9 b. 4 6 8 7 5 3 2 9 0 1 c. 2 5 6 7 4 8 9 3 1 0 d. 4 3 2 1 0 5 6 7 8 9
1.3.14 编写一个类ResizingArrayQueueOfStrings，使用定长数组实现队列的抽象，然后扩展实现，使用调整数组的方法突破大小的限制。
1.3.15 编写一个Queue的用例，接受一个命令行参数k并打印出标准输入中的倒数第k个字符串（假设标准输入中至少有k个字符串）。
1.3.16 使用1.3.1.5节中的readInts()作为模板为Date编写一个静态方法readDates()，从标准输入中读取由练习1.2.19的表格所指定的格式的多个日期并返回一个它们的数组。
1.3.17 为Transaction类完成练习1.3.16。
链表练习
这部分练习是专门针对链表的。建议：使用正文中所述的可视化表达方式画图。
1.3.18 假设x是一条链表的某个结点且不是尾结点。下面这条语句的效果是什么？
x.next = x.next.next;
答：删除x的后续结点。
1.3.19 给出一段代码，删除链表的尾结点，其中链表的首结点为first。
1.3.20 编写一个方法delete()，接受一个int参数k，删除链表的第k个元素（如果它存在的话）。
1.3.21 编写一个方法find()，接受一条链表和一个字符串key作为参数。如果链表中的某个结点的item域的值为key，则方法返回true，否则返回false。
1.3.22 假设x是一条链表中的某个结点，下面这段代码做了什么？
t.next = x.next; x.next = t;
答：插入结点t并使它成为x的后续结点。
1.3.23 为什么下面这段代码和上一道题中的代码效果不同？
x.next = t; t.next = x.next;
答：在更新t.next时，x.next已经不再指向x的后续结点，而是指向t本身！
1.3.24 编写一个方法removeAfter()，接受一个链表结点作为参数并删除该结点的后续结点（如果参数结点或参数结点的后续结点为空则什么也不做）。
1.3.25 编写一个方法insertAfter()，接受两个链表结点作为参数，将第二个结点插入链表并使之成为第一个结点的后续结点（如果两个参数为空则什么也不做）。
1.3.26 编写一个方法remove()，接受一条链表和一个字符串key作为参数，删除链表中所有item域为key的结点。
1.3.27 编写一个方法max()，接受一条链表的首结点作为参数，返回链表中键最大的节点的值。假设所有键均为正整数，如果链表为空则返回0。
1.3.28 用递归的方法解答上一道练习。
1.3.29 用环形链表实现Queue。环形链表也是一条链表，只是没有任何结点的链接为空，且只要链表非空则last.next的值为first。只能使用一个Node类型的实例变量（last）。
1.3.30 编写一个函数，接受一条链表的首结点作为参数，（破坏性地）将链表反转并返回结果链表的首结点。
迭代方式的解答：为了完成这个任务，我们需要记录链表中三个连续的结点：reverse、first和second。在每轮迭代中，我们从原链表中提取结点first并将它插入到逆链表的开头。我们需要一直保持first指向原链表中所有剩余结点的首结点，second指向原链表中所有剩余结点的第二个结点，reverse指向结果链表中的首结点。
public Node reverse(Node x)
{
Node first = x;
Node reverse = null;
while (first ! = null)
{
Node second = first.next;
first.next = reverse;
reverse = first;
first = second;
}
return reverse;
}
在编写和链表相关的代码时，我们必须小心处理异常情况（链表为空或是只有一个或两个结点）和边界情况（处理首尾结点）。它们通常比处理正常情况要困难得多。
递归解答：假设链表含有N个结点，我们先递归颠倒最后N-1个结点，然后小心地将原链表中的首结点插入到结果链表的末端。
public Node reverse(Node first)
{
if (first == null) return null;
if (first.next == null) return first;
Node second = first.next;
Node rest = reverse(second);
second.next = first;
first.next = null;
return rest;
}
1.3.31 实现一个嵌套类DoubleNode用来构造双向链表，其中每个结点都含有一个指向前驱元素的引用和一项指向后续元素的引用（如果不存在则为null）。为以下任务实现若干静态方法：在表头插入结点、在表尾插入结点、从表头删除结点、从表尾删除结点、在指定结点之前插入新结点、在指定结点之后插入新结点、删除指定结点。
提高题
1.3.32 Steque。一个以栈为目标的队列（或称steque），是一种支持push、pop和enqueue操作的数据类型。为这种抽象数据类型定义一份API并给出一份基于链表的实现。
1.3.33 Deque。一个双向队列（或者称为deque）和栈或队列类似，但它同时支持在两端添加或删除元素。Deque能够存储一组元素并支持表1.3.9中的API：
表1.3.9 泛型双向队列的API
编写一个使用双向链表实现这份API的Deque类，以及一个使用动态数组调整实现这份API的ResizingArrayDeque类。
1.3.34 随机背包。随机背包能够存储一组元素并支持表1.3.10中的API：
表1.3.10 泛型随机背包的API
编写一个RandomBag类来实现这份API。请注意，除了形容词随机之外，这份API和Bag的API是相同的，这意味着迭代应该随机访问背包中的所有元素（对于每次迭代，所有的N！种排列出现的可能性均相同）。提示：用数组保存所有元素并在迭代器的构造函数中随机打乱它们的顺序。
1.3.35 随机队列。随机队列能够存储一组元素并支持表1.3.11中的API：
表1.3.11 泛型随机队列的API
编写一个RandomQueue类来实现这份API。提示：使用（能够动态调整大小的）数组表示数据。删除一个元素时，随机交换某个元素（索引在0和N-1之间）和末位元素（索引为N-1）的位置，然后像ResizingArrayStack一样删除并返回末位元素。编写一个用例，使用RandomQueue＜Card＞在桥牌中发牌（每人13张）。
1.3.36 随机迭代器。为上一题中的RandomQueue＜Item＞编写一个迭代器，随机返回队列中的所有元素。
1.3.37 Josephus问题。在这个古老的问题中，N个身陷绝境的人一致同意通过以下方式减少生存人数。他们围坐成一圈（位置记为0到N-1）并从第一个人开始报数，报到M的人会被杀死，直到最后一个人留下来。传说中Josephus找到了不会被杀死的位置。编写一个Queue的用例Josephus，从命令行接受N和M并打印出人们被杀死的顺序（这也将显示Josephus在圈中的位置）。
% java Josephus 7 2 1 3 5 0 4 2 6
1.3.38 删除第k个元素。实现一个类并支持表1.3.12中的API：
表1.3.12 泛型一般队列的API
首先用数组实现该数据类型，然后用链表实现该数据类型。注意：我们在第3章中介绍的算法和数据结构可以保证insert()和delete()的实现所需的运行时间和和队列中的元素数量成对数关系——请见练习3.5.27。
1.3.39 环形缓冲区。环形缓冲区，又称为环形队列，是一种定长为N的先进先出的数据结构。它在进程间的异步数据传输或记录日志文件时十分有用。当缓冲区为空时，消费者会在数据存入缓冲区前等待；当缓冲区满时，生产者会等待将数据存入缓冲区。为RingBuffer设计一份API并用（回环）数组将其实现。
1.3.40 前移编码。从标准输入读取一串字符，使用链表保存这些字符并清除重复字符。当你读取了一个从未见过的字符时，将它插入表头。当你读取了一个重复的字符时，将它从链表中删去并再次插入表头。将你的程序命名为MoveToFront：它实现了著名的前移编码策略，这种策略假设最近访问过的元素很可能会再次访问，因此可以用于缓存、数据压缩等许多场景。
1.3.41 复制队列。编写一个新的构造函数，使以下代码
Queue＜Item＞ r = new Queue＜Item＞(q);
得到的r指向队列q的一个新的独立的副本。可以对q或r进行任意入列或出列操作但它们不会相互影响。提示：从q中取出所有元素再将它们插入q和r。
1.3.42 复制栈。为基于链表实现的栈编写一个新的构造函数，使以下代码
Stack＜Item＞ t = new Stack＜Item＞(s);
得到的t指向栈s的一个新的独立的副本。
1.3.43 文件列表。文件夹就是一列文件和文件夹的列表。编写一个程序，从命令行接受一个文件夹名作为参数，打印出该文件夹下的所有文件并用递归的方式在所有子文件夹的名下（缩进）列出其下的所有文件。提示：使用队列，并参考java.io.File。
1.3.44 文本编辑器的缓冲区。为文本编辑器的缓冲区设计一种数据类型并实现表1.3.13中的API。
表1.3.13 文本缓冲区的API
提示：使用两个栈。
1.3.45 栈的可生成性。假设我们的栈测试用例将会进行一系列混合的入栈和出栈操作，序列中的整数0,1, ..., N-1（按此先后顺序排列）表示入栈操作，N个减号表示出栈操作。设计一个算法，判定给定的混合序列是否会使数组向下溢出（你所使用的空间量与N无关，即不能用某种数据结构存储所有整数）。设计一个线性时间的算法判定我们的测试用例能否产生某个给定的排列（这取决于出栈操作指令的出现位置）。
解答：除非对于某个整数k，前k次出栈操作会在前k次入栈操作前完成，否则栈不会向下溢出。如果某个排列可以产生，那么它产生的方式一定是唯一的：如果输出排列中的下一个整数在栈顶，则将它弹出，否则将它压入栈之中。
1.3.46 栈可生成性问题中禁止出现的排列。若三元组（a, b, c）中a＜b＜c且c最先被弹出，a第二，b第三（c和a以及a和b之间可以间隔其他整数），那么当且仅当排列中不含这样的三元组时（如上题所述的）栈才可能生成它。
部分解答：设有一个这样的三元组（a, b, c）。c会在a和b之前被弹出，但a和b会在c之前被压入。因此，当c被压入时，a和b都已经在栈之中了。所以，a不可能在b之前被弹出。
1.3.47 可连接的队列、栈或steque。为队列、栈或steque（请见练习1.3.32）添加一个能够（破坏性地）连接两个同类对象的额外操作catenation。
1.3.48 双向队列与栈。用一个双向队列实现两个栈，保证每个栈操作只需要常数次的双向队列操作（请见练习1.3.33）。
1.3.49 栈与队列。用有限个栈实现一个队列，保证每个队列操作（在最坏情况下）都只需要常数次的栈操作。警告：非常难！
1.3.50 快速出错的迭代器。修改Stack的迭代器代码，确保一旦用例在迭代器中（通过push()或pop()操作）修改集合数据就抛出一个java.util.ConcurrentModificationException异常。
解答：用一个计数器记录push()和pop()操作的次数。在创建迭代器时，将该值记录到Iterator的一个实例变量中。在每次调用hasNext()和next()之前，检查该值是否发生了变化，如果变化则抛出异常。