温故：栈|数据结构

对数据结构-栈进行温故，以期获新知

温故系列是我尝试的一种新学习总结方式，在 阅历增长时，总结旧闻，以 期获 新知，并不断迭代。了解更多

本次温故时间：2021年3月

基本概念

目的：存储逻辑关系为 一对一 的数据

特性：出口和入口一致，后进先出、先进后出，先行存储结构

定义：栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的 线性存储结构。

操作：

• 向栈中添加数据，即 进栈 、 入栈 、 压栈, 从栈顶进
• 从栈中取出数据，即 出栈，从栈顶出

线性存储结构

线性结构是一种 有序数据项 的 集合，其中每个数据项都有 唯一 的 前驱 和 后继， 注意：第一个没有前驱，最后一个没有后继。

新数据项加入到数据集中时，只会加入到原有某个数据项 之前 或者 之后

实现思路有两种：

• 顺序栈
• 链栈

区别在于：数据项存放的相对位置，顺序栈用 数组 作为底层实现，而链栈使用 链表 作为底层实现。

JDK中的实现

public class Stack<E> extends Vector<E> {
    public Stack() {
    }

    public E push(E item) {
        addElement(item);

        return item;
    }

    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    public boolean empty() {
        return size() == 0;
    }

    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
}

直接建立在Vector上，细节忽略。

应用场景脑暴

• 页面浏览特性
  • 页面导航，面包屑导航
  • 页面信息存储
• 分步求解中，中间结果的存取特性满足 后进先出 特性
  • 进制转换
  • 括号等成对匹配

这些场景下，可以利用栈的特性以简化问题，不是必须（唯一性），也不一定是最佳

算法题练练手

从LeetCode挑选两道算法题，简单练练手。

简单题：有效的括号

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

1 <= s.length <= 10,000 (注:原内容为10的4次方)
s 仅由括号 '()[]{}' 组成

来源：力扣（LeetCode 链接：https://leetcode-cn.com/problems/valid-parentheses 著作权归领扣网络所有。

读完题目之后，我们可以发现，

• 需要从左到右遍历整个字符串，并且匹配成对的括号
• 发现 左括号 时，需要先作为 中间结果
• 当发现 右括号 时，检查 中间结果 中 最新 的左括号是否对应:
  • 如果不存在左括号、或者不对应，则非法
  • 如果对应，则从 中间结果 中移除。
• 遍历完后，中间结果 被完全匹配，则合法。

中间结果的存取要求非常符合 栈 的功能特性。

static public class Q20 {
        private static final Map<Character, Character> map = new HashMap<Character, Character>() {{
            put('{', '}');
            put('[', ']');
            put('(', ')');
        }};

        public static boolean isValid(String s) {
            final int length = s.length();

            if (length % 2 == 1) //奇数一定不匹配，快速失败
                return false;

            final Stack<Character> stack = new Stack<>();

            for (int i = 0; i < length; i++) {
                Character c = s.charAt(i);
                if (map.containsKey(c)) { //左括号存入栈
                    stack.push(c);
                } else { //右括号处理
                    // 如果不存在左括号、或者不对应，则非法
                    if (stack.isEmpty() /*右边括号多余或者先于对应的左括号*/
                            || c != map.get(stack.pop()) /*类型不匹配*/
                    )
                        return false;
                }
            }

            // 遍历完后，栈中的左括号被完全匹配，则合法。
            return stack.isEmpty();
        }
    }

中等题： 行星碰撞

给定一个整数数组 asteroids，表示在同一行的行星。

对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。

找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1：

输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

示例 2：

输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。

示例 3：

输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。

示例 4：

输入：asteroids = [-2,-1,1,2]
输出：[-2,-1,1,2]
解释：-2 和 -1 向左移动，而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞，
所以最终没有行星发生碰撞。

提示：
    2 <= asteroids.length <= 10,000 (注:原内容为10的4次方)
    -1000 <= asteroids[i] <= 1000
    asteroids[i] != 0

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/asteroid-collision 著作权归领扣网络所有。

读题之后呢,我们发现这是一个需要 分步求解 ，中间结果满足 后进先出 的问题。

思考方向有两个，对于一颗行星：

• 考虑它被撞击的问题
• 考虑它撞击别人的问题

揪着一个思路去处理即可，不要 反复横跳。

采用 考虑它撞击别人的问题 这一思路开始，考虑下完整思路。

• 定义栈A，用于存储幸存的行星
• 从 asteroids 按序取出行星 ast，
• 碰撞问题：考虑 ast 与 A 中的行星可能发生的碰撞 (从栈头到栈尾)
  • 如果无碰撞，则入栈
  • 如果有碰撞，又分为3种可能
    • ast 赢了, A栈头的行星需要出栈，继续考虑 碰撞问题
    • ast 输了，从 asteroids 取下一个行星（如果不存在，则整个过程结束），继续考虑 碰撞问题
    • 同归于尽，A栈头的行星需要出栈，从 asteroids 取下一个行星（如果不存在，则整个过程结束），继续考虑 碰撞问题

我们将这一过程实现：

static public class Q735 {

  public static int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();

    int i = 0;
    final int size = asteroids.length;
    int top;

    while (i < size) {

      int target = asteroids[i];
      //init as -1 mask it not crash
      int crashResult = -1;

      // + & - will crash
      while (!stack.isEmpty() && stack.peek() > 0 && target < 0) {
        top = stack.peek();

        crashResult = top + target;
        //handle crash
        // crash has 3 result:
        // positive: the target lost, next round
        // zero: both lost, next round
        // negative: left lost, if the top of current stack is positive, *if exist*, will crash
        // or just push into stack

        if (crashResult == 0) {
          //both lost
          stack.pop();
          //break the loop
          break;
        } else if (crashResult < 0) {
          //target win
          stack.pop();
        } else {
          break;
        }
      }

      // target win all or won't crash,push into stack
      if (crashResult < 0)
        stack.push(target);
      i++;
    }

    i = stack.size();
    int[] ret = new int[i];
    while (i > 0) {
      ret[i - 1] = stack.pop();
      i--;
    }

    return ret;
  }
}

这样实现会写出很长的代码。如果结合 for循环 和 label，就可以 直译 我们的思路：

static public class Q735 {
  //来源：力扣（LeetCode）
  //链接：https://leetcode-cn.com/problems/asteroid-collision
  //著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
  public static int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();
    for (int ast : asteroids) {
      collision:
      {
        while (!stack.isEmpty() && ast < 0 && 0 < stack.peek()) {
          if (stack.peek() < -ast) {
            stack.pop();
            continue;
          } else if (stack.peek() == -ast) {
            stack.pop();
          }
          break collision;
        }
        stack.push(ast);
      }
    }

    int[] ans = new int[stack.size()];
    for (int t = ans.length - 1; t >= 0; --t) {
      ans[t] = stack.pop();
    }
    return ans;
  }
}

温故总结

栈在底层使用较多，上层业务中，使用场景不是太多。需要用到 线性存储结构 来存贮 中间过程值，并且使用时满足 后进先出，就可以考虑使用栈。

以后在业务开发中，可以多加留心，注意是否可以利用栈简化业务。本篇就到此结束了。