套路

• 暫無

注意點

• Stack : empty() ，ArrayDeque / LinkedList：isEmpty()
• poll（）、top（）、peek（）、min（）操作都需要排除棧為空的情況 !stack.empty()

目錄

• 包含min函數(shù)的棧
• 棧的壓入、彈出序列（實際過程模擬還需要練習）
• 用兩個棧實現(xiàn)隊列

包含min函數(shù)的棧

定義棧的數(shù)據結構，請在該類型中實現(xiàn)一個能夠得到棧最小元素的min函數(shù)。

Stack<Integer> stack = new Stack<>();
Stack<Integer> stackMin = new Stack<>();

public void push(int node) {
    stack.push(node);
    if (stackMin.empty()) {
        stackMin.push(node);
    } else if (node <= stackMin.peek()) {
        stackMin.push(node);
    }
}

public void pop() {
    if (stack.empty()) {
        throw new EmptyStackException("this stack is empty !");
    } else {
        if (stack.pop() == stackMin.peek()) {
            stackMin.pop();
        }
    }
}

public int top() {
    if (stack.empty()) {
        throw new EmptyStackException("this stack is empty !");
    } else {
        return stack.peek();
    }
}

public int min() {
    if (stackMin.empty()) {
        throw new EmptyStackException("this stack is empty !");
    } else {
        return stackMin.peek();
    }
}

棧的壓入、彈出序列

輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）

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

用兩個棧實現(xiàn)隊列

用兩個棧來實現(xiàn)一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為int類型。

• 解題思路：在將棧1中的元素放入棧2時，只要保證棧2此時為空，就可以保證正確性。

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

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

public int pop() {
    if (stack1.empty() && stack2.empty()) {
        return -1;
    }
    if (stack2.empty()) {
        while (!stack1.empty()) {
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}