剑指Offer：栈的压入、弹出序列

剑指Offer题目：栈的压入、弹出序列

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压栈序列，序列4、5、3、2、1是该压栈序列对应的一个弹出序列，但4、3、5、1、2就不可能是该压栈序列的弹出序列。

解题的步骤

-通过分析以上序列，可以得出：

如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。

如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。

如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

代码实现

bool IsPopOrder(vector pushV,vector popV)

{

//出栈元素和入栈元素数量必须一致

if (pushV.size() != popV.size()) return false;

int pushIndex = 0;

int popIndex = 0;

stack s;

while (popIndex < popV.size())

{

//如果栈s为空或者 出栈的元素和栈顶元素不同，那么就入栈

while (s.empty() || s.top() != popV[popIndex])

{

if (pushIndex < pushV.size())

s.push(pushV[pushIndex++]);

else

return false;

}

//如果出栈元素和栈顶元素相同，那么就出栈

s.pop();

popIndex++;

}

return true;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!