Stack In Java——对java中栈使用的一些思考

栈的介绍

栈（Stack）是一种后入先出（LIFO）的数据结构。经常用来形象说明栈的结构的例子是书箱：把书平放到书箱里，先取出来的书是最后放进去的。

应该使用Stack类吗？

相信大多数人（也包括我），在调用Java中封装好的数据结构以在代码中使用栈结构时，往往使用java.util.Stack类。

// import java.util.*;

	Stack<Integer> stack = new Stack<>();
    stack.push(1);
    while (!stack.empty()){
    	System.out.println(stack.pop());
    }

这难道不是很正常吗？就像使用集合时调用Set，使用列表时调用List一样。既然是Java中所定义好的以Stack命名的结构，那就应该是Java设计者们所设计的最合适、最好用的结构了。

然而并不是这样。
甚至你去查看JDK的官方文档，都能发现这么一段话：

“Deque接口及其实现提供了更完整和一致的LIFO堆栈操作集，这些接口应优先于此类”

令人惊讶，Java官方竟然推荐使用队列（Deque）来实现栈！这一切的原因都在文档中的另一句话：“从以下版本开始：JDK1.0”

为什么不应该使用Stack类？

Stack类继承自Vector类。Vector是一个动态数组，因而Vector可以在数组中操作任意一个位置的元素。
而因为Stack继承自Vector，所以Vector的所有公有方法Stack都可以使用——这就意味着，Stack也可以在任意位置添加或删除元素！

	Stack<Integer> stack = new Stack<>();
	stack.push(1);
	stack.push(2);
	stack.add(1,3);
	System.out.println(stack);

[1, 3, 2]

上面的代码是可以运行的。一个设计为后入先出的结构，竟然可以在其他位置插入元素？你无法想象其他人在使用栈时会不会有意或无意地做出这些操作——一旦做出，代码的安全性荡然无存。

Java的设计者在设计Stack时犯了如此荒唐的错误。如果Stack和Vector的关系不是继承而是组合（Stack里应该拥有一个动态数组，而不是继承自一个数组！），那么今天我们就不会在这里讨论这个糟糕的问题。

现在，为了保证Java代码的兼容性，这段糟糕的设计仍然保留在JDK中。但是我们应该了解Stack的缺陷，并在自己的代码中避免它。

用什么结构来替代Stack类？

1. Deque

用一个ArrayDeque可以实现和Stack相同的功能，这也是Java官方所推荐的做法。

	Deque<Integer> stack = new ArrayDeque<>();
	stack.push(1);
	stack.push(2);
	stack.push(3);
	while (!stack.isEmpty())
		System.out.println(stack.pop());

3
2
1

2. LinkedList

没错，用LinkedList也可以实现同样的功能。只不过，LinkedList的接口不那么直接，或许需要你编写一个自己的Stack类来包装一下。

import java.util.LinkedList;

public class Stack<T> {
    LinkedList<T> list;
    public Stack(){
        list = new LinkedList<>();
    }
    
    public void push(T t){
        list.addFirst(t);
    }
    
    public <T> T pop(){
        return (T) list.removeFirst();
    }
    
    public <T> T peek(){
        return (T) list.getFirst();
    }
    
    public boolean empty(){
        return list.isEmpty();
    }
}

用泛型可以很容易地写出通用的数据结构。而且，通过LinkedList，可以自定义不同的栈，比如双向栈。你可以自己实现一下。

结语

不要使用java.util.Stack！这是本篇文章的核心论点。使用Stack可能会导致你被面试官挂掉，从今天起培养用Deque代替Stack的习惯。