題目描述

輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。

例如序列 1,2,3,4,5 是某棧的壓入順序，序列 4,5,3,2,1 是該壓棧序列對應的一個彈出序列，但 4,3,5,1,2 就不可能是該壓棧序列的彈出序列。

解題思路

使用一個棧來模擬壓入彈出操作。

代碼實現(xiàn)

public boolean IsPopOrder(int[] pushSequence, int[] popSequence) {
    int n = pushSequence.length;
    Stack<Integer> stack = new Stack<>();
    for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {
        stack.push(pushSequence[pushIndex]);
        while (popIndex < n && !stack.isEmpty() 
                && stack.peek() == popSequence[popIndex]) {
            stack.pop();
            popIndex++;
        }
    }
    return stack.isEmpty();
}