剑指offer——栈的压入弹出序列

119 阅读 0 评论 79 点赞

我是靠谱客的博主粗暴金毛，这篇文章主要介绍剑指offer——栈的压入弹出序列，现在分享给大家，希望可以做个参考。

题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

采用实践尝试的方式
基本思路点：

当pushA[i] == popA[j] 则：直接两个指针向后移动。然后循环判断栈顶元素与popA[j]相同。如果相同则弹出栈顶，且 j++。
当pushA[i] != popA[j] 则：pushA[i] 入栈，i++。

判断结果

当最后一个pushA也入栈，说明pushA的最后一个≠popA 宣布死亡。
当popA指针走到最后说明成功.

复制代码

package com.JZOffer;

import java.util.Stack;

public class 栈的压入弹出序列 {

public static boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        //当pop中序列完毕为完成，所以这里循环定为popA的length
        while (j < popA.length) {
            //当pushA没到头，
            if (i != pushA.length) {
                //如果当前指针所指项相同，相当于pushA中可以入栈-出栈， 此时两指针均向后移动
                if (pushA[i] == popA[j]) {
                    i++;
                    j++;
                    // 当弹出一个后，直接循环将栈内元素与popA中相比，只有此时才可能连续弹出！
                    //  注意peek前判空！
                    while (!stack.isEmpty() && stack.peek().equals(popA[j])) {
                        stack.pop();
                        j++;
                    }
                } else {
                //当不同，把pushA中入栈，（进入下一个循环继续比较）
                    stack.push(pushA[i]);
                    i++;
                }
            } else {
                //当最后一个pushA也入栈，说明pushA的最后一个≠popA 宣布死亡
                return false;
            }
        }
        return true;
    }

public static void main(String[] args) {
        int[] push = {1, 2, 3};
        int[] pop = {3, 1, 2};
        System.out.println(栈的压入弹出序列.IsPopOrder(push, pop));
    }
}

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
36
37
38
39
40
41
42
43
44
package com.JZOffer;

import java.util.Stack;

public class 栈的压入弹出序列 {

    public static boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        //当pop中序列完毕为完成，所以这里循环定为popA的length
        while (j < popA.length) {
            //当pushA没到头，
            if (i != pushA.length) {
                //如果当前指针所指项相同，相当于pushA中可以入栈-出栈， 此时两指针均向后移动
                if (pushA[i] == popA[j]) {
                    i++;
                    j++;
                    // 当弹出一个后，直接循环将栈内元素与popA中相比，只有此时才可能连续弹出！
                    //  注意peek前判空！
                    while (!stack.isEmpty() && stack.peek().equals(popA[j])) {
                        stack.pop();
                        j++;
                    }
                } else {
                //当不同，把pushA中入栈，（进入下一个循环继续比较）
                    stack.push(pushA[i]);
                    i++;
                }
            } else {
                //当最后一个pushA也入栈，说明pushA的最后一个≠popA 宣布死亡
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] push = {1, 2, 3};
        int[] pop = {3, 1, 2};
        System.out.println(栈的压入弹出序列.IsPopOrder(push, pop));
    }
}