Java中的栈Stack，Deque，ArrayDeque，LinkedList - 编程导航 | 一线开发者编程经验和技术实战分享

今天在做算法题目的时候，使用

Stack<Integer> st = new Stack<>();

创建栈，但是在leetcode上时间使用了250ms，我就想为什么时间这么久，我抱着试试的心态，用了以前使用过的Deque

Deque<Integer> st=new ArrayDeque<>();

卧槽，发现竟然只要25ms，然后我就去搜，为什么？我在网上搜了好多，发现许多帖子不是在说“栈”这种数据结构不被推荐使用，而是在说 Java 语言中，Stack 这个类不被推荐使用。为什么？实际上，这个不推荐不是某个技术专家或者某个企业的规范标准，而是来自 Java 官方。

The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.

When a stack is first created, it contains no items.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:

Deque<Integer> stack = new ArrayDeque<Integer>();

官方解释的，看不懂，翻译下大概意思：

一个更加完整，一致的，后进先出的栈相关的操作，应该由 Deque 接口提供。并且，也推荐使用 Deque 这种数据结构（比如 ArrayDeque）来实现。

因此，如果你想使用栈这种数据结构，Java 官方推荐的写法是这样的（假设容器中的类型是 Integer）：

Deque<Integer> stack = new ArrayDeque<Integer>();

下面，我们先来看看 Stack 到底怎么了？再来看看为什么使用 Deque？

Java 中的 Stack 类，最大的问题是，继承了 Vector 这个类。

Vector 是什么类？简单来说，Vector 就是一个动态数组。大家应该都知道，ArrayList 也是动态数组。ArrayList 和 Vector 的区别我们后面再讨论。我们先来看一下，Stack 这个类继承 Vector，会产生什么问题？最大的问题在于，继承使得子类继承了父类的所有公有方法。

而 Vector 作为动态数组，是有能力在数组中的任何位置添加或者删除元素的。因此，Stack 继承了 Vector，Stack 也有这样的能力！

大家可以尝试如下的代码片段，在 Java 中是正确的：

Stack<Integer> st = new Stack<>();

st.push(1);

st.push(2);

//指定在1这个位置插入一个123

st.add(1,123);

但很显然，我们不希望对于栈来说，可以指定在 1 这个位置插入一个 123。这一点都不 123，而是破坏了栈这种数据结构的封装。

问题出在哪里？

Java 中的 Stack 实现，是被业界一直认为非常糟糕的实现。实际上，它犯了面向对象设计领域的一个基本错误：Stack 和 Vector 之间的关系，不应该是继承关系，而应该是组合关系（composition）。

关于继承关系和组合关系的区别，相信大家在 OOD （面向对象设计-- 将各个功能和模块向上级申请和审批过程）学习过程中，听过无数遍。继承关系描述的是 is-a 的关系，即“是一个”的关系。猫是一个动物，所以猫这个类可以继承动物类；程序员是一个雇员，所以程序员这个类可以继承雇员类。车里有一台发动机，所以发动机这个类和车这个类之间，应该是组合关系，即车中包含一个成员变量，是发动机这个类的对象；电脑里有 CPU，内存，显卡。所以 CPU，内存，显卡，这些类和电脑类之间的关系，都应该是组合关系。

比如，栈这种数据结构，和动态数组这种数据结构之间，到底应该是 is-a 的关系？还是 has-a 的关系？

使用自然语言描述，听起来似乎说：栈是一个动态数组，毛病不大。但其实仔细思考，就会发现，栈不是一个动态数组！

因此，很多时候，对于现实中并不存在的设计对象，人类很可能想不清楚 is-a 和 has-a 的关系。在这里，我再提供一个简单的原则：判断一下，如果设计成继承关系的话，我们是否有可能把子类进行向上的父类转型？如果可能，则应该设计成继承关系，否则应该是组合关系。换句话说，在这个例子中，我们是否可能将栈当做一个动态数组使用？答案是不可能。所以，栈和动态数组之间的关系不应该是继承关系。

Java 官方不知道这个 Stack 类的实现不好吗？为什么不改？

Java 官方当然知道这个实现不好。但是，因为要保持兼容性（backward compatibility），对于已经正式发布的代码，Java 官方不能做接口设计层面的修改。否则，使用老版本 Java 的程序，将在新的 Java 环境下无法执行，这是 Java 官方不愿意看到的。Java 官方可以做到的是，将这个类标志成“弃用”（deprecated），以让新版本的开发者不再允许使用这个类，但老版本的程序，还能继续执行。但是，这么多年了，Java 官方也并没有将 Stack 标为“弃用”，只是在文档上注明“不建议使用”。

什么是 Deque 接口？

Deque 是双端队列的意思。所谓的双端队列，就是能在线性数据结构的两段，进行插入和删除操作。

大家可以想象，由于 Stack 的定义是在同一端进，同一端出。所以，如果 Deque 可以满足在两段进行插入和删除，自然也能在同一端进行插入和删除，也就是可以以此为基础，做成一个 stack。

等等！这里有问题！

很多同学应该能马上反应过来了。这里有问题！

因为我们根据 Java 官方推荐的方法声明的这个 stack，虽然变量名称是 stack，但它实际上是一个 deque。这就意味着，这个 stack，可以在两段做插入和删除操作！但是，真正的栈，只能在同一端做插入和删除操作！

这难道不是重蹈了 Stack 这个类的覆辙？毕竟，我们最开始分析，就说 Stack 这个类的一大问题，是继承了 Vector 这个类的若干我们不需要的方法，破坏了封装性，比如在任何一个位置插入一个元素。现在这个基于 Deque 接口的 stack，依然有我们不需要的方法啊！

没错！这就是 Java 的历史遗留问题了。这个问题至此已经无解了。因为 Stack 这个关键字被占据了。Java 官方不想推出一个叫做 RealStack 或者 CorrectStack 一类的接口名称。所以，按照 Java 官方的推荐所建立的这个 stack，依然不完美。

但至今为止，Java 暂时只是做到这个份儿上。

或许，Oracle 少打一些官司，多研究一下如何处理这些历史遗留问题，Java 能更好吧。

所以，在实际的工程应用上，有人也并不建议使用 Deque 做为 stack 的实现，而是自己再做一层封装。

这个代码其实很简单，因为这本质是一个设计问题，而不是逻辑问题。有兴趣的同学可以看一下这篇文章：

http://baddotrobot.com/blog/2013/01/10/stack-vs-deque/

链表呢？

再说一个小问题。

大家可以看到，Java 官方推荐的创建栈的方式，使用了 Deque 接口。并且，在底层实现上，使用了 ArrayDeque，也就是基于动态数组的实现。为什么？

大家应该都知道，动态数组是可以进行扩容操作的。在触发扩容的时候，时间复杂度是 O(n) 的，但整体平均时间复杂度（Amortized Time）是 O(1)。

但是，基于链表的实现，不会牵扯到扩容问题，因此，每一次添加操作，从时间复杂度的角度，都是 O(1) 的。

虽然如此，可是实际上，当数据量达到一定程度的时候，链表的性能是远远低于动态数组的。

这是因为，对于链表来说，每添加一个元素，都需要重新创建一个 Node 类的对象，也就是都需要进行一次 new 的内存操作。而对内存的操作，是非常慢的。

也就是使用 LinkedList，会比使用 ArrayDeque 慢 5 倍以上。

因此，甚至有人建议：在实践中，尤其是面对大规模数据的时候，不应该使用链表！

哎，一道leetcode竟然有这么多的东西，继续学习吧，还是太弱！！！