我們今天繼續(xù)來(lái)看看周五留下的習(xí)題：

面試題：輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷二個(gè)序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如：壓入序列為{1，2，3，4，5}，那{4，5，3，2，1} 就是該棧的彈出順序，而{4，3，5，1，2} 明顯就不符合要求；

這道題還是比較容易想到思路，很直觀的想法就是建立一個(gè)輔助棧，把輸入的第一個(gè)序列中的數(shù)字依次壓入該輔助棧，并按照第二個(gè)序列的順序依次從該棧中彈出數(shù)字。

提前想好測(cè)試用例

一樣是老方法，我們先準(zhǔn)備測(cè)試用例：

• 傳入兩個(gè) null，或者 1 個(gè) null，或者空數(shù)組，此時(shí)應(yīng)該不符合要求；
• 傳入兩個(gè)不相等的數(shù)組，應(yīng)該直接不符合要求；
• 分別傳入題干的示意值，他們應(yīng)該分別滿足和不滿足要求；
• 傳入單個(gè)數(shù)字，選擇一組滿足要求的和一組不滿足要求的；

思考程序邏輯

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

然而有的小伙伴還是容易被繞暈，這時(shí)候不妨我們可以直接作一個(gè)表格來(lái)模擬他們的壓棧出棧過(guò)程，數(shù)據(jù)就采用我們題設(shè)中的數(shù)據(jù)吧~

用作圖和模擬數(shù)據(jù)更容易給面試官一個(gè)你是個(gè)喜歡思考的好同事喲~

首先看看我們正確的數(shù)據(jù)。

實(shí)際上我們?cè)诓莞寮埳喜⒉恍枰鲞@么標(biāo)準(zhǔn)的表格，只要能表現(xiàn)意思即可。

我們仔細(xì)觀察可以得知，我們判斷壓入還是彈出甚至是得出確定結(jié)論的標(biāo)準(zhǔn)是，先看當(dāng)前棧頂元素和彈出的數(shù)字是否相等，如果相等則直接彈出；如果不相等則直接看看壓入數(shù)組中還有沒(méi)有元素，如果有則直接壓入到輔助棧；如果已經(jīng)沒(méi)有數(shù)據(jù)則代表第二個(gè)序列不是第一個(gè)序列的彈出棧。

編寫程序代碼

實(shí)際上我們心中已經(jīng)大概知道怎么寫了。

private static boolean isPushStack(int[] push, int[] pop) {
    if (push == null || pop == null || pop.length != push.length)
        return false;
    Stack<Integer> stack = new Stack<>();
    int j = 0;
    for (int i = 0; i < pop.length; i++) {
        // 第一步判斷棧頂元素是否和 pop[i] 相等
        if (!stack.isEmpty() && pop[i] == stack.peek()) {
            // 如果相等則直接 pop()
            stack.pop();
        } else {
            // 棧頂和 pop[i] 不相等，則判斷 push 數(shù)組還有沒(méi)有數(shù)據(jù)
            // 如果 push 數(shù)組沒(méi)數(shù)據(jù)了，棧頂元素又不等于 pop[i]，則說(shuō)明不符合要求
            if (j == push.length)
                return false;
            while (j < push.length) {
                // 如果還有數(shù)據(jù)，則直接 push
                stack.push(push[j]);
                ++j;
                // push 后繼續(xù)判斷棧頂元素是否和 pop[i] 相等；
                if (pop[i] == stack.peek()) {
                    // 如果相等則彈出棧，并且推出內(nèi)層循環(huán)
                    stack.pop();
                    break;
                }
            }
        }
    }
    return true;
}

驗(yàn)證測(cè)試用例

寫畢代碼后，我們得用自己事先準(zhǔn)備的測(cè)試用例測(cè)試一下。

• 測(cè)試 1 和測(cè)試 2 我們已經(jīng)考慮到了，這樣的情況直接在功能之前就判斷，不符合條件的直接返回 false，測(cè)試通過(guò)。

• 傳入{1，2，3，4，5} 和 {4，5，3，2，1}：

  1. 進(jìn)入循環(huán)，i = 0，pop[i] = 4，直接進(jìn)入 else 語(yǔ)句，開(kāi)始 push 數(shù)據(jù)，一直 push 到 j = 3。
  2. 此時(shí)棧內(nèi)元素為 {1，2，3，4}，push 里面還剩下 {5}。因?yàn)?pop[0] 等于棧頂，所以進(jìn)入 if 語(yǔ)句，彈出 4，退出 while 循環(huán)；
  3. i = 1，棧內(nèi)元素為{1，2，3}，棧頂元素不等于 pop[1] = 5，進(jìn)入 else 語(yǔ)句。push 數(shù)組還有數(shù)據(jù)，直接 push，結(jié)束后 j = 5，棧內(nèi)元素為 {1，2，3，5}，棧頂剛好等于 pop[1]，故彈出數(shù)字 5，退出 while 循環(huán)；
  4. i = 2，棧內(nèi)元素為{1，2，3}，棧頂元素剛剛等于 pop[2] ，彈出數(shù)字 3；
  5. i = 3，棧內(nèi)元素為 {1，2}，棧頂元素剛等于 pop[3]，彈出數(shù)字 2；
  6. i = 4，棧內(nèi)元素為 {1}，棧頂元素剛剛等于 pop[4]，彈出數(shù)字 1；
  7. for 循環(huán)能直接執(zhí)行結(jié)束，返回 ture，測(cè)試通過(guò)。

