入栈出栈问题

声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
给定无重复元素的两个等长数组,分别表述入栈序列和出栈序列,
请问:这样的出栈序列是否可行
如:入栈序列为"ABCDEFG",出栈序列为"BAEDFGC",则可行
入栈序列"ABCD",出栈序列"BDAC",不可行
分析:
1.使用一个堆栈S来模拟压栈出栈的操作.记入栈序列为A,出栈序列为B
2.遍历B的每个元素b:
(1).若b等于栈顶元素s,恰好匹配,则检查B的下一个元素,栈顶元素s出栈;
若栈s为空,则认为b无法与栈内元素匹配,则调用(2)
(2).若b不等于栈顶元素s,则将A的当前元素入栈,目的是希望在A的剩余元素中找到b
Java版本实现：

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;
    }

测试代码:

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);
    }

输出结果：
true
false
代码可进一步优化，合并判断分支，如下：

public static boolean isPossible2(char[] in, char[] out){
        Stack<Character> stack = new Stack<>();
        int i=0;
        int j=0;
        while(i<out.length){//遍历out的每一个字符
            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;
    }

同样可以实现上述功能，代码看上去更简洁。