題目描述：

輸入兩個(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)度是相等的。

分析：

思路

【思路】借用一個(gè)輔助的棧，遍歷壓棧順序，先將第一個(gè)放入棧中，這里是1，然后判斷棧頂元素是不是出棧順序的第一個(gè)元素，這里是4，很顯然1≠4，所以我們繼續(xù)壓棧，直到相等以后開始出棧，出棧一個(gè)元素，則將出棧順序向后移動(dòng)一位，直到不相等，這樣循環(huán)等壓棧順序遍歷完成，如果輔助棧還不為空，說明彈出序列不是該棧的彈出順序。

舉例：
入棧1,2,3,4,5
出棧4,5,3,2,1
首先1入輔助棧，此時(shí)棧頂1≠4，繼續(xù)入棧2
此時(shí)棧頂2≠4，繼續(xù)入棧3
此時(shí)棧頂3≠4，繼續(xù)入棧4
此時(shí)棧4＝4，出棧4，彈出序列向后一位，此時(shí)為5，,輔助棧里面是1,2,3
此時(shí)棧頂3≠5，繼續(xù)入棧5
此時(shí)棧頂5=5，出棧5,彈出序列向后一位，此時(shí)為3，,輔助棧里面是1,2,3
….
依次執(zhí)行，最后輔助棧為空。如果不為空說明彈出序列不是該棧的彈出順序。

代碼：

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      Stack<Integer> stack = new Stack<>();
        int k =0;
        for(int i =0;i<pushA.length;i++){
            int a = pushA[i];
            stack.push(a);
            for(int j=k;j<popA.length;j++){
                if(stack.peek()==popA[j]){
                    stack.pop();
                    continue;
                }else{
                    k=j;
                    break;
                }
            }
        }
        boolean result = stack.isEmpty()?true:false;
        return result;
    }
}

運(yùn)行結(jié)果

代碼優(yōu)化：

代碼可以寫的更加精簡(jiǎn)：

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

小結(jié)：

此題的重點(diǎn)在于思路，用一個(gè)棧來模擬壓入和彈出操作。按照入棧順序依次入棧，當(dāng)棧頂?shù)扔诔鰲Ｐ蛄械牡谝粋€(gè)元素時(shí)，開始出棧，依次往后判斷，當(dāng)棧頂不等于出棧序列的相應(yīng)元素時(shí)，停止出棧繼續(xù)入棧，入棧后判斷棧頂和出棧序列相應(yīng)元素是否相等，依次進(jìn)行下去，當(dāng)運(yùn)行結(jié)束時(shí)候，棧不為空，則出棧序列為非法的出棧序列。