第6章 栈

先进后出 LinkedList 有最近一直性的东西用栈 比如括号匹配

20. 括号匹配

class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            }
            if (c == ')' || c == '}' || c == ']') {
                if(stack.peek() == null ||stack.pop() != c) return false;
            }
        }
        return stack.peek() == null ;
    }
}

155. 最小栈

class MinStack {
    private Node top;
    /** initialize your data structure here. */
    public MinStack() {
    }
    public void push(int val) {
        if (top == null)
            top = new Node(val, val);
        else {
            top = new Node(val, Math.min(val, top.min), top);
        }
    }
    public void pop() {
        top = top.pre;
    }
    public int top() {
        return top.val;
    }
    public int getMin() {
        return top.min;
    }
    private class Node {
        int val;
        int min;
        Node pre;
        public Node (int val, int min, Node pre) {
            this(val,min);
            this.pre = pre;
        }
        public Node (int val, int min) {
            this.val = val;
            this.min = min;
        }
    }
}