思考题

给定一个仅包含字符：(,),[,]的字符串，确定输入字符串是否有效。
字符串有效的定义如下：

• 开括号必须用同一类型的括号闭合。
• 开方括号必须按正确顺序闭合。

// 示例1
Input: "()"
Output: true
// 示例2
Input: "()[]{}"
Output: true
// 示例3
Input: "(]"
Output: false

可以先思考一下这个问题，是否可以结合栈解决呢？

栈

栈（stack）又名堆栈，它是一种操作受限的线性表。其限制是仅允许在线性表头进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。

• 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
• 从一个栈删除元素又称作出栈、退栈或弹栈，它是把栈顶元素删掉，使下方的元素成为新的栈顶元素；

栈按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

关于栈我列举一个很贴切的例子，就是一摞叠在一起的书。假设我们平时放书的时候，都是从下往上一本一本的放，取书的时候也都是从上往下一本一本的取，不能从中间任意位置抽取和放置，这就是典型的栈结构。

一叠书.png

如何实现栈呢？

前面我们讲解过数组和链表，栈也可以使用这两个数据结构去实现。基于数组实现的栈，我们称之为数组栈。基于链表实现的栈，我们称之为链式栈。由于数组的特性，数组栈的空间是有界的，当栈的空间不满足需求时，需要执行扩容。而链表理论上则是无界的，因为实际受到物理资源限制。

// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           // 栈的大小

  // 初始化数组，申请一个大小为 n 的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了，直接返回 false，入栈失败。
    if (count == n) return false;
    // 将 item 放到下标为 count 的位置，并且 count 加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空，则直接返回 null
    if (count == 0) return null;
    // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

了解了定义和基本操作，那它的操作的时间、空间复杂度是多少呢？

不管是顺序栈还是链式栈，我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

注意，这里存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

空间复杂度分析是不是很简单？时间复杂度也不难。不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。

Java中的栈的实现

Java中的栈我们主要关注Stack类，它继承自Vector。Vector是线程安全容器，但由于使用synchronized锁，在要求高性能高并发环境下并不推荐。

Stack使用数组存储元素，但凡使用数组构建的数据结构都会有一个共通的问题——需要扩容。在JDK8中，默认情况下Stack的扩容规则是当栈的大小等于容量大小时，则将当前容量扩大为现在容量的两倍。如果要修改默认扩容行为，可以通过构造器设定扩容的步长，以求更合理的配置扩容。

Object (java.lang)
       AbstractCollection (java.util)
              AbstractList (java.util)
                     Vector (java.util)
                            Stack (java.util)

解答思考题

使用栈这种数据结构，使得我们很容易解决诸如逆波兰式、汉诺塔等问题。熟悉栈的定义并不难，但我们对栈的理解不能仅仅停留在静态栈的层面上，更多的需要思考栈的动态性，结合这些动态性我们可以解决哪些问题。

class Solution {
    public boolean isValid(String s) {

        if ((s.length() & 1) == 1) {
            return false;
        }

        HashMap<Character, Character> symbolMap = new HashMap<>();
        symbolMap.put(')', '(');
        symbolMap.put('}', '{');
        symbolMap.put(']', '[');

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

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            switch (c) {
                case ')':
                case '}':
                case ']':
                    if (stack.empty()) {
                        return false;
                    } else if (Objects.equals(stack.lastElement(), symbolMap.get(c))) {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                    break;
                default:
                    stack.push(c);
                    break;
            }
        }
        return stack.empty();
    }
}