判断一个序列是否是另外一个序列的出栈序列（java实现）

87 阅读 0 评论 58 点赞

我是靠谱客的博主过时眼睛，这篇文章主要介绍判断一个序列是否是另外一个序列的出栈序列（java实现），现在分享给大家，希望可以做个参考。

判断一个序列是否是另外一个序列的出栈序列

在各种刷题网站上刷题时，如果刷的是单选题的话，常常会遇到这样一个问题：

如果进栈序列为1，2，3，4，则可能的出栈序列是()
注：一个元素进栈后可以马上出栈，不用等全部进栈
正确答案: B C
A.3，1，4，2
B.2，4，3，1
C.2，3，4，1
D.任意顺序都有可能
如果单纯的做选择题的话，是挺简单的，一个选项一个选项的对比，观察是否能够通过进栈序列进栈得到
但是如果用代码实现呢？个人感觉，第一次想这个问题的时候是比较头疼的，但是在思索一番之后，还是敲出来了，话不多说，直接上代码：

复制代码

/**
     * 判断一个序列是另外一个序列的出栈序列
     * @param src 源序列
     * @param out 判断的序列
     * @return
     */
    private static boolean isOut(int[] src,int[] out){
        //如果两个序列的长度都不相等，肯定不是出栈序列
        if(src.length != out.length){
            return false;
        }
        int i = 0;//src的标记位
        int j = 0;//out的标记位
        Stack<Integer> stack = new Stack<>();
        while (i < src.length && j < out.length){
            //一直入栈，直到要入栈的值是判断序列当前要判断的值
            for(; i <src.length && src[i] != out[j]; i++){
                stack.push(src[i]);
            }
            //也可能判断序列中没有入栈序列的值
            if(i == src.length){
                return false;
            }
            //找到入栈序列中与判断序列当前要判断值所对应的值
            i++;
            j++;//当做已经出栈了
            //如果栈里面的值与判断序列的下一个值相等，则一直出栈，直到栈为空或者不相等为止
            //然后判断位就会改变，入栈序列继续入栈，执行上述步骤
            for(;j < out.length && !stack.empty() && stack.peek() == out[j]  ;j++){
                stack.pop();
            }
        }
        return true;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 /**
     * 判断一个序列是另外一个序列的出栈序列
     * @param src 源序列
     * @param out 判断的序列
     * @return
     */
    private static boolean isOut(int[] src,int[] out){
        //如果两个序列的长度都不相等，肯定不是出栈序列
        if(src.length != out.length){
            return false;
        }
        int i = 0;//src的标记位
        int j = 0;//out的标记位
        Stack<Integer> stack = new Stack<>();
        while (i < src.length && j < out.length){
            //一直入栈，直到要入栈的值是判断序列当前要判断的值
            for(; i <src.length && src[i] != out[j]; i++){
                stack.push(src[i]);
            }
            //也可能判断序列中没有入栈序列的值
            if(i == src.length){
                return false;
            }
            //找到入栈序列中与判断序列当前要判断值所对应的值
            i++;
            j++;//当做已经出栈了
            //如果栈里面的值与判断序列的下一个值相等，则一直出栈，直到栈为空或者不相等为止
            //然后判断位就会改变，入栈序列继续入栈，执行上述步骤
            for(;j < out.length && !stack.empty() && stack.peek() == out[j]  ;j++){
                stack.pop();
            }
        }
        return true;
    }