栈

括号匹配等问题可以用栈解决，不过这不是重点。对于给定的入栈序列检验出栈序列是否合法只需要按照顺序将元素入栈，发现栈顶为出栈序列的第一个元素时弹出栈顶和出栈序列的第一个元素即可。最后栈为空则合法，否则不合法。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int n,top,pos,a[100'005],b[100'005],s[100'005];
void solution(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    top=0,pos=1;
    for(int i=1;i<=n;i++){
        s[++top]=a[i];
        while(top!=0&&s[top]==b[pos]) --top,++pos;
    }
    puts(top==0 ? "Yes":"No");
}
int T;
int main(){
    scanf("%d",&T);
    while(T--) solution();
    return 0;
}