本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖

面試題31：棧的壓入彈出序列

題目要求：
輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，判斷第二個(gè)序列是否為該棧的彈出序序列。假設(shè)壓入棧的所有數(shù)字均不相等。例如，壓入序列為(1,2,3,4,5)，序列(4,5,3,2,1)是它的彈出序列，而(4,3,5,1,2)不是。

解題思路：
對(duì)于一個(gè)給定的壓入序列，由于彈出的時(shí)機(jī)不同，會(huì)出現(xiàn)多種彈出序列。如果是選擇題，依照后進(jìn)先出的原則，復(fù)現(xiàn)一下棧的壓入彈出過程就很容易判斷了。寫成程序同樣如此，主要步驟如下：

步驟1：棧壓入序列第一個(gè)元素，彈出序列指針指彈出序列的第一個(gè)；
步驟2：判斷棧頂元素是否等于彈出序列的第一個(gè)元素：
    步驟2.1：如果不是，壓入另一個(gè)元素，進(jìn)行結(jié)束判斷，未結(jié)束則繼續(xù)執(zhí)行步驟2；
    步驟2.2：如果是，棧彈出一個(gè)元素，彈出序列指針向后移動(dòng)一位，進(jìn)行結(jié)束判斷，未結(jié)束則繼續(xù)執(zhí)行步驟2；

結(jié)束條件：如果彈出序列指針還沒到結(jié)尾但已經(jīng)無元素可壓入，則被測(cè)序列不是彈出序列。
         如果彈出序列指針以判斷完最后一個(gè)元素，則被測(cè)序列是彈出序列。

當(dāng)然，進(jìn)行判斷前需要進(jìn)行一些檢查，比如傳入?yún)?shù)是否為null，壓入序列與彈出序列長(zhǎng)度是否一致。

package chapter4;
import java.util.Stack;
/**
 * Created by ryder on 2017/7/17.
 * 棧的壓入彈出序列
 */
public class P168_StackPushPopOrder {
    public static boolean isPopOrder(int[] pushSeq,int[] popSeq){
        if(pushSeq==null||popSeq==null||pushSeq.length!=popSeq.length)
            return false;
        Stack<Integer> stack = new Stack<>();
        int pushSeqIndex=0,popSeqIndex=0;
        while (popSeqIndex<popSeq.length){
            if(stack.isEmpty()||stack.peek()!=popSeq[popSeqIndex]) {
                if(pushSeqIndex<pushSeq.length)
                    stack.push(pushSeq[pushSeqIndex++]);
                else
                    return false;
            }
            else{
                stack.pop();
                popSeqIndex++;
            }
        }
        return true;
    }
    public static void main(String[] args){
        int[] push = {1,2,3,4,5};
        int[] pop1 = {4,5,3,2,1};
        int[] pop2 = {4,3,5,1,2};
        System.out.println(isPopOrder(push,pop1));
        System.out.println(isPopOrder(push,pop2));
    }
}

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

true
false