《剑指offer》面试题31：栈的压入、d出序列

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

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

思路：

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

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

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

基于以上思路，参考代码如下：

bool IsPopOrder(const int* pPush,const int* pPop,int nLength)

{

bool bPossible = false;

if(pPush != nullptr && pPop != nullptr && nLength > 0)

{

const int* pNextPush = pPush;

const int* pNextPop = pPop;

std::stack stackData;

while(pNextPop - pPop < nLength)

{

// 当辅助栈的栈顶元素不是要d出的元素

// 先压入一些数字入栈

while(stackData.empty() || stackData.top() != *pNextPop)

{

// 如果所有数字都压入辅助栈了，退出循环

if(pNextPush - pPush == nLength)

break;

stackData.push(*pNextPush);

pNextPush ++;

}

if(stackData.top() != *pNextPop)

break;

stackData.pop();

pNextPop ++;

}

if(stackData.empty() && pNextPop - pPop == nLength)

bPossible = true;

}

return bPossible;

}

测试用例：

a.功能测试（输入的两个数组含有多个数字或者只有一个数字；第二个数组是或者不是第一个数组表示的压入序列对应的栈的d出序列）。

b.特殊输入测试（输入两个nullptr指针）。

参考：

http://www.jb51.cc/article/p-wnhecjuu-pa.HTML

总结

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

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