Question

根据已知入栈顺序判断一个数组是否是出栈顺序

Answer 1

题目含义已经很明确了，现在开始使用一个样例输入和输出

int a[]={1,2,3,4,5};//原始的入栈顺序
int b[]={4,5,3,1,2};//出栈顺序
int b1[]={4,5,3,2,1};//出栈顺序

我的策略是依次遍历给定的出栈顺序数组，从第一个开始，以b为例，

1、第一个元素是4，则在a中确定4所在的位置，将4之前的所有元素入栈记为sck，并记录该位置nCount

2、开始遍历出栈数组的下一个元素，记为tmp，首先根nCount，如果nCount小于长度，也即a[nCount]还是一个有效整数，则判断tmp和a[nCount]是否相等，如果相等，则继续步骤2，如果不相等，判断sck中是否还有元素，如果有，则弹出顶端元素，判断是否相等，如果相等，继续步骤2，不相等则直接返回，不是正确的出战顺序，如果栈中的元素个数为0，同样也退出算法，不正确的出栈顺序

int Check(int* a,int* b1,int length)
{
if(NULL==a||NULL==b1)
return 0;
stacksck;
int nCount=0;
for(int i=0;i<length;i++) {="" int="" tmp="b1[i];" if(i="=0)" 确定tmp在a中的位置="" index="-1;" for(int="" j="0;j<length;j++)" if(tmp="=a[j])" ncount="j+1;" break;="" }="" else="" sck.push(a[j]);="" 将元素已经入栈="" if(index="=-1)" return="" 0;="" 接下来处理一般元素="" 首先查看栈外的第一个元素="" if(ncount0)
{
int mm=sck.top();
sck.pop();
if(mm==tmp)
{
continue;
}
else
{
return 0;
}
}
else
{
return 0;
}
}
}
return 1;
}