套路

• 暫無(wú)

注意點(diǎn)

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

目錄

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

包含min函數(shù)的棧

定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃?lèi)型中實(shí)現(xiàn)一個(gè)能夠得到棧最小元素的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();
    }
}

棧的壓入、彈出序列

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

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

用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類(lèi)型。

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

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