2531: 【普及/提高-】【P4387】验证栈序列
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：4
题目描述
给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出
Yes，否则输出 No。为了防止骗分，每个测试点有多组数据。输入
第一行一个整数 ，询问次数。
接下来 个询问，对于每个询问：
第一行一个整数 表示序列长度；
第二行 个整数表示入栈序列；
第三行 个整数表示出栈序列；
输出
对于每个询问输出答案。
样例输入 复制
2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3样例输出 复制
Yes
No提示
#include<bits/stdc++.h>
using namespace std;
stack<int> pushed;
queue<int> poped;
int q,n,a[100010],b;
int main(){
cin>>q;
while (q--) {
cin>>n;
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
scanf("%d",&b),poped.push(b);
for (int i=1;i<=n;i++) {
pushed.push(a[i]);
while (pushed.top()==poped.front()) {
pushed.pop();
poped.pop();
if (pushed.empty()) break;
}
}
if (pushed.empty()&&poped.empty())
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
while (!pushed.empty()) pushed.pop();
while (!poped.empty()) poped.pop();
}
return 0;
}