Skip to content

Latest commit

 

History

History
82 lines (60 loc) · 1.98 KB

6_栈.md

File metadata and controls

82 lines (60 loc) · 1.98 KB

栈

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();
}