Stack

应用场景

任何需要记住最近一步运算结果的场景。

使用技巧

掌握好两个操作，入栈与出栈。

1。入栈，通常是为了保存之前的运算结果，即已经完成了运算的一些节点。 For example，binary tree pre-order traversal，栈里存的就是已经遍历过当前节点和左子树的所有节点，出栈的时候只需要判断右子树即可。

2。出栈，通常是为了进行新的计算。

括号一类的题目用 Stack 来判断 开 与 闭，非常方便。

经典题目

150 Evaluate Reverse Polish Notation

栈的经典题之一。每次遇到操作符，从栈中pop 头两个数字；每次遇到数字，直接进栈。

public int evalRPN(String[] tokens) {
    Deque<Integer> numbers = new LinkedList<>();
    for (String cur: tokens) {
        if (cur.equals("+")) {
            int first = numbers.pollLast();
            int second = numbers.pollLast();
            numbers.add(first + second);
        } else if (cur.equals("-")) {
            int first = numbers.pollLast();
            int second = numbers.pollLast();
            numbers.add(second - first);
        } else if (cur.equals("*")) {
            int first = numbers.pollLast();
            int second = numbers.pollLast();
            numbers.add(first * second);
        } else if (cur.equals("/")) {
            int first = numbers.pollLast();
            int second = numbers.pollLast();
            numbers.add(second / first);
        } else {
            numbers.add(Integer.valueOf(cur));
        }
    }
    return numbers.pollLast();
}

224 Basic Calculator

很明显，要用Stack做。这题的难点在于，运算有加减法，优先级的话得先计算括号里的数。 这里用3个变量，res代表目前括号里的目前结果，number代表目前的数，sign代表上一个符号。

public int calculate(String s) {
    Deque<Integer> numberStack = new LinkedList<>();
    int res = 0;
    int number = 0;
    int sign = 1;
    for (int i = 0; i < s.length(); i++) {
        char cur = s.charAt(i);
        if (Character.isDigit(cur)) {
            number = number * 10 + (cur - '0');
        } else if (cur == '+') {
            res += sign * number;
            number = 0;
            sign = 1;
        } else if (cur == '-') {
            res += sign * number;
            number = 0;
            sign = -1;
        } else if (cur == '(') {
            numberStack.push(res);
            numberStack.push(sign);
            res = 0;
            sign = 1;
        } else if (cur == ')') {
            res += sign * number;
            number = 0;
            res *= numberStack.pop();
            res += numberStack.pop();
        }
    }
    if (number != 0) res += sign * number;
    return res;
}

227 Basic Calculator II

public int calculate(String s) {
    int number = 0;
    char sign = '+';
    Deque<Integer> numberStack = new LinkedList<>();
    
    for (int i = 0; i < s.length(); i++) {
        char cur = s.charAt(i);
        if (Character.isDigit(cur)) {
            number = number * 10 + (cur - '0');
        } 
        if ((!Character.isDigit(cur) && cur != ' ') || i == s.length() - 1) {
            if (sign == '+') {
                numberStack.push(number);
            } else if (sign == '-') {
                numberStack.push(-number);
            } else if (sign == '*') {
                numberStack.push(numberStack.pop() * number);
            } else if (sign == '/') {
                numberStack.push(numberStack.pop() / number);
            }
            number = 0;
            sign = cur;
        }
    }
    int res = 0;
    for (int i : numberStack) {
        res += i;
    }
    return res;
}