栈、队列

Stack先进后出，常用函数3P: peek push pop

Stack

Queue先进先出，常用函数POP: peek offer poll
注意，Stack是一个Class，而Queue在Java里是interface，一般用LinkedList实现。

Queue

1. 最小栈

设计含返回栈中最小数的函数的栈，要求时间复杂度为O(1)。
做法是使用一个记录最小值的栈，每层的元素对应原栈相同层截止最小的元素。

public class MinStack {
    
    Stack<Integer> stack; 
    Stack<Integer> min; 
    

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<Integer>();
        min = new Stack<Integer>();
    }
    
    public void push(int x) {
        if(stack.empty() || x < min.peek()){
            min.push(x);
        }else{
            min.push(min.peek());
        }
        stack.push(x);
        
    }
    
    public void pop() {
        stack.pop();
        min.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}

2. 两个栈实现一个队列

让一个栈实现队列的顺序，就是在每插入一个元素时，把元素插到栈底，即为队尾。这时候就需要用到一个辅助栈来记录原栈成员，实现原栈的修复。

如果一个栈的元素一个个跳出同时另一个栈不停把元素push进去，那么另一个栈的跳出顺序就会反过来，就会变成队列的顺序，而另一个栈再进行一个个跳出让原栈一个个push，原栈的顺序变回跟以前一样。

还有一个类似的思路是，push不变，原栈还是保持栈的顺序，只是跳出时跳栈底的元素。

public class MyQueue {
    
    Stack<Integer> queue;

    /** Initialize your data structure here. */
    public MyQueue() {
        queue = new Stack<Integer>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        Stack<Integer> temp = new Stack<Integer>();
        
        while(!queue.empty()){
            temp.push(queue.pop());
        }
        temp.push(x);
        while(!temp.empty()){
            queue.push(temp.pop());
        }
        
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        return queue.pop();
        
    }
    
    /** Get the front element. */
    public int peek() {
        return queue.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return queue.empty();
    }
}

3. 两个队列实现一个栈

public class MyStack {
    
    Queue<Integer> stack;

    /** Initialize your data structure here. */
    public MyStack() {
        stack = new LinkedList<Integer>();  
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        Queue<Integer> temp = new LinkedList<Integer>();
        
        while(stack.peek() != null){
            temp.offer(stack.poll());
        }
        stack.offer(x);
        while(temp.peek() != null) {
            stack.offer(temp.poll());
        }
        
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return stack.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return stack.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return stack.peek() == null;
    }
}

4. 出栈入栈合理性

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
这里就用一个栈来储存和模拟压入和弹出的过程。按照压入顺序依次压入元素进栈，如果发现栈顶元素刚好是当前弹出元素，说明此时发生一次弹出，栈弹出一个元素且弹出数组后移一位。整个过程结束后(遍历完pushA后)，如果栈为空且popA也遍历完，则说明合理；反之不合理。
（P.S.之前代码思路有误但牛客网上仍然通过，说明牛客网测试用例设计得不够全面。幸得朋友指出。）

 public boolean IsPopOrder(int [] pushA,int [] popA) {
     
        if(pushA == null || popA == null) return false;
        Stack<Integer> stack = new Stack<Integer>();
     
        int j = 0;
        for(int i = 0; i < pushA.length; i++){
            stack.push(pushA[i]);
            while(!stack.isEmpty() && stack.peek() == popA[j]){
                stack.pop();
                j++;
            }           
        }     
        return (stack.isEmpty() && popA.length == j);
    }