剑指offer：栈的压入弹出序列

剑指offer：栈的压入弹出序列2015-09-18剑指offer上的第22题，九度OJ上AC。

题目描述：

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

输入：

每个测试案例包括3行：

第一行为1个整数n（1<=n<=100000），表示序列的长度。

第二行包含n个整数，表示栈的压入顺序。

第三行包含n个整数，表示栈的弹出顺序。

输出：

对应每个测试案例，如果第二个序列是第一个序列的弹出序列输出Yes，否则输出No。

样例输入：

1 2 3 4 5

4 5 3 2 1

1 2 3 4 5

4 3 5 1 2

样例输出：

Yes

判定方法如下：

如果第二个序列中当前要判断的元素刚好与栈顶元素相等，则直接pop出来，如果不等，则将第一个序列的后面还没有入栈的元素入栈，直到将与之相等的元素入栈为止，如果第一个序列的所有的元素都入栈了，还没有找到与之相等的元素，则说明第二个序列不是第一个序列的弹出序列，

AC代码如下：

/* 本程序采用数组模拟栈 */typedef int ElemType;#define MAX 100000 //栈的深度#include<stdio.h>#include<stdlib.h>#include<stdbool.h>int top = -1;/* 在栈顶索引指针为top时，向栈A中压入数据data */bool push（int *A,ElemType data）{if（top>=MAX-1 || top<-1）return false;A[++top] = data;return true;}/* 在栈顶索引指针为top时，出栈 */bool pop（）{if（top<0）return false;top--;return true;}/* 判断popList是否是pushList的弹出序列 */bool IsPopOrder（int *pushList,int *popList,int len,int *stack）{if（popList==NULL || pushList==NULL || len<1）return false;int i;int pushIndex = 0;for（i=0;i<len;i++）{while（top==-1 || stack[top] ！= popList[i]）{//如果没有元素可以push了，就说明不符合if（pushIndex == len）return false;push（stack,pushList[pushIndex++]）;}pop（）;}return true;}int main（）{int n;int stack[MAX]; //辅助栈while（scanf（"%d",&n） ！= EOF）{int *pushList = （int *）malloc（n*sizeof（int））;if（pushList == NULL）exit（EXIT_FAILURE）;int i;for（i=0;i<n;i++）scanf（"%d",pushList+i）;int *popList = （int *）malloc（n*sizeof（int））;if（popList == NULL）exit（EXIT_FAILURE）;for（i=0;i<n;i++）scanf（"%d",popList+i）;if（IsPopOrder（pushList,popList,n,stack））printf（"Yes
"）;elseprintf（"No
"）;free（pushList）;pushList = NULL;free（popList）;popList = NULL;}return 0;}

作者：csdn博客兰亭风雨