C# · 12月 20, 2021

剑指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;

}