棧的壓入、彈出序列

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

解題思路：

解決這個(gè)問(wèn)題很直觀的想法就是建立一個(gè)輔助棧，把輸入的第一個(gè)序列中的數(shù)字依次壓入該輔助棧，并按照第二個(gè)序列的順序依次從該棧中彈出數(shù)字。

判斷一個(gè)序列是不是棧的彈出序列的規(guī)律：如果下一個(gè)彈出的數(shù)字剛好是棧頂數(shù)字，那么直接彈出。如果下一個(gè)彈出的數(shù)字不在棧頂，我們把壓棧序列中還沒(méi)有入棧的數(shù)字壓入輔助棧，直到把下一個(gè)需要彈出的數(shù)字壓入棧頂為止。如果所有的數(shù)字都?jí)喝霔Ａ巳匀粵](méi)有找到下一個(gè)彈出的數(shù)字，那么該序列不可能是一個(gè)彈出序列。

代碼實(shí)現(xiàn)：

public class Test22 {
    /**
     * 輸入兩個(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就不可能是該壓棋序列的彈出序列。
     * 【與書本的的方法不同】
     *
     * @param push 入棧序列
     * @param pop  出棧序列
     * @return true：出棧序列是入棧序列的一個(gè)彈出順序
     */
    public static boolean isPopOrder(int[] push, int[] pop) {
        // 輸入校驗(yàn)，參數(shù)不能為空，并且兩個(gè)數(shù)組中必須有數(shù)字，并且兩個(gè)數(shù)組中的數(shù)字個(gè)數(shù)相同
        // 否則返回false
        if (push == null || pop == null || pop.length == 0 || push.length == 0 || push.length != pop.length) {
            return false;
        }
        // 經(jīng)過(guò)上面的參數(shù)校驗(yàn)，兩個(gè)數(shù)組中一定有數(shù)據(jù)，且數(shù)據(jù)數(shù)目相等
        // 用于存放入棧時(shí)的數(shù)據(jù)
        Stack<Integer> stack = new Stack<>();
        // 用于記錄入棧數(shù)組元素的處理位置
        int pushIndex = 0;
        // 用于記錄出棧數(shù)組元素的處理位置
        int popIndex = 0;
        // 如果還有出棧元素要處理
        while (popIndex < pop.length) {
            // 入棧元素還未全部入棧的條件下，如果棧為空，或者棧頂?shù)脑夭慌c當(dāng)前處理的相等，則一直進(jìn)行棧操作，
            // 直到入棧元素全部入棧或者找到了一個(gè)與當(dāng)出棧元素相等的元素
            while (pushIndex < push.length && (stack.isEmpty() || stack.peek() != pop[popIndex])) {
                // 入棧數(shù)組中的元素入棧
                stack.push(push[pushIndex]);
                // 指向下一個(gè)要處理的入棧元素
                pushIndex++;
            }
            // 如果在上一步的入棧過(guò)程中找到了與出棧的元素相等的元素
            if (stack.peek() == pop[popIndex]) {
                // 將元素出棧
                stack.pop();
                // 處理下一個(gè)出棧元素
                popIndex++;
            }
            // 如果沒(méi)有找到與出棧元素相等的元素，說(shuō)明這個(gè)出棧順序是不合法的
            // 就返回false
            else {
                return false;
            }
        }
        // 下面的語(yǔ)句總是成立的
        // return stack.isEmpty();
        // 為什么可以直接返回true：對(duì)上面的外層while進(jìn)行分析可知道，對(duì)每一個(gè)入棧的元素，
        // 在stack棧中，通過(guò)一些入棧操作，總可以在棧頂上找到與入棧元素值相同的元素，
        // 這就說(shuō)明了這個(gè)出棧的順序是入棧順序的一個(gè)彈出隊(duì)列，這也可以解釋為什么stack.isEmpty()
        // 總是返回true，所有的入棧元素都可以進(jìn)棧，并且可以被匹配到，之后就彈出，最后棧中就無(wú)元素。
        return true;
    }
    /**
     * 輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷二個(gè)序列是否為該棧的彈出順序。
     * 【按書本上的思路進(jìn)行求解，兩者相差不大】
     *
     * @param push 入棧序列
     * @param pop  出棧序列
     * @return true：出棧序列是入棧序列的一個(gè)彈出順序
     */
    public static boolean isPopOrder2(int[] push, int[] pop) {
        // 用于記錄判斷出棧順序是不是入棧順的一個(gè)出棧序列，默認(rèn)false
        boolean isPossible = false;
        // 當(dāng)入棧和出棧數(shù)組者都不為空，并且都有數(shù)據(jù)，并且數(shù)據(jù)個(gè)數(shù)都相等
        if (push != null && pop != null && push.length > 0 && push.length == pop.length) {
            // 用于存放入棧時(shí)的數(shù)據(jù)
            Stack<Integer> stack = new Stack<>();
            // 記錄下一個(gè)要處理的入棧元素的位置
            int nextPush = 0;
            // 記錄下一個(gè)要處理的出棧元素的位置
            int nextPop = 0;
            // 如果出棧元素沒(méi)有處理完就繼續(xù)進(jìn)行處理
            while (nextPop < pop.length) {
                // 如果棧為空或者棧頂?shù)脑嘏c當(dāng)前處理的出棧元素不相同，一直進(jìn)行操作
                while (stack.isEmpty() || stack.peek() != pop[nextPop]) {
                    // 如果入棧的元素已經(jīng)全部入棧了，就退出內(nèi)層循環(huán)
                    if (nextPush >= push.length) {
                        break;
                    }
                    // 執(zhí)行到此處說(shuō)明還有入棧元素可以入棧
                    // 即將元素入棧
                    stack.push(push[nextPush]);
                    // 指向下一個(gè)要處理的入棧元素的位置
                    nextPush++;
                }
                // 執(zhí)行到此處有兩種情況：
                // 第一種：在棧頂上找到了一個(gè)與入棧元素相等的元素
                // 第二種：在棧頂上沒(méi)有找到一個(gè)與入棧元素相等的元素，而且輸入棧的元素已經(jīng)全部入棧了
                // 對(duì)于第二種情況就說(shuō)彈出棧的順序是不符合要求的，退出外層循環(huán)
                if (stack.peek() != pop[nextPop]) {
                    break;
                }
                // 對(duì)應(yīng)到第一種情況：需要要棧的棧頂元素彈出
                stack.pop();
                // 指向下一個(gè)要處理的出棧元素的位置
                nextPop++;
            }
            // 執(zhí)行到此處有兩種情況
            // 第一種：外層while循環(huán)的在第一種情況下退出，
            // 第二種：所有的出棧元素都被正確匹配
            // 對(duì)于出現(xiàn)的第一種情況其stack.isEmpty()必不為空，原因?yàn)榉治鋈缦拢?            // 所有的入棧元素一定會(huì)入棧，但是只有匹配的情況下才會(huì)出棧，
            // 匹配的次數(shù)最多與入棧元素個(gè)數(shù)元素相同（兩個(gè)數(shù)組的長(zhǎng)度相等），如果有不匹配的元素，
            // 必然會(huì)使出棧的次數(shù)比入棧的次數(shù)少，這樣棧中至少會(huì)有一個(gè)元素
            // 對(duì)于第二種情況其stack.isEmpty()一定為空
            // 所以書本上的nextPop == pop.length（pNextPop-pPop==nLength）是多余的
            if (stack.isEmpty()) {
                isPossible = true;
            }
        }
        return isPossible;
    }
    public static void main(String[] args) {
        int[] push = {1, 2, 3, 4, 5};
        int[] pop1 = {4, 5, 3, 2, 1};
        int[] pop2 = {3, 5, 4, 2, 1};
        int[] pop3 = {4, 3, 5, 1, 2};
        int[] pop4 = {3, 5, 4, 1, 2};
        System.out.println("true: " + isPopOrder(push, pop1));
        System.out.println("true: " + isPopOrder(push, pop2));
        System.out.println("false: " + isPopOrder(push, pop3));
        System.out.println("false: " + isPopOrder(push, pop4));
        int[] push5 = {1};
        int[] pop5 = {2};
        System.out.println("false: " + isPopOrder(push5, pop5));
        int[] push6 = {1};
        int[] pop6 = {1};
        System.out.println("true: " + isPopOrder(push6, pop6));
        System.out.println("false: " + isPopOrder(null, null));
        // 測(cè)試方法2
        System.out.println();
        System.out.println("true: " + isPopOrder2(push, pop1));
        System.out.println("true: " + isPopOrder2(push, pop2));
        System.out.println("false: " + isPopOrder2(push, pop3));
        System.out.println("false: " + isPopOrder2(push, pop4));
        System.out.println("false: " + isPopOrder2(push5, pop5));
        System.out.println("true: " + isPopOrder2(push6, pop6));
        System.out.println("false: " + isPopOrder2(null, null));
    }
}

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

http://wiki.jikexueyuan.com/project/for-offer/images/29.png" alt="" />