牛客刷题之JZ31.栈的压入、弹出序列（C++）

1.题目解析

本题给出两个序列，判断一个序列压入栈后的弹出序列是否有可能成为另一个序列，核心难度就是如何判断能否满足弹出序列

2.算法原理

这里的算法思路是讲压入栈的序列模拟弹出，即将压入的序列与弹出的序列对比，相同则将压入栈的元素与弹出栈的元素同时弹出，最后判断压入栈内是否还残留元素，如果没有剩下则代表模拟成功，即符合另一序列的弹出顺序，反之则不满足

3.代码展示

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code here//使用一个栈模拟弹出顺序//比较是否符合指定弹出顺序size_t popi = 0;stack<int> st;for(auto& e : pushV){st.push(e);while(!st.empty() && st.top() == popV[popi]){st.pop();popi++;}}//如果原来的栈为空则代表模拟成功,符合弹出顺序return st.empty();}
};