Stack先進后出，常用函數3P: peek push pop

Stack

Queue先進先出，常用函數POP: peek offer poll
注意，Stack是一個Class，而Queue在Java里是interface，一般用LinkedList實現(xiàn)。

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. 兩個棧實現(xiàn)一個隊列

讓一個棧實現(xiàn)隊列的順序，就是在每插入一個元素時，把元素插到棧底，即為隊尾。這時候就需要用到一個輔助棧來記錄原棧成員，實現(xiàn)原棧的修復。

如果一個棧的元素一個個跳出同時另一個棧不停把元素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. 兩個隊列實現(xiàn)一個棧

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. 出棧入棧合理性

輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。
這里就用一個棧來儲存和模擬壓入和彈出的過程。按照壓入順序依次壓入元素進棧，如果發(fā)現(xiàn)棧頂元素剛好是當前彈出元素，說明此時發(fā)生一次彈出，棧彈出一個元素且彈出數組后移一位。整個過程結束后(遍歷完pushA后)，如果棧為空且popA也遍歷完，則說明合理；反之不合理。
（P.S.之前代碼思路有誤但?？途W上仍然通過，說明牛客網測試用例設計得不夠全面。幸得朋友指出。）

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