Java/堆栈之道
abstract data typeseeADT ADT encapsulation
到目前为止，我们所见过的所有数据类型都是具体的，因为我们已经完全指定了它们的实现方式。例如，Card 类使用两个整数来表示一张卡片。正如我在当时讨论的那样，这不是表示卡片的唯一方式；还有许多替代的实现方式。
抽象数据类型（ADT）指定了一组操作（或方法）以及操作的语义（它们的作用），但它没有指定操作的实现方式。这就是它抽象的原因。
项目符号
如果你可以指定所需的运算而不必同时考虑运算的执行方式，那么这将简化指定算法的任务。
由于通常有许多方法可以实现 ADT，因此编写可与任何可能的实现方式一起使用的算法可能会有用。
众所周知的 ADT（例如本章中的堆栈 ADT）通常在标准库中实现，因此可以编写一次，由许多程序员使用。
ADT 上的操作为指定和讨论算法提供了通用的高级语言。
项目符号
当我们谈论 ADT 时，我们经常将使用 ADT 的代码（称为客户端代码）与实现 ADT 的代码（称为提供者代码）区分开来，因为它提供了一组标准服务。
client provider
stack collection ADT!Stack
在本章中，我们将研究一种常见的 ADT，即堆栈。堆栈是一种集合，这意味着它是一种包含多个元素的数据结构。我们见过的其他集合包括数组和列表。
正如我所说，ADT 由一组操作定义。堆栈可以执行以下操作集
描述
[构造函数:] 创建一个新的空堆栈。
[push:] 向堆栈添加一个新项目。
[pop:] 从堆栈中删除并返回一个项目。返回的项目始终是最后添加的项目。
[empty:] 检查堆栈是否为空。
描述
堆栈有时被称为“后进先出”或 LIFO 数据结构，因为最后添加的项目是第一个被移除的项目。
Stack class!Stack generic data structure data structure!generic
Java 提供了一个名为 Stack 的内置对象类型，它实现了堆栈 ADT。你应该努力使这两件事（ADT 和 Java 实现）保持一致。在使用 Stack 类之前，我们必须从 java.util 中导入它。
然后构造一个新 Stack 的语法是
逐字
Stack stack = new Stack ();
逐字
最初堆栈为空，我们可以用 empty 方法确认，该方法返回一个布尔值
逐字
System.out.println (stack.empty ());
逐字
堆栈是一种泛型数据结构，这意味着我们可以向其中添加任何类型的项目。但是，在 Java 实现中，我们只能添加对象类型。在我们的第一个示例中，我们将使用 Node 对象，如上一章中定义的那样。让我们从创建和打印一个简短的列表开始。
逐字
LinkedList list = new LinkedList (); list.addFirst (3); list.addFirst (2); list.addFirst (1); list.print ();
逐字
输出是 (1, 2, 3)。要将 Node 对象放入堆栈，请使用 push 方法
verbatim stack.push (list.head); verbatim
以下循环遍历列表并将所有节点推入堆栈
逐字
for (Node node = list.head; node != null; node = node.next)
stack.push (node);
逐字
我们可以使用 pop 方法从堆栈中删除一个元素。
逐字
Object obj = stack.pop ();
逐字
pop 的返回类型是 Object！这是因为堆栈实现实际上不知道它包含的对象的类型。当我们推入 Node 对象时，它们会自动转换为 Object。当我们从堆栈中取回它们时，我们必须将它们转换回 Node。
verbatim Node node = (Node) obj; System.out.println (node); verbatim
不幸的是，跟踪堆栈中的对象并在从堆栈中删除它们时将其转换回正确的类型的责任落在了程序员身上。如果你尝试将对象转换为错误的类型，你将得到一个 ClassCastException。
以下循环是在堆栈为空时停止，弹出堆栈中所有元素的常用惯用法
逐字
while (!stack.empty ())
Node node = (Node) stack.pop ();
System.out.print (node + " ");
逐字
输出是 3 2 1。换句话说，我们刚刚使用堆栈以相反的顺序打印了列表的元素！当然，这不是打印列表的标准格式，但使用堆栈，这样做非常容易。
你应该将这段代码与上一章中 printBackward 的实现进行比较。这里递归版本的 printBackward 和堆栈算法之间存在自然的平行关系。区别在于 printBackward 使用运行时堆栈跟踪节点，同时遍历列表，然后在从递归返回时打印它们。堆栈算法做同样的事情，只是使用 Stack 对象而不是运行时堆栈。
wrapper class class!wrapper object type primitive type
对于 Java 中的每种基本类型，都有一个名为包装类的内置对象类型。例如，int 的包装类称为 Integer；对于 double，它被称为 Double。
包装类很有用，原因如下
项目符号
你可以实例化包装类并创建包含基本值的 对象。换句话说，你可以将基本值包装在一个对象中，这在你需要调用需要对象类型的方法时很有用。
每个包装类都包含特殊值（例如类型的最小值和最大值）以及用于类型之间转换的有用方法。
项目符号
wrapper class!instantiating
创建包装对象最直接的方法是使用其构造函数
逐字
Integer i = new Integer (17);
Double d = new Double (3.14159);
Character c = new Character ('b');
逐字
从技术上讲，String 不是包装类，因为没有相应的基本类型，但创建 String 对象的语法相同
逐字
String s = new String ("fred");
逐字
另一方面，没有人使用 String 对象的构造函数，因为你可以用简单的 String 值获得相同的效果
逐字
String s = "fred";
逐字
一些包装类具有第二个构造函数，该构造函数以 String 作为参数并尝试转换为适当的类型。例如
逐字
Integer i = new Integer ("17");
Double d = new Double ("3.14159");
逐字
类型转换过程不是很健壮。例如，如果 String 格式不正确，它们将导致 NumberFormatException。String 中的任何非数字字符（包括空格）都将导致转换失败。
NumberFormatException exception!NumberFormat
逐字
Integer i = new Integer ("17.1"); // WRONG!!
Double d = new Double ("3.1459 "); // WRONG!!
逐字
在尝试转换 String 之前，通常最好检查 String 的格式。
wrapper class!extracting value
Java 知道如何打印包装对象，因此提取值的 easiest 方式就是打印对象
逐字
Integer i = new Integer (17); Double d = new Double (3.14159); System.out.println (i); System.out.println (d);
逐字
或者，你可以使用 toString 方法将包装对象的内容转换为 String
逐字
String istring = i.toString(); String dstring = d.toString();
逐字
最后，如果你只想从对象中提取基本值，每个包装类中都有一个对象方法可以完成这项工作
逐字
int iprim = i.intValue (); double dprim = d.doubleValue ();
逐字
还有将包装对象转换为不同基本类型的方法。你应该查看每个包装类的文档，以了解有哪些可用方法。
wrapper class!methods
正如我提到的，包装类包含与每个类型相关的有用方法。例如，Character 类包含许多用于将字符转换为大小写以及检查字符是否为数字、字母或符号的方法。
String 类还包含用于转换为大小写的方法。但是请记住，它们是函数，而不是修饰符（参见不可变部分）。
举个例子，Integer 类包含用于以不同进制解释和打印整数的方法。如果有一个包含以 6 进制表示的数字的字符串，可以使用 parseInt 将其转换为 10 进制。
逐字
String base6 = "12345"; int base10 = Integer.parseInt (base6, 6); System.out.println (base10);
逐字
由于 parseInt 是一个类方法，因此可以通过点表示法命名类和方法来调用它。
6 进制可能没有那么有用，但十六进制（16 进制）和八进制（8 进制）在与计算机科学相关的领域中很常见。
后缀表达式
[edit | edit source]postfix infix expressions
在大多数编程语言中，数学表达式是用操作符放在两个操作数之间来写的，比如 1+2。这种格式称为中缀。一些计算器使用另一种称为后缀的格式。在后缀中，操作符位于操作数之后，例如 1 2+。
后缀有时很有用，因为有一种使用堆栈自然地计算后缀表达式的办法。
项目符号
从表达式的开头开始，一次获取一个项（操作符或操作数）。
项目符号
如果该项是操作数，则将其压入堆栈。
如果该项是操作符，则从堆栈中弹出两个操作数，对它们执行操作，并将结果压回堆栈。
项目符号
当我们到达表达式的末尾时，堆栈上应该只剩下一个操作数。这个操作数就是结果。
项目符号
作为练习，将此算法应用于表达式 1 2 + 3 *。
此示例演示了后缀的一个优势：不需要使用括号来控制操作顺序。要获得相同的结果，在中缀中，我们必须写成 (1 + 2) * 3。作为练习，写一个与 1 + 2 * 3 等效的后缀表达式？
解析
[edit | edit source]parse token delimiter class!StringTokenizer StringTokenizer class
为了实现上一节中的算法，我们需要能够遍历一个字符串，并将其分解为操作数和操作符。这个过程是一个解析的例子，结果——字符串的各个片段——被称为标记。
Java 提供了一个名为 StringTokenizer 的内置类，它解析字符串并将它们分解成标记。要使用它，必须从 java.util 中导入它。
在最简单的形式中，StringTokenizer 使用空格来标记标记之间的边界。一个标记边界的字符称为分隔符。
我们可以通过通常的方式创建一个 StringTokenizer，将要解析的字符串作为参数传递。
逐字
StringTokenizer st = new StringTokenizer ("Here are four tokens.");
逐字
以下循环是用于从 StringTokenizer 中提取标记的标准惯用法。
逐字
while (st.hasMoreTokens ())
System.out.println (st.nextToken());
逐字
输出是
verbatim 这里有四个标记。 verbatim
为了解析表达式，我们可以选择指定其他将用作分隔符的字符
逐字
StringTokenizer st = new StringTokenizer ("11 22+33*", " +-*/");
逐字
第二个参数是一个包含所有将用作分隔符的字符的字符串。现在输出是
verbatim 11 22 33 verbatim
这成功地提取了所有操作数，但我们丢失了操作符。幸运的是，StringTokenizer 还有另一种选择。
逐字
StringTokenizer st = new StringTokenizer ("11 22+33*", " +-*/", true);
逐字
第三个参数表示，“是的，我们想将分隔符也作为标记处理”。现在输出是
verbatim 11 verbatim
22 + 33
逐字
这正是我们用来计算这个表达式的标记流。
实现 ADT
[edit | edit source]encapsulation ADT
ADT 的基本目标之一是分离提供者（编写实现 ADT 的代码的人）和客户端（使用 ADT 的人）的关注点。提供者只需担心实现是否正确——符合 ADT 的规范——而不必担心如何使用它。
相反，客户端假设 ADT 的实现是正确的，并且不关心细节。当您使用 Java 的内置类之一时，您可以享受只作为客户端思考的便利。
另一方面，当您实现 ADT 时，您还需要编写客户端代码来测试它。在这种情况下，您有时必须仔细考虑在特定时刻扮演的是哪种角色。
在接下来的几节中，我们将换个思路，看看使用数组实现 Stack ADT 的一种方法。开始像提供者一样思考。
Stack ADT 的数组实现
[edit | edit source]arraystack
implementation!Stack stack!array implementation
此实现的实例变量是一个 Object 数组，它将包含堆栈中的项目，以及一个整数索引，它将跟踪数组中下一个可用的空间。最初，数组为空，索引为 0。
要向堆栈中添加元素（push），我们将对其引用复制到堆栈上，并增加索引。要删除元素（pop），我们必须先减少索引，然后将元素复制出来。
以下是类定义
verbatim public class Stack verbatim
Object[] array; int index;
public Stack ()
this.array = new Object[128];
this.index = 0;
逐字
像往常一样，一旦我们选择了实例变量，编写构造函数就是一个机械过程。现在，默认大小为 128 个项目。稍后我们将考虑处理此问题的更好方法。
检查空堆栈是微不足道的。
逐字
public boolean empty ()
return index == 0;
逐字
但是，重要的是要记住，堆栈中的元素数量与数组的大小不同。最初，大小为 128，但元素数量为 0。
push 和 pop 的实现自然地遵循规范。
逐字
public void push (Object item)
array[index] = item;
index++;
public Object pop ()
index--;
return array[index];
逐字
为了测试这些方法，我们可以利用我们用来练习内置 Stack 的客户端代码。我们只需要注释掉行 import java.util.Stack。然后，程序将使用我们刚刚编写的实现，而不是使用 java.util 中的堆栈实现。
如果一切按计划进行，程序应该无需任何额外更改即可运行。再一次，使用 ADT 的优势之一是，您可以更改实现而无需更改客户端代码。
调整数组大小
[edit | edit source]resize
array!resizing ArrayIndexOutOfBounds exception!ArrayIndexOutOfBounds
此实现的一个缺点是，它在创建 Stack 时为数组选择了一个任意大小。如果用户向堆栈中推入超过 128 个项目，它将导致 ArrayIndexOutOfBounds 异常。
ArrayIndexOutOfBounds exception!ArrayIndexOutOfBounds
另一种方法是让客户端代码指定数组的大小。这可以缓解问题，但它要求客户端提前知道需要多少个项目，而这并不总是可能的。
更好的解决方案是在必要时检查数组是否已满，并将其变大。由于我们不知道数组需要多大，所以从一个小尺寸开始，每次溢出时将其加倍是一个合理的策略。
以下是 push 的改进版本
逐字
public void push (Object item)
if (full ()) resize ();
// at this point we can prove that index < array.length
array[index] = item;
index++;
逐字
在将新项目放入数组之前，我们检查数组是否已满。如果是，则调用 resize。在 if 语句之后，我们知道要么 (1) 数组中有空间，要么 (2) 数组已调整大小，并且有空间。如果 full 和 resize 是正确的，那么我们可以证明 index < array.length，因此下一条语句不会导致异常。
现在我们只需要实现 full 和 resize 即可。
逐字
private boolean full ()
return index == array.length;
private void resize ()
Object[] newArray = new Object[array.length * 2];
// we assume that the old array is full
for (int i=0; i<array.length; i++)
newArray[i] = array[i];
array = newArray;
逐字
这两个方法都被声明为私有，这意味着它们不能从另一个类调用，只能从当前类内部调用。这是可以接受的，因为没有理由让客户端代码使用这些函数，并且是可取的，因为它强制执行了实现和客户端之间的边界。
method!private private method
full 的实现是微不足道的；它只是检查索引是否超出了有效索引范围。
resize 的实现很简单，但有一个前提，即它假定旧数组已满。换句话说，这个假设是这个方法的前提条件。很容易看出这个前提条件是满足的，因为 resize 被调用的唯一方式是 full 返回 true，而这只有在 index == array.length 时才会发生。
在 resize 的末尾，我们用新数组替换旧数组（导致旧数组被垃圾回收）。新的 array.length 是旧数组的两倍，而 index 没有改变，所以现在必须为真 index < array.length。这个断言是 resize 的后置条件：在方法完成时必须为真的内容（只要它的前提条件得到满足）。
前提条件、后置条件和不变式是用于分析程序和证明其正确性的有用工具。在本例中，我演示了一种有利于程序分析的编程风格和一种有助于证明正确性的文档风格。
precondition postcondition invariant
ADT client provider wrapper class infix postfix parse token delimiter predicate postcondition
描述
[抽象数据类型 (ADT):] 一种由一组操作定义的数据类型（通常是对象的集合），但可以以多种方式实现。
[客户端:] 使用 ADT 的程序（或编写该程序的人）。
[提供者:] 实现 ADT 的代码（或编写该代码的人）。
[包装类:] 一些 Java 类，如 Double 和 Integer，它们提供对象来包含原始类型，以及对原始类型进行操作的方法。
[私有:] 一个 Java 关键字，表示方法或实例变量不能从当前类定义之外访问。
[中缀:] 一种用运算符位于操作数之间的形式来编写数学表达式的格式。
[后缀:] 一种用运算符位于操作数之后的形式来编写数学表达式的格式。
[解析:] 读取字符或标记字符串并分析其语法结构。
[标记:] 一组字符，在解析时被视为一个单元，就像自然语言中的词语一样。
[分隔符:] 用于分隔标记的字符，就像自然语言中的标点符号一样。
[谓词:] 一种数学命题，要么为真，要么为假。
[后置条件:] 在方法结束时必须为真的谓词（前提是在开始时为真的）。