牛客_JZ31 栈的压入、弹出序列
✨✨ 欢迎大家来到小伞的大讲堂✨✨
🎈🎈养成好习惯，先赞后看哦~🎈🎈
所属专栏：C++_OJ
小伞的主页：xiaosan_blog
栈的压入、弹出序列
栈的压入、弹出序列_牛客题霸_牛客网
描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同
示例1
输入：
[1,2,3,4,5],[4,5,3,2,1]复制返回值：
true复制说明：
可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop() 这样的顺序得到[4,5,3,2,1]这个序列，返回true示例2
输入：
[1,2,3,4,5],[4,3,5,1,2]复制返回值：
false复制说明：
由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false
解题思路
利用辅助栈模拟弹出
压入压入栈的首个元素，在进行判断((s.top() == *it_pop)),如果不等，压入压入栈的下个元素
当((s.top() == *it_pop))等于时
辅助栈栈顶元素出栈，it_pop++指向下一元素，再次进入循环判断，新的辅助栈的栈顶是否与++后的*it_pop的值相等，所以此处应该加入一个判断
这里另起一图，当下一元素与*it_pop相等
返回true的条件，辅助栈最后的元素为NULL，说明与弹出栈匹配
否则为false
#include <iostream>
#include<stack>
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
// write code here
stack<int> s;//辅助栈
vector<int>::iterator it_push = pushV.begin();
vector<int>::iterator it_pop = popV.begin();
s.push(*it_push);//插入栈中
while (it_push != pushV.end() && it_pop != popV.end()) {
if(s.top() == *it_pop) {
s.pop();
it_pop++;
if (s.empty() && it_push != pushV.end() && it_pop != popV.end()) {
it_push++;
s.push(*it_push);//插入栈中
}//如果辅助栈为空，但是其余栈并没有完全入栈，则再次进行插入
}else{
it_push++;
s.push(*it_push);//插入栈中
}
}
if (s.empty()) {
return true;
} else {
return false;
}
}
};