算法动画图解 | 被 "废弃" 的 Java 栈，为什么还在用

公众号：ByteCode，致力于分享最新技术原创文章，涉及 Kotlin、Jetpack、译文、系统源码、 LeetCode / 剑指 Offer / 多线程 / 国内外大厂算法题 等等一系列文章。

在 LeetCode 上不知不觉已经刷了 210+ 题，总提交次数 1000+ 次，从这篇文章开始，每篇算法类型的文章，将会做成动画的形式，每篇文章都会用 Java 和 kotlin 去实现，并且每道题目都有解题思路、时间复杂度、空间复杂度和源代码，更多内容点击下方链接前去查看。

• 剑指 Offer 及国内外大厂面试题解：在线阅读
• LeetCode 系列题解：在线阅读

通过这篇文章你将学习到以下内容：

• 栈的定义
• 栈的实现

• 为什么不推荐使用 Java 栈

• 性能低
• 破坏了原有的数据结构

• 不推荐使用了，为什么现在还在用
• 为什么推荐使用 Deque 接口替换栈

• 效率比 Java 栈快
• 屏蔽掉无关的方法

• Stack 和 ArrayDeque 区别
• 栈的时间复杂度

• 栈的应用：有效的括号

栈的定义

栈是 后入先出（LIFO） 的数据结构，入栈通常使用 push 操作，往栈中插入数据到栈底，出栈使用 pop 操作，从栈顶删除数据。入栈和出栈操作动画如下所示。

栈的实现

栈常用的实现方式是通过动态数组来实现的，在 Java 和 Kotlin 中也内置了栈库 Stack，但是 Stack 已经不推荐使用了。

为什么不推荐使用

• 性能低

性能低是因为 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 来代替，如果在非线程安全的情况下可以使用 ArrayList，线程安全的情况下可以使用 CopyOnWriteArrayList 。

• 破坏了原有的数据结构

栈的定义是在一端进行 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() 等等方法，但是这样会破坏栈原有的结构。所以对于栈的数据结构，不应该有可以在任何位置添加或者删除元素的能力。

为什么现在还在用

但是为什么在实际项目中还有很多小伙伴在使用 Stack。如果你经常刷 LeetCode 应该会见到很多小伙伴使用 Stack 做相关的算法题。总结了一下主要有两个原因。

• JDK 官方是不推荐使用 Stack，之所以还有很多人在使用，是因为 JDK 并没有加 deprecation 注解，只是在文档和注释中声明不建议使用，但是很少有人会去关注其实现细节
• 在做算法题的时候，关注点在解决问题的算法逻辑思路上，并不会关注在不同语言下 Stack 实现细节，但是对于使用 Java 语言的开发者，不仅需要关注算法逻辑本身，也需要关注它的实现细节

为什么推荐使用 Deque 接口替换栈

如果 JDK 不推荐使用 Stack，那应该使用什么集合类来替换栈，一起看看官方的文档。

正如图中标注部分所示，栈的相关操作应该由 Deque 接口来提供，推荐使用 Deque 这种数据结构， 以及它的子类，例如 ArrayDeque。

val stack: Deque<Int> = ArrayDeque()

使用 Deque 接口来实现栈的功能有什么好处：

• 速度比 Stack 快

这个类作为栈使用时可能比 Stack 快，作为队列使用时可能比 LinkedList 快。因为原来的 Java 的 Stack 继承自 Vector，而 Vector 在每个方法中都加了锁，而 Deque 的子类 ArrayDeque 并没有锁的开销。

• 屏蔽掉无关的方法

原来的 Java 的 Stack，包含了在任何位置添加或者删除元素的方法，这些不是栈应该有的方法，所以需要屏蔽掉这些无关的方法。

声明为 Deque 接口可以解决这个问题，在接口中声明栈需要用到的方法，无需管子类是如何是实现的，对于上层使用者来说，只可以调用和栈相关的方法。

Stack 和 ArrayDeque 区别如下所示。

Stack 常用的方法如下所示。

ArrayDeque 常用的方法如下所示。

栈的时间复杂度

栈的核心实现是通过动态数组来实现的，所以在扩容的时候，时间复杂度为 O(n)，其他操作例如 push(E item) 和  pop() 、 peek() 等等时间复杂度为 O(1)。

栈的应用：有效的括号

题解已收藏于 github.com/hi-dhl/Leet…。每道题目都会用 Java 和 kotlin 去实现，并且每道题目都有解题思路、时间复杂度、空间复杂度和源代码，

题目描述

给定一个字符串, 只包括 '('，')'，'{'，'}'，'['，']'，判断字符串是否有效

有效字符串需要满足以下条件：

• 左括号必须用相同类型的右括号闭合
• 左括号必须以正确的顺序闭合

注意空字符串可被认为是有效字符串。

