力扣对应题目链接：946. 验证栈序列 - 力扣（LeetCode）
牛客对应题目链接：栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
核心考点 ：栈的理解。
一、《剑指Offer》内容
二、分析题目
要判定第二个序列是否可能是该栈的弹出序列，就要使用指定的入栈顺序模拟出来对应的弹栈序列，我们设入栈顺序序列式 pushV，可能出栈序列 popV。
popv 的第一个元素，一定是最后入栈，最先弹栈的， 而我们的入栈顺序是一定的，也就决定了，我们必须一直入栈，直到碰到 popv 的第一个元素，然后开始弹栈。最后在循环这个过程，如果符合要求，最后栈结构一定是空的。
- 遍历入栈序列，只要 popv 的第一个数据和当前 pushv 的数据不相等，一直进行入栈操作。
- 只要 st 栈顶值和 popv 的出栈序列数据是相等的，则一直执行出战逻辑
- 返回 st.empty()
三、代码
//牛客 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型 */ bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { if(pushV.empty() || popV.empty() || pushV.size()!=popV.size()) return false; stack<int> st; int j=0; for(int i=0; i<pushV.size(); i++) { st.push(pushV[i]); while(!st.empty() && st.top()==popV[j]) { st.pop(); j++; } } if(st.empty()) return true; else return false; } }; //力扣 class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { if(pushed.empty() || popped.empty() || pushed.size()!=popped.size()) return false; stack<int> st; int j=0; for(int i=0; i<pushed.size(); i++) { st.push(pushed[i]); while(!st.empty() && st.top()==popped[j]) { st.pop(); j++; } } return st.empty(); } };
