5.16 Stacks and Queues

1. Min Stack
   思路：
   两种解法：
   1. 两个栈，一个栈存所有的element, 另一个栈存最小的当前栈中的最小元素，
   ```java
   class MinStack {
   Stack stackMin; //store the min element
   Stack stack;
   //int min; //多余 不需要这个全局最小值， 用stackMin.peek() 来记录全局最小值即可
   }

2. 新建一个自定义的数据类型 node 存val, next, min 三个reference

难点在于对stack的 push() 和 pop() 操作的更新。
压入栈的规则：
假设当前数据为newNum, 先将其压入stack, 然后判断stackMin是否为空：
如果stackMin为空，将newNum也压入stackMin
如果不为空，则比较newNum 和stackMin 的栈顶元素中哪一个更小：
如果newNum更小，将newNum也压入stackMin栈中，同时更新min = newNum
如果stackMin的栈顶元素更小，则stackMin不压入元素

弹出栈的元素从上到下依次增大，栈顶元素既为stackMin中的最小值，也同时为全局最小值，
弹出栈的规则：
先弹出stack中的栈顶元素，记作value, 然后比较当前stackMin的栈顶元素和value哪一个最小：
当value == stackMin.peek(), stackMin 弹出栈顶元素
当value > stackMin.peek(), stackMin 不弹出
不会出现value < stackMin.peek() 的情况，因为stackMin.peek() 是两个栈的最小值

CC189 3.3 Stack of Plates
resizing stack??
关键在于对将 stack 扩展之后，两个stack之间如何建立起链接？ 新建一个reference, 指向stack

3.5 Sort Stack
Write a program to sort a stack such that the smallest items are on the top. (use only one tempory stack)
倒水杯
先设定有两个stack, 一个已经sorted 另一个没有sorted，如何将未sorted的stack与已经sorted的stack 合并为一个sorted stack?

Leetcode 20 Valid Parenthesis
左右必定配对，左括号
for (char c : s.toCharArray()) {...}

LeetCode 331. Verify Preorder Serialization of a Binary Tree
必须要做相关处理 剪枝
String[] strs = preorder.split(",");

public class Solution { 
     public boolean isValidSerialization(String preorder) {
        if (preorder == null) {
            return false;
        }
        String[] strs = preorder.split(','); //must use .split(",") instead of .split(',');
        Stack<String> stack = new Stack<String>();
        for (int i = 0; i < strs.length; i++) {
            String curr = strs[i]; //iterate all the string
            while (curr.equals("#") && !stack.isEmpty() && stack.peek().equals("#")) {
                stack.pop();
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
            stack.push(curr);
        }
        return stack.size() == 1 && stack.peek().equals("#");
    }
}

```