StackPushAndPop

发表于 分类于

题目描述[原题链接][https://www.acwing.com/problem/content/description/40/]

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。

例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。

样例

1
2
3
4
输入：[1,2,3,4,5]
      [4,5,3,2,1]

输出：true

算法描述

首先判断两个数组的长度是否相等，如果不相等，直接返回false,接下来是主要算法，每次往栈中压入一个元素，如果栈顶元素与出栈序列的首个元素相等，弹栈，直到栈顶元素与当前出栈序列不相等为止。在操作过程中注意边界条件的处理。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size()!=popV.size())return false;
       stack<int> sta;
       int t=0;
       for(int i=0;i<pushV.size();i++){
            sta.push(pushV[i]);
           while(!sta.empty()&&sta.top()==popV[t]){
               sta.pop();
               t++;
               continue;
           }
       }
       if(sta.empty())return true;
       return false;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isPopOrder(int [] pushV,int [] popV) {
        Stack<Integer> sta = new Stack<>();
        if(pushV.length!=popV.length)return false;
        int i=0;
        for(int t : pushV){
            sta.push(t);
            while(!sta.empty()&&sta.peek()==popV[i]){
                sta.pop();
                i++;
            }
        }
        if(i==pushV.length)return true;
        return false;
    }
}