题解 | 验证栈序列

//算法练习 No.23
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

string solve()
{
   int n;
   if(!(cin >> n)) return "No";//防止错误读取

   vector<int> pushed(n);
   vector<int> popped(n);

   for(int i = 0;i<n;i++) cin >> pushed[i];
   for(int i = 0;i<n;i++) cin >> popped[i];

   stack<int> stk;
   int pop_index {0};

   for(int i = 0;i<n;i++)
   {
    stk.push(pushed[i]);
    while(!(stk.empty()) && stk.top() == popped[pop_index])// 必须用 while，因为可能入栈一个，连着出栈好几个
    {
        stk.pop();
        pop_index++;
    }

   }
   
    if(stk.empty())
        return "Yes";
    else
        return "No";

}

int main() {
    
    int q;
    cin >> q;
    while(q--)
    {
        cout << solve() << endl;
    }
   

}
// 64 位输出请用 printf("%lld")