栈的压入、弹出序列

题目描述

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

样例输入

5 1 2 3 4 5  4 5 3 2 1  5 1 2 3 4 5  4 3 5 1 2

样例输出

Yes No

 

解题思路：先定义一个辅助栈，让它进一个跟结果比较一次，如果对的话就出栈，不对的话就继续进栈。当元素全部比较一次后，如果辅助栈内还有元素，说明这个出栈序列是错的。

 

#include <stdio.h> #include <string.h> #include <stack> using namespace std; const int MAXN = 100005; int s[MAXN]; int r[MAXN]; stack <int> S; int main() { int s[105]; int r[105]; int i,j,k; int n; while(~scanf("%d",&n)){ for (i = 0; i < n; i++) { scanf("%d", &s[i]); } for (i = 0; i < n; i++) { scanf("%d", &r[i]); } k = 0; //出栈的（r[]) 下表 for (i = 0; i < n; i++) { S.push(s[i]); while (S.top() == r[k]) { S.pop(); k++; if (S.empty()) { break; } } } if (S.empty()) { printf("Yes\n"); } else { printf("No\n"); } } return 0; }