题目描述

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

输入格式

第一行一个整数 $q$，询问次数。

接下来 $q$ 个询问，对于每个询问：

第一行一个整数 $n$ 表示序列长度；

第二行 $n$ 个整数表示入栈序列；

第三行 $n$ 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

样例输入

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

样例输出

Yes
No

算法思想（模拟）

根据题目描述，按照序列$A$的顺序进栈，能否按照序列$B$的顺序正确出栈。那么只要遍历要出栈的每一个元素BiB_iBi​：

• 如果当前栈顶元素就是BiB_iBi​，直接出栈即可
• 否则，当前栈顶元素不是BiB_iBi​，则按照入栈顺序将AjA_jAj​入栈，直到栈顶元素为BiB_iBi​。如果无法找到BiB_iBi​，则枚举结束。
• 出栈序列枚举完毕后，检查栈是否为空，如果不为空则出栈序列不正确。

代码实现

#include <iostream>
#include <stack>
using namespace std;const int N = 1e5 + 10;
int a[N], b[N];
int main()
{int q, n;cin >> q;while(q --) {cin >> n;for(int i = 1; i <= n; i ++) cin >> a[i];for(int i = 1; i <= n; i ++) cin >> b[i];stack<int> stk;for(int i = 1, j = 1; i <= n; i ++) {//如果栈顶是当前要出栈的元素，直接出栈if(!stk.empty() && stk.top() == b[i]) stk.pop();else{//按入栈顺序将元素入栈stk.push(a[j ++]);//如果栈顶不是当前元素就继续将元素入栈while(stk.top() != b[i] && j <= n) stk.push(a[j ++]);if(stk.top() == b[i]) stk.pop();else break;}}if(stk.empty()) puts("Yes");else puts("No");}
}