栈的压入、弹出序列
C++,栈模拟。
模拟所有数据出栈和入栈的过程:
- 遍历要出栈的每个元素;
- 如果栈顶不是当前要出栈的元素,说明得继续入栈;
- 入栈直到栈顶是当前要出栈的元素;
- 最后正常的话,所有元素都出栈;
- 不正常的话,会出现要出栈的某个元素A,就算把所有元素都入栈,都无法让栈顶元素B = A;
代码:
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> s;
int m = pushV.size();
int j = 0;
for (int &it : popV) {
while (s.empty() || s.top() != it) {
s.push(pushV[j++]);
if (j >= m) break;
}
if (j >= m && s.top() != it)
return false;
s.pop();
}
return true;
}
};