题解 | 验证栈序列

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

bool isValidPopSequence(std::vector<int>& pushed, std::vector<int>& popped)
{
    std::stack<int> st;
    int i = 0;//指向popped当前位置

    for(int num : pushed)
    {
        st.push(num);
        while(!st.empty() && st.top() == popped[i])
        {
            st.pop();
            i++;
        }
    }
    return st.empty();
}

int main()
{
    int q = 0;
    int n = 0;
    int num = 0;
    cin >> q;
    getchar();
    vector<int> pushed;
    vector<int> popped;
    
    while(q--)
    {
        pushed.clear();
        popped.clear();
        cin >> n;
        getchar();

        for(int i = 0; i < n; i++)
        {
            cin >> num;
            pushed.push_back(num);
        }

        for(int i = 0; i < n; i++)
        {
            cin >> num;
            popped.push_back(num);
        }
        cout << (isValidPopSequence(pushed, popped) ? "Yes" : "No") << endl;
    }   
}
// 64 位输出请用 printf("%lld")