栈

LeetCode

20. 有效的括号

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        Stack<Character> stack = new Stack<>();
        char[] carr = s.toCharArray();
        for (int i = 0; i < carr.length; i++) {
            char cur = carr[i];
            boolean flag = false;
            if (!stack.isEmpty()) {
                char peek = stack.peek();
                if (cur == ')' && peek == '(') {
                    flag = true;
                    stack.pop();
                } else if (cur == ']' && peek == '[') {
                    flag = true;
                    stack.pop();
                } else if (cur == '}' && peek == '{') {
                    flag = true;
                    stack.pop();
                }
            }
            if (!flag) {
                stack.push(cur);
            }
        }
        return stack.isEmpty();
    }
}

150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> st = new Stack<>();
        for(int i = 0; i < tokens.length; i++) {
            switch(tokens[i]) {
                case "+":
                    st.push(st.pop() + st.pop());
                    break;
                case "-":
                    st.push(-st.pop() + st.pop());
                    break;
                case "*":
                    st.push(st.pop() * st.pop());
                    break;
                case "/":
                    int n1 = st.pop(), n2 = st.pop();
                    st.push(n2 / n1);
                    break;
                default:
                    st.push(Integer.parseInt(tokens[i]));
            }
        }
        return st.pop();
    }
}

剑指 Offer

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

思路：
两个栈，一个负责出栈，一个负责入栈。appendTail时直接压入栈1。deleteHead时如果栈2不为空，则直接弹出栈2的栈顶返回，否则弹出栈1中元素，压入栈2，当栈2不为空时返回栈2栈顶。

class CQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        }else{
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.isEmpty() ? -1 : stack2.pop();
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

思路：
维护两个栈，一个栈存放所有元素，一个栈用来记录每次 push 后的最小值。push时默认压入stackTotal；如果 stackLittle 不为空且栈顶元素大于等于当前元素，则将当前元素压入 stackLittle 中，否则将栈顶元素压入 stackLittle 中，维持两个栈大小一致。pop 时两个栈直接 pop 即可。top 返回 stackTotal 的栈顶。 min 返回 stackLittle 的栈顶。

class MinStack {
    private Stack<Integer> stackTotal;
    private Stack<Integer> stackLittle;
    /** initialize your data structure here. */
    public MinStack() {
        stackTotal = new Stack<>();
        stackLittle = new Stack<>();
    }

    public void push(int x) {
        stackTotal.push(x);
        if (stackLittle.isEmpty()) {
            stackLittle.push(x);
        } else {
            if (x <= stackLittle.peek()) {
                stackLittle.push(x);
            } else {
                stackLittle.push(stackLittle.peek());
            }
        }
    }

    public void pop() {
        stackTotal.pop();
        stackLittle.pop();
    }

    public int top() {
        return stackTotal.peek();
    }

    public int min() {
        return stackLittle.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

剑指 Offer 31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

思路：
按顺序将 pushed 中的元素压入栈 temp 中，当 temp 的栈顶和 ind 指向的 poped 元素相等时，将 temp 栈顶弹出，ind 自增。1,2,3,4 此时弹出 4，temp 为 1,2,3，继续遍历 pushed，1,2,3,5，弹出 5,3,2,1，temp 为空，所以返回 true。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length == 0 || popped.length == 0) {
            return true;
        }
        Stack<Integer> temp = new Stack<>();
        int ind = 0;
        for (int i = 0; i < pushed.length; i++) {
            temp.push(pushed[i]);
            while (!temp.isEmpty() && temp.peek() == popped[ind]) {
                temp.pop();
                ind++;
            }
        }
        return temp.isEmpty();
    }
}

卡兰特数
3个不同元素依次进栈,有( 5 )种不同的出栈序列
序列的总数目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)。其中，n为节点的个数。
c(2n,n)/(n+1) = c(6,3)/4=654/(123)/4=5。