为什么不推荐 ArrayDeque 代替 Stack

为什么不推荐 ArrayDeque 代替 Stack

  • 如果评论区没有及时回复,欢迎来公众号:ByteCode 咨询
  • 公众号:ByteCode。致力于分享最新技术原创文章,涉及 Kotlin、Jetpack、算法、译文、系统源码相关的文章

这篇文章源于对 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 就被淘汰掉了,因此使用 ArrayListCopyOnWriteArrayList 来代替,在线程安全的情况下可以使用 CopyOnWriteArrayList,否则非线程安全的情况下可以使用 ArrayList

  • 破坏了原有的数据结构

栈的定义是在一端进行 pushpop 操作,除此之外不应该包含其他 入栈和出栈 的方法,但是 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
http://baddotrobot.com/blog/2013/01/10/stack-vs-deque

因为接口 Deque 是双端队列的线性数据结构, 也就是说可以在两端进行插入和删除操作。而栈只能在一端做插入和删除操作。

栈的定义是在一端进行 pushpop 操作,除此之外不应该包含其他 入栈和出栈 的方法,但是基于 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,查看最新技术文章


致力于分享一系列 Android 系统源码、逆向分析、算法、翻译、Jetpack 源码相关的文章,在技术的道路上一起前进

Android10 源码分析

正在写一系列的 Android 10 源码分析的文章,了解系统源码,不仅有助于分析问题,在面试过程中,对我们也是非常有帮助的,如果你同我一样喜欢研究 Android 源码,可以关注我 GitHub 上的 Android10-Source-Analysis

算法题库的归纳和总结

由于 LeetCode 的题库庞大,每个分类都能筛选出数百道题,由于每个人的精力有限,不可能刷完所有题目,因此我按照经典类型题目去分类、和题目的难易程度去排序。

  • 数据结构: 数组、栈、队列、字符串、链表、树……
  • 算法: 查找算法、搜索算法、位运算、排序、数学、……

每道题目都会用 Java 和 kotlin 去实现,并且每道题目都有解题思路,如果你同我一样喜欢算法、LeetCode,可以关注我 GitHub 上的 LeetCode 题解:Leetcode-Solutions-with-Java-And-Kotlin

精选国外的技术文章

目前正在整理和翻译一系列精选国外的技术文章,不仅仅是翻译,很多优秀的英文技术文章提供了很好思路和方法,每篇文章都会有译者思考部分,对原文的更加深入的解读,可以关注我 GitHub 上的 Technical-Article-Translation

评论