题解 | 验证栈序列

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin>>q;
    while(q--)
    {
        int n;
        cin>>n;
        vector<int>x1(n);
        vector<int>x2(n);
        stack<int>p;
        for(int i=0;i<n;i++)//入栈序列
        {
            cin>>x1[i];
        }
        for(int j=0;j<n;j++)//出栈序列
        {
            cin>>x2[j];
        }
        int push_index=0;//下一个要入栈的元素
        bool is_vaild=true;//默认为合法序列
        for(int k=0;k<n;k++)
        {
           while(p.empty()||p.top()!=x2[k])
           {
                if(push_index>=n)//入栈元素均压入，但栈顶元素仍然无法匹配
                {
                    is_vaild=false;
                    break;
                }
                p.push(x1[push_index++]);
           }
           if(!is_vaild)//非法序列，直接跳出循环
           {
                break;
           }
           p.pop();
        }
        if(!p.empty())
            cout<<"No"<<"\n";
        else
            cout<<"Yes"<<"\n";
    }
}