每日一题(35)
题目来自剑指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;
int nTop = -1;
int nCurPush = -1;
int nCurPop = 0;
while (nCurPop < nLen)
{
while ((-1 == nTop || Stack != nArrPop) && nCurPush < nLen - 1)
{
Stack[++nTop] = nArrPush[++nCurPush];
}
if (Stack == nArrPop)
{
nCurPop++;//处理出栈序列中的元素
nTop--; //栈中元素出栈
continue;
}
if (nCurPush == nLen - 1) //出栈序列中一个元素到入栈序列中没找着
{
return false;
}
}
return true;
}
int main()
{
//int nArrPush = {1,2,3,4,5};
//int nArrPop = {4,3,5,1,2};
//int nArrPush = {1,2,3,4,5};
//int nArrPop = {4,3,5,2,1};
int nArrPush = {1};
int nArrPop = {1};
if (IsPopOrder(nArrPop,nArrPush,1))
{
cout<<"合法出栈序列!"<<endl;
}
else
{
cout<<"不合法出栈序列!"<<endl;
}
system("pause");
return 1;
}
页:
[1]