《P4387 【深基15.习9】验证栈序列》

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 n(n≤100000)。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes ，否则输出 No 。为了防止骗分，每个测试点有多组数据，不超过 5 组。

输入格式

第一行一个整数 q，询问次数。 接下来 q 个询问，对于每个询问： 第一行一个整数 n 表示序列长度； 第二行 n 个整数表示入栈序列； 第三行 n 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

输入输出样例

输入 #1 复制

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

输出 #1 复制

Yes
No

代码实现： #include #include #include /* run this program using the console pauser or add your own getch, system(“pause”) or input loop */ using namespace std; int main(int argc, char** argv) { int m,n,i,j,c[100001]; cin»m; stack sta; for(j=0;j>n; int a[n],b[n]; for(i=0;i>a[i]; } for(i=0;i>b[i]; } int head=0; for(i=0;i<n;i++) { sta.push(a[i]); while(sta.top()==b[head]) { sta.pop(); head++; if(sta.empty()) { break; } } } if(sta.empty()) { c[j]=1; } else { c[j]=0; } while (!sta.empty()) { sta.pop(); } } for(i=0;i<m;i++) { if(c[i]==0) { cout«“No”«endl; } else { cout«“Yes”«endl; } } return 0; }