(24) 不可能的出棧順序

一、問題描述

給定兩個數組，一個進棧順序，一個出棧順序。判定出棧數組的出棧順序是不是有可能的。

二、Code

package algorithm;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Created by adrian.wu on 2019/5/30.
 */
public class StackPopOrderJudge {
    /*
    思路：
    1、整體思路用一個輔助棧還原入棧元素的順序，并比較兩者是否一致
    2、如果第一個出棧元素并非最后一個入棧元素，則這個出戰元素之前的元素不可能先于它出棧，因此把這個元素即之前的元素都壓入棧
    3、上述步驟之后，如果出棧元素并非入棧棧頂元素，則其是先pop出去了，因此直接壓人輔助棧
    4、重復上述步驟，并比較輔助棧和壓入棧的元素，遇到相同則pop
    5、觀察最后入棧元素和輔助棧是否都為空，為空則正確，不為空則False
     */

    public static boolean isPopOrder(int[] in, int[] out) {
        int n = out.length;
        int nextPop = 0, nextPush = 0;
        Deque<Integer> deque = new ArrayDeque<>();


        while (nextPop != n) {
            while (deque.isEmpty() || deque.peek() != out[nextPop]) {
                if (nextPush == n) break;
                deque.push(in[nextPush++]);
            }

            if (!deque.isEmpty() && deque.peek() != out[nextPop++]) break;
            deque.pop();
        }
        return nextPop == n && deque.isEmpty();
    }
}

?