题解 | 验证栈序列

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    int q;
    cin >> q;

    while (q--) {
        int n;
        cin >> n;

        vector<int> ruzhanxulie(n);
        vector<int> chuzhanxulie(n);

        // 读取入栈序列
        for (int i = 0; i < n; i++) {
            cin >> ruzhanxulie[i];
        }

        // 读取出栈序列
        for (int i = 0; i < n; i++) {
            cin >> chuzhanxulie[i];
        }

        stack<int> zhan;
        int shijilu = 0;
        bool panduan = true;

        for (int i = 0; i < n; i++) {
            int target = chuzhanxulie[i];
            
            // 如果栈为空或者栈顶不是目标元素，就继续入栈直到找到目标
            while (shijilu < n && (zhan.empty() || zhan.top() != target)) {
                zhan.push(ruzhanxulie[shijilu++]);
            }
            
            // 检查栈顶是否等于目标元素
            if (!zhan.empty() && zhan.top() == target) {
                zhan.pop();
            } else {
                panduan = false;
                break;
            }
        }

        if (panduan && zhan.empty()) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")