5_栈.md

栈

1、用两个栈实现队列（19）

用两个栈实现队列

Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
    stack1.push(node);
}

public int pop() {
    if(stack2.isEmpty()){
        while (!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}

*2、包含 min 函数的栈（35）

包含 min 函数的栈

private Stack<Integer> stack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();

public void push(int node) {
    stack.push(node);
    if(minStack.isEmpty() || node<minStack.peek()){ 
        //注意：minStack 一开始栈为空,则直接如 minStack 栈
        minStack.push(node);
    }
}

public void pop() {
    if(stack.peek()==minStack.peek()){
        minStack.pop();
    }
    stack.pop();
}

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

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

*3、栈的压入、弹出序列（36）

栈的压入、弹出序列

public boolean IsPopOrder(int [] pushA,int [] popA) {
    int n = pushA.length;

    //使用一个栈来模拟弹出、压出操作。
    Stack<Integer> stack=new Stack<>();

    for(int pushIndex=0,popIndex=0;pushIndex<n;pushIndex++){
        stack.push(pushA[pushIndex]);
        while(popIndex<n && stack.peek()==popA[popIndex]){
            stack.pop();
            popIndex++;
        }
    }
    return stack.isEmpty();
}

4、有效的括号

有效的括号

public boolean isValid(String s) {
    if(s.length()==0){
        return true;
    }
    Stack<Character> stack=new Stack<>();
    for(int i=0;i<s.length();i++){
        char c=s.charAt(i);
        if(c=='(' || c=='[' || c=='{'){
            stack.push(c);
        }else{ // c 可能的取值是 ')' ']' ,'}'
            if(stack.isEmpty()){ //没有左括号进栈式不对的
                return false;
            }
            char validChar=' ';
            char topChar=stack.peek();
            if(topChar=='('){
                validChar=')';
            }else if(topChar=='['){
                validChar=']';
            }else if(topChar=='{'){
                validChar='}';
            }
            if(c==validChar){
                stack.pop();
            }else{
                return false;
            }
        }
    }
    return stack.isEmpty();
}