公众号：ByteCode，致力于分享最新技术原创文章，涉及 Kotlin、Jetpack、译文、系统源码、 LeetCode / 剑指 Offer / 多线程 / 国内外大厂算法题 等等一系列文章。
这篇文章源于对 stack-vs-deque 文章的思考，也是对我上一篇文章 算法动画图解 | 被 "废弃" 的 Java 栈，为什么还在用 内容的补充。
通过这篇文章你将学习到以下内容：
- 为什么不推荐使用 Java 栈
- JDK 推荐使用
ArrayDeque代替Stack真的合理吗 - 如何实现一个真正意义上的栈
在开始讨论之前，我们先来简单的回顾上一篇文章的内容。
为什么不推荐使用 Java 栈
栈是 后入先出（LIFO） 的数据结构，入栈通常使用 push 操作，往栈中插入数据到栈底，出栈使用 pop 操作，从栈顶删除数据。
栈是非常好的数据结构，但是 Java 栈的实现，存在以下问题，所以 JDK 不推荐使用 Java 栈。
- 性能低
性能低是因为 Stack 继承自 Vector， 而 Vector 在每个方法中都加了锁，如下所示：
......
public synchronized void trimToSize() { }
public synchronized void ensureCapacity(int minCapacity) { }
public synchronized void setSize(int newSize) { }
public synchronized int capacity() { }
public synchronized int size() { }
public synchronized boolean isEmpty() { }
......
由于需要兼容老的项目，很难在原有的基础上进行优化，因此 Vector 就被淘汰掉了，因此使用 ArrayList 和 CopyOnWriteArrayList 来代替，在线程安全的情况下可以使用 CopyOnWriteArrayList，否则非线程安全的情况下可以使用 ArrayList。
- 破坏了原有的数据结构
栈的定义是在一端进行 push 和 pop 操作，除此之外不应该包含其他 入栈和出栈 的方法，但是 Stack 继承自 Vector，使得 Stack 可以使用父类 Vector 公有的方法，如下所示。
val stack = Stack<Int>()
stack.push(6)
stack.add(1,10)
stack.removeAt(1)
stack.pop()
stack.addAll(arrayListOf())
......
正如你所见，除了调用 push() 和 pop() 方法之外，还可以调用 addXXX() 、 removeXXX() 等等方法，但是这样会破坏栈原有的结构。所以对于栈的数据结构，不应该有可以在任何位置添加或者删除元素的能力。
JDK 推荐使用 ArrayDeque 代替 Stack
在 JDK 文档中，栈的相关操作应该由 Deque 接口来提供，推荐使用 Deque 的子类 ArrayDeque 代替 Stack。如下图标注部分所示。
使用 Deque 接口来实现栈的功能有以下好处：
- 速度比
Stack快
这个类作为栈使用时可能比 Stack 快，作为队列使用时可能比 LinkedList 快。因为原来的 Java 的 Stack 继承自 Vector，而 Vector 在每个方法中都加了锁，而 Deque 的子类 ArrayDeque 并没有锁的开销。
- 屏蔽掉无关的方法
原来的 Java 的 Stack，包含了在任何位置添加或者删除元素的方法，这些不是栈应该有的方法，所以需要屏蔽掉这些无关的方法。
声明为 Deque 接口可以解决这个问题，在接口中声明栈需要用到的方法，无需管子类是如何是实现的，对于上层使用者来说，只可以调用和栈相关的方法。
大神不推荐使用 ArrayDeque 代替 Stack
既然使用 Deque 接口来实现栈有这么多好处，那为什么大神不推荐使用 ArrayDeque 代替 Stack。
baddotrobot.com/blog/2013/0…
因为接口 Deque 是双端队列的线性数据结构, 也就是说可以在两端进行插入和删除操作。而栈只能在一端做插入和删除操作。
栈的定义是在一端进行 push 和 pop 操作，除此之外不应该包含其他 入栈和出栈 的方法，但是基于 Deque 接口来实现栈，还可以在另外一端进行操作，如下所示。
val stack: Deque<Int> = ArrayDeque()
stack.push(1)
stack.poll() // 栈为空时会抛出异常
stack.peek() // 栈为空时返回 null
stack.offerLast(2)
stack.pollLast()
stack.peekLast()
如上所示，还可以调用 offerLast() 、 pollLast() 、 peekLast() 等等方法，往队列的另一端插入数据。
如果是在做算法题目无论使用 ArrayDeque 还是 Stack 都可以，因为关注点不一样，在做算法题的时候，关注点在解决问题的算法逻辑思路上。但是在大型的项目中不建议直接使用 Stack，也不推荐使用 ArrayDeque 代替 Stack。我们可以基于 ArrayDeque 封装一个真正的栈，只允许在一端做插入和删除操作，如下所示。
interface Stack<E> {
fun push(e: E)
fun pop(): E?
fun peek(): E?
fun size(): Int
fun empty(): Boolean
}
class ArrayStack<E> : Stack<E> {
private val deque = ArrayDeque<E>()
override fun push(e: E) = deque.push(e)
override fun pop(): E? = deque.poll()
override fun peek(): E? = deque.peek()
override fun size() = deque.size
override fun empty(): Boolean = deque.isEmpty()
}
如果有帮助 点个赞 就是对我最大的鼓励
代码不止，文章不停
欢迎关注公众号：ByteCode，查看最新技术文章
最后推荐我一直在更新维护的项目和网站：
-
个人博客，将所有文章进行分类，欢迎前去查看 hi-dhl.com
-
更多 Kotlin 、Jetpack 实战开源项目，欢迎前往查看 github
-
LeetCode / 剑指 offer / 国内外大厂面试题 / 多线程 题解，语言 Java 和 kotlin，包含多种解法、解题思路、时间复杂度、空间复杂度分析
- 剑指 offer 及国内外大厂面试题解： 在线阅读
- LeetCode 系列题解： 在线阅读
近期必读热门文章
- 算法动画图解 | 被 "废弃" 的 Java 栈，为什么还在用
- 影响性能的 Kotlin 代码（一）
- Jetpack Splashscreen 解析 | 助力新生代 IT 农民工 事半功倍
- 为数不多的人知道的 Kotlin 技巧及解析(三)
- 为数不多的人知道的 Kotlin 技巧以及 原理解析（二）
- 为数不多的人知道的 Kotlin 技巧以及 原理解析（一）
- 揭秘 Kotlin 中的 == 和 ===
- Kotlin 密封类进化了
- Kotlin 中的密封类 优于 带标签的类
- Kotlin Sealed 是什么？为什么 Google 都在用
- Android 12 行为变更，对应用产生的影响
- 图解多平台 AndroidStudio 技巧(三)
- Kotlin StateFlow 搜索功能的实践 DB + NetWork
- Kotlin 插件的落幕，ViewBinding 的崛起
