本文共 1306 字，大约阅读时间需要 4 分钟。

地址：http://ac.jobdu.com/problem.php?pid=1366

题目1366：栈的压入、弹出序列

题目描述：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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。

样例输入：

51 2 3 4 54 5 3 2 151 2 3 4 54 3 5 1 2

样例输出：

YesNo

1、将入栈顺序放入数组a，弹栈顺序放入数组b

2、将数组b中元素与栈顶元素相比。相等，弹出；不相等，压入a中新元素。直到a中元素全部遍历完成

3、检查栈是否为空。为空，正确；否则，错误。

#include 
    
     #include 
     
      #include 
      
       using namespace std;int main(){	int n;	stack
       
         S;	while(scanf("%d", &n) != EOF){		int *a = (int *)malloc(sizeof(int) * n);		int *b = (int *)malloc(sizeof(int) * n);		while(!S.empty())			S.pop();		for(int i = 0; i < n; i ++)			scanf("%d", &a[i]);		for(int i = 0; i < n; i ++)			scanf("%d", &b[i]);		S.push(a[0]);		for(int i = 0, j = 0; i < n && j < n; ){			if(!S.empty() && S.top() == b[j]){				S.pop();				j ++;				continue;			}			else{				i ++;				S.push(a[i]);			}		}		if(!S.empty())			printf("No\n");		else			printf("Yes\n");	}	return 0;}/**************************************************************	Problem: 1366	Language: C++	Result: Accepted	Time:200 ms	Memory:4556 kb****************************************************************/
       
      
     
    

转载地址：http://cesob.baihongyu.com/