栈的压入、弹出序列

问题陈述

给定一个入栈序列，可能存在多种出栈序列。然后我们给定一个出栈序列，判断它是否是正确的出栈序列。

思路分析

  • 按入栈序列逐个入栈并判断当前栈顶元素是否和出栈序列元素相等，若相等则出栈该元素，同时出栈序列指向下一个元素。
  • 继续入栈，继续判断。若为合理的出栈序列，最后栈必空。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class StackPop_sequence {
    public boolean is_StackPop_sequence(int[] in,int[] out){
        Stack<Integer> stack=new Stack<>();
        int j=0,n=out.length;
        for(int i=0;i<in.length;i++){
            stack.push(in[i]);
            while (!stack.isEmpty()&&j<n&&stack.peek()==out[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
    public static void main(String[] args){
        int[] in={1,2,3,4,5};
        int[] out={5,4,3,2,1};
        StackPop_sequence stackPop_sequence=new StackPop_sequence();
        System.out.println(stackPop_sequence.is_StackPop_sequence(in,out));
    }
}