聲明： 本總結(jié)僅為個(gè)人學(xué)習(xí)總結(jié)，以防止遺忘而作，不得轉(zhuǎn)載和商用。
給定無(wú)重復(fù)元素的兩個(gè)等長(zhǎng)數(shù)組,分別表述入棧序列和出棧序列,
請(qǐng)問:這樣的出棧序列是否可行
如:入棧序列為"ABCDEFG",出棧序列為"BAEDFGC",則可行
入棧序列"ABCD",出棧序列"BDAC",不可行
分析:
1.使用一個(gè)堆棧S來(lái)模擬壓棧出棧的操作.記入棧序列為A,出棧序列為B
2.遍歷B的每個(gè)元素b:
(1).若b等于棧頂元素s,恰好匹配,則檢查B的下一個(gè)元素,棧頂元素s出棧;
若棧s為空,則認(rèn)為b無(wú)法與棧內(nèi)元素匹配,則調(diào)用(2)
(2).若b不等于棧頂元素s,則將A的當(dāng)前元素入棧,目的是希望在A的剩余元素中找到b
Java版本實(shí)現(xiàn)：

public static boolean isPossible(char[] in, char[] out){
        Stack<Character> stack = new Stack<>();
        int i=0;
        int j=0;
        while(i<out.length){
            if (!stack.isEmpty()) {
                if (stack.peek() == out[i]) {
                    stack.pop();
                    i++;
                }else {
                    if (j > in.length-1) {//如果in遍歷完,則返回false
                        return false;
                    }
                    stack.push(in[j]);
                    j++;
                }
            }else {
                if (j > in.length-1) {
                    return false;
                }
                stack.push(in[j]);
                j++;
            }
        }
        return true;
    }

測(cè)試代碼:

public static void main(String[] args) {
        String in = "ABCDEFG";
        String out = "BAEDFGC";
        boolean b = isPossible(in.toCharArray(), out.toCharArray());
        System.out.println(b);
        in = "ABCD";
        out = "BDAC";
        b = isPossible(in.toCharArray(), out.toCharArray());
        System.out.println(b);
    }

輸出結(jié)果：
true
false
代碼可進(jìn)一步優(yōu)化，合并判斷分支，如下：

public static boolean isPossible2(char[] in, char[] out){
        Stack<Character> stack = new Stack<>();
        int i=0;
        int j=0;
        while(i<out.length){//遍歷out的每一個(gè)字符
            if (!stack.isEmpty() && stack.peek() == out[i]) {
                stack.pop();
                i++;
            }else {
                if (j > in.length-1) {//如果in遍歷完,則返回false
                    return false;
                }
                stack.push(in[j]);
                j++;
            }
        }
        return true;
    }

同樣可以實(shí)現(xiàn)上述功能，代碼看上去更簡(jiǎn)潔。