刷题——栈的压入弹出

文章目录

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

简单分析：
由题目可知，会给两个数组，第一个为入栈顺序的元素，第二个为出栈顺序的数组。这道题的思路非常简单，首先将第一个数组的元素以特定要求存入栈中，同时在与出栈顺序比较即可。

代码实现：

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      Stack<Integer> stack = new Stack<>();
          int j = 0;
          int n = pushA.length;
          for(int i = 0;i < n;i++){
            //入栈操作，当栈为空，或栈顶元素不为出栈数组
            while(j < n && (stack.isEmpty()||stack.peek() != popA[i])){
                stack.push(pushA[j]);
                j++;
            }
            //查看是否出栈
            if(stack.peek() == popA[i]){
                stack.pop();
            }
            else{
                return false;
            }
        }
        //全部完成后表明正确
        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