为什么不推荐 ArrayDeque 代替 Stack
- 如果评论区没有及时回复,欢迎来公众号:ByteCode 咨询
- 公众号:ByteCode。致力于分享最新技术原创文章,涉及 Kotlin、Jetpack、算法、译文、系统源码相关的文章
这篇文章源于对 stack-vs-deque 文章的思考,也是对我上一篇文章 算法动画图解 | 被 “废弃” 的 Java 栈,为什么还在用 内容的补充。
通过这篇文章你将学习到以下内容:
- 为什么不推荐使用 Java 栈
- JDK 推荐使用
ArrayDeque
代替Stack
真的合理吗 - 如何实现一个真正意义上的栈
在开始讨论之前,我们先来简单的回顾上一篇文章的内容。
为什么不推荐使用 Java 栈
栈是 后入先出(LIFO) 的数据结构,入栈通常使用 push
操作,往栈中插入数据到栈底,出栈使用 pop
操作,从栈顶删除数据。
栈是非常好的数据结构,但是 Java 栈的实现,存在以下问题,所以 JDK 不推荐使用 Java 栈。
- 性能低
性能低是因为 Stack
继承自 Vector
, 而 Vector
在每个方法中都加了锁,如下所示:
...... |
由于需要兼容老的项目,很难在原有的基础上进行优化,因此 Vector
就被淘汰掉了,因此使用 ArrayList
和 CopyOnWriteArrayList
来代替,在线程安全的情况下可以使用 CopyOnWriteArrayList
,否则非线程安全的情况下可以使用 ArrayList
。
- 破坏了原有的数据结构
栈的定义是在一端进行 push
和 pop
操作,除此之外不应该包含其他 入栈和出栈 的方法,但是 Stack
继承自 Vector
,使得 Stack
可以使用父类 Vector
公有的方法,如下所示。
val stack = Stack<Int>() |
正如你所见,除了调用 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
。
http://baddotrobot.com/blog/2013/01/10/stack-vs-deque
因为接口 Deque
是双端队列的线性数据结构, 也就是说可以在两端进行插入和删除操作。而栈只能在一端做插入和删除操作。
栈的定义是在一端进行 push
和 pop
操作,除此之外不应该包含其他 入栈和出栈 的方法,但是基于 Deque
接口来实现栈,还可以在另外一端进行操作,如下所示。
val stack: Deque<Int> = ArrayDeque() |
如上所示,还可以调用 offerLast()
、 pollLast()
、 peekLast()
等等方法,往队列的另一端插入数据。
如果是在做算法题目无论使用 ArrayDeque
还是 Stack
都可以,因为关注点不一样,在做算法题的时候,关注点在解决问题的算法逻辑思路上。但是在大型的项目中不建议直接使用 Stack
,也不推荐使用 ArrayDeque
代替 Stack
。我们可以基于 ArrayDeque
封装一个真正的栈,只允许在一端做插入和删除操作,如下所示。
interface Stack<E> { |
如果有帮助 点个赞 就是对我最大的鼓励
代码不止,文章不停
欢迎关注公众号:ByteCode,查看最新技术文章
- 本文作者:hi-dhl
- 本文标题:为什么不推荐 ArrayDeque 代替 Stack
- 本文链接:https://hi-dhl.com/2021/09/24/algorithm/02-arraydeque/
- 版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 hi-dhl