每日一题(35)

5imobi

　　题目来自剑指Offer
　　题目：
　　


　　思路：根据弹出序列和一个辅助栈来模拟进栈操作。
　　对于弹出序列中的一个元素V，
　　1、如果栈为空或者栈顶元素不等于V，则去压栈序列中寻找结点V，
　　（1）如果在压栈序列中能找到结点V，并把寻找结点V的过程中遇到的顶点压入辅助栈中。
　　（2）如果不能找到结点V，则表示该元素已经在栈中或者该元素不存在，此时该数字是不合法的弹出序列。
　　2、如果栈顶元素等于V，则辅助栈中的元素出栈。继续处理下一个元素。
　　代码
　　

#include <iostream>
#include <assert.h>
using namespace std;
bool IsPopOrder(int nArrPop[],int nArrPush[],int nLen)
{
assert(nArrPop && nArrPush && nLen > 0);
int* Stack = new int[nLen];
int nTop = -1;
int nCurPush = -1;
int nCurPop = 0;
while (nCurPop < nLen)
{
while ((-1 == nTop || Stack[nTop] != nArrPop[nCurPop]) && nCurPush < nLen - 1)
{
Stack[++nTop] = nArrPush[++nCurPush];
}
if (Stack[nTop] == nArrPop[nCurPop])
{
nCurPop++;//处理出栈序列中的元素
nTop--; //栈中元素出栈
continue;
}
if (nCurPush == nLen - 1) //出栈序列中一个元素到入栈序列中没找着
{
return false;
}
}
return true;
}
int main()
{
//int nArrPush[5] = {1,2,3,4,5};
//int nArrPop[5] = {4,3,5,1,2};
//int nArrPush[5] = {1,2,3,4,5};
//int nArrPop[5] = {4,3,5,2,1};
int nArrPush[5] = {1};
int nArrPop[5] = {1};
if (IsPopOrder(nArrPop,nArrPush,1))
{
cout<<&quot;合法出栈序列!&quot;<<endl;
}
else
{
cout<<&quot;不合法出栈序列!&quot;<<endl;
}
system(&quot;pause&quot;);
return 1;
}