• 傳入 {1，2，3，4，5} 和 {4，3，5，1，2}：

  1. 進(jìn)入循環(huán)，i = 0，pop[i] = 4，由于同上，所以直接進(jìn)入到上面的步驟 3；
  2. 此時(shí) i = 1，棧內(nèi)元素為 {1，2，3}，因?yàn)闂ｍ斣氐扔?pop[1]，彈出數(shù)字 3；
  3. i = 2，棧內(nèi)元素為 {1，2}，棧頂元素不等于 pop[2]，進(jìn)入 else 語(yǔ)句，此時(shí) push 數(shù)組還有元素 {5}，所以進(jìn)入 while 循環(huán)。push 后棧內(nèi)元素為 {1，2，5}，棧頂元素等于 pop[2]，所以彈出數(shù)字 5，退出 while 循環(huán)；
  4. i = 3，棧內(nèi)元素為{1，2}，pop[3] = 1，和棧頂元素不相等，所以進(jìn)入 else 語(yǔ)句，由于 push 里面已經(jīng)沒(méi)有了元素，所以直接返回 false，測(cè)試通過(guò)。

• 傳入 {1} 和 {2}：

  進(jìn)入循環(huán)，i = 0，pop[i] = 2，進(jìn)入 else 語(yǔ)句，不相等，直接進(jìn)入 while 循環(huán)，push 后棧內(nèi)元素為 {1}，棧頂元素和 pop[i] 不相等，此時(shí) j = 1，不符合 while 循環(huán)條件。循環(huán)結(jié)束，外循環(huán)也結(jié)束，返回 true。測(cè)試不通過(guò)。

修復(fù)程序邏輯

所以我們現(xiàn)在應(yīng)該著重處理一下單個(gè)數(shù)字的情況，分析后明顯可以得到，我們要判斷這種情況只需要再判斷結(jié)束 for 循環(huán)后棧內(nèi)是否還有元素和 push 里面還是否有元素即可。

所以在最后增加一個(gè)條件判斷即可。

public class Test16 {


    private static boolean isPushStack(int[] push, int[] pop) {
        if (push == null || pop == null || pop.length != push.length)
            return false;
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pop.length; i++) {
            // 第一步判斷棧頂元素是否和 pop[i] 相等
            if (!stack.isEmpty() && pop[i] == stack.peek()) {
                // 如果相等則直接 pop()
                stack.pop();
            } else {
                // 棧頂和 pop[i] 不相等，則判斷 push 數(shù)組還有沒(méi)有數(shù)據(jù)
                // 如果 push 數(shù)組沒(méi)數(shù)據(jù)了，棧頂元素又不等于 pop[i]，則說(shuō)明不符合要求
                if (j == push.length)
                    return false;
                while (j < push.length) {
                    // 如果還有數(shù)據(jù)，則直接 push
                    stack.push(push[j]);
                    ++j;
                    // push 后繼續(xù)判斷棧頂元素是否和 pop[i] 相等；
                    if (pop[i] == stack.peek()) {
                        // 如果相等則彈出棧，并且推出內(nèi)層循環(huán)
                        stack.pop();
                        break;
                    }
                }
            }
        }
        // 增加判斷
        if (!stack.isEmpty() && j == push.length)
            return false;
        return true;
    }

    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(isPushStack(push, pop1));
        System.out.println(isPushStack(push, pop2));
        System.out.println(isPushStack(push, pop3));
        System.out.println(isPushStack(push, pop4));
        int[] push1 = {1};
        int[] pop5 = {2};
        System.out.println(isPushStack(push1, pop5));
        int[] push2 = {1};
        int[] pop6 = {1};
        System.out.println(isPushStack(push2, pop6));
    }
}

上面在代碼邏輯上并沒(méi)有做多少操作，所以我們只需要再傳入 {1} 和 {1} 測(cè)試就可以了。

直接進(jìn)入到 while 循環(huán)，push 后棧內(nèi)元素為 {1}，因?yàn)闂ｍ斣貏倓偟扔?pop[0]，所以推出數(shù)字 1。此后棧內(nèi)無(wú)元素，所以直接返回 true。

總結(jié)

我親愛(ài)的小伙伴想必也一定在上面的分析中收獲到東西了吧，這也是南塵給大家的箴言。

• 在思路不是很清晰的時(shí)候畫(huà)表或者畫(huà)圖來(lái)處理；
• 在驗(yàn)證測(cè)試用例的時(shí)候，一定從簡(jiǎn)單的開(kāi)始，比如上面，我們其實(shí)更加建議先驗(yàn)證單個(gè)數(shù)字的情況。

拓展延伸

本次學(xué)習(xí)的方法將非常有效，不信大家可以試試下明天的拓展題。

面試題：從上到下打印二叉樹(shù)的每個(gè)結(jié)點(diǎn)，同一層按照從左到右的順序打印。例如數(shù)的結(jié)構(gòu)如下：

? 1
2 3
4 5 6 7

則依次打印 1、2、3、4、5、6、7