堆栈Stack · 《Java 编程思想》第五版

## [堆栈Stack](https://lingcoder.gitee.io/onjava8/#/book/12-Collections?id=%e5%a0%86%e6%a0%88stack) 堆栈是“后进先出”（LIFO）集合。它有时被称为*叠加栈*（pushdown stack），因为最后“压入”（push）栈的元素，第一个被“弹出”（pop）栈。经常用来类比栈的事物是带有弹簧支架的自助餐厅托盘。最后装入的托盘总是最先拿出来使用的。 Java 1.0 中附带了一个**Stack**类，结果设计得很糟糕（为了向后兼容，我们永远坚持 Java 中的旧设计错误）。Java 6 添加了**ArrayDeque**，其中包含直接实现堆栈功能的方法： ~~~ // collections/StackTest.java import java.util.*; public class StackTest { public static void main(String[] args) { Deque<String> stack = new ArrayDeque<>(); for(String s : "My dog has fleas".split(" ")) stack.push(s); while(!stack.isEmpty()) System.out.print(stack.pop() + " "); } } /* Output: fleas has dog My */ ~~~ 即使它是作为一个堆栈在使用，我们仍然必须将其声明为**Deque**。有时一个名为**Stack**的类更能把事情讲清楚： ~~~ // onjava/Stack.java // A Stack class built with an ArrayDeque package onjava; import java.util.Deque; import java.util.ArrayDeque; public class Stack<T> { private Deque<T> storage = new ArrayDeque<>(); public void push(T v) { storage.push(v); } public T peek() { return storage.peek(); } public T pop() { return storage.pop(); } public boolean isEmpty() { return storage.isEmpty(); } @Override public String toString() { return storage.toString(); } } ~~~ 这里引入了使用泛型的类定义的最简单的可能示例。类名称后面的告诉编译器这是一个参数化类型，而其中的类型参数**T**会在使用类时被实际类型替换。基本上，这个类是在声明“我们在定义一个可以持有**T**类型对象的**Stack**。”**Stack**是使用**ArrayDeque**实现的，而**ArrayDeque**也被告知它将持有**T**类型对象。注意，`push()`接受类型为**T**的对象，而`peek()`和`pop()`返回类型为**T**的对象。`peek()`方法将返回栈顶元素，但并不将其从栈顶删除，而`pop()`删除并返回顶部元素。如果只需要栈的行为，那么使用继承是不合适的，因为这将产生一个具有**ArrayDeque**的其它所有方法的类（在[附录：集合主题](https://lingcoder.gitee.io/onjava8/#/)中将会看到，**Java 1.0**设计者在创建**java.util.Stack**时，就犯了这个错误）。使用组合，可以选择要公开的方法以及如何命名它们。下面将使用**StackTest.java**中的相同代码来演示这个新的**Stack**类： ~~~ // collections/StackTest2.java import onjava.*; public class StackTest2 { public static void main(String[] args) { Stack<String> stack = new Stack<>(); for(String s : "My dog has fleas".split(" ")) stack.push(s); while(!stack.isEmpty()) System.out.print(stack.pop() + " "); } } /* Output: fleas has dog My */ ~~~ 如果想在自己的代码中使用这个**Stack**类，当在创建其实例时，就需要完整指定包名，或者更改这个类的名称；否则，就有可能会与**java.util**包中的**Stack**发生冲突。例如，如果我们在上面的例子中导入 \**java.util.\*\**，那么就必须使用包名来防止冲突： ~~~ // collections/StackCollision.java public class StackCollision { public static void main(String[] args) { onjava.Stack<String> stack = new onjava.Stack<>(); for(String s : "My dog has fleas".split(" ")) stack.push(s); while(!stack.isEmpty()) System.out.print(stack.pop() + " "); System.out.println(); java.util.Stack<String> stack2 = new java.util.Stack<>(); for(String s : "My dog has fleas".split(" ")) stack2.push(s); while(!stack2.empty()) System.out.print(stack2.pop() + " "); } } /* Output: fleas has dog My fleas has dog My */ ~~~ 尽管已经有了**java.util.Stack**，但是**ArrayDeque**可以产生更好的**Stack**，因此更可取。还可以使用显式导入来控制对“首选”**Stack**实现的选择： ~~~ import onjava.Stack; ~~~ 现在,任何对**Stack**的引用都将选择**onjava**版本，而在选择**java.util.Stack**时，必须使用全限定名称（full qualification）。