Example 1:
    Input: "()"
    Output: true
Example 2:
    Input: "()[]{}"
    Output: true
Example 3:
    Input: "(]"
    Output: false
Example 4:
    Input: "([)]"
    Output: false
Example 5:
    Input: "{[]}"
    Output: true

算法流程

1. 如果遇到左括号，将对应的右括号压入栈中
2. 如果遇到右括号

• 判断当前栈是否为空
• 如果不为空，判断当前元素是否和栈顶元素相等
• 如果不相等，发现了不符合的括号，提前返回 false，结束循环

3. 重复执行「步骤 1」 和「步骤 2」
4. 循环结束之后，通过判断栈是否为空，来检查是否是有效的括号

复杂度分析

假设字符串的长度为 N 则：

• 时间复杂度：O(N)。正确有效的括号需要遍历了一次字符串，所需要的时间复杂度为 O(N)。
• 空间复杂度：O(N)。如果输入字符串全是左括号，例如 (((((((，栈的大小即为输入字符串的长度，所需要的空间复杂度为 O(N)

Kotlin 实现

class Solution {
    fun isValid(s: String): Boolean {
        val stack = ArrayDeque<Char>()
        // 开始遍历字符串
        for (c in s) {
            when (c) {
                // 遇到左括号，将对应的右括号压入栈中
                '(' -> stack.push(')')
                '[' -> stack.push(']')
                '{' -> stack.push('}')
                else -> {
                    // 遇到右括号，判断当前元素是否和栈顶元素相等，不相等提前返回，结束循环
                    if (stack.isEmpty() || stack.poll() != c) {
                        return false
                    }
                }
            }
        }
        // 通过判断栈是否为空，来检查是否是有效的括号
        return stack.isEmpty()
    }
}

Java 实现

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<Character>();
        // 开始遍历字符串
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 遇到左括号，则将其对应的右括号压入栈中
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else {
                // 遇到右括号，判断当前元素是否和栈顶元素相等，不相等提前返回，结束循环
                if (stack.isEmpty() || stack.poll() != c) {
                    return false;
                }
            }
        }
        // 通过判断栈是否为空，来检查是否是有效的括号
        return stack.isEmpty();
    }
}

仓库 KtKit 是用 Kotlin 语言编写的小巧而实用的工具库，包含了项目中常用的一系列工具, 正在逐渐完善中。

• KtKit 仓库地址：https://github.com/hi-dhl/KtKit
• KtKit 在线阅读：https://ktkit.hi-dhl.com

如果这个仓库对你有帮助，请在仓库右上角帮我 star 一下，非常感谢你的支持，同时也欢迎你提交 PR

如果有帮助 点个赞 就是对我最大的鼓励

代码不止，文章不停

最后推荐我一直在更新维护的项目和网站：

• 个人博客，将所有文章进行分类，欢迎前去查看 hi-dhl.com
  
• 计划建立一个最全、最新的 AndroidX Jetpack 相关组件的实战项目 以及 相关组件原理分析文章，正在逐渐增加 Jetpack 新成员，仓库持续更新，欢迎前去查看：AndroidX-Jetpack-Practice
  
• LeetCode / 剑指 offer / 国内外大厂面试题 / 多线程 题解，语言 Java 和 kotlin，包含多种解法、解题思路、时间复杂度、空间复杂度分析

• 剑指 offer 及国内外大厂面试题解：在线阅读
• LeetCode 系列题解：在线阅读

• 最新 Android 10 源码分析系列文章，了解系统源码，不仅有助于分析问题，在面试过程中，对我们也是非常有帮助的，仓库持续更新，欢迎前去查看 Android10-Source-Analysis
  
• 整理和翻译一系列精选国外的技术文章，每篇文章都会有译者思考部分，对原文的更加深入的解读，仓库持续更新，欢迎前去查看 Technical-Article-Translation

近期必读热门文章

• 影响性能的 Kotlin 代码（一）
• Jetpack Splashscreen 解析 | 助力新生代 IT 农民工 事半功倍
• 为数不多的人知道的 Kotlin 技巧及解析(三)
• 为数不多的人知道的 Kotlin 技巧以及 原理解析（二）
• 为数不多的人知道的 Kotlin 技巧以及 原理解析（一）
• 揭秘 Kotlin 中的 == 和 ===
• Kotlin 密封类进化了
• Kotlin 中的密封类 优于 带标签的类
• Kotlin Sealed 是什么？为什么 Google 都在用
• Android 12 行为变更，对应用产生的影响
• 图解多平台 AndroidStudio 技巧(三)
• Kotlin StateFlow 搜索功能的实践 DB + NetWork
• Kotlin 插件的落幕，ViewBinding 的崛起
• 竟然如此简单，DataBinding 和 ViewBinding