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

概述本文章向大家介绍剑指Offer：栈的压入、d出序列，主要包括剑指Offer：栈的压入、d出序列使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

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

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

解题的步骤

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

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

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

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

代码实现

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;

}

总结

以上是内存溢出为你收集整理的剑指Offer：栈的压入、d出序列全部内容，希望文章能够帮你解决剑指Offer：栈的压入、d出序列所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。