题解 | 验证栈序列

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
//使用双指针法可以很好地解决这个文体1
//分析一下可以知道 入栈序列代表的是入栈的顺序 出栈序列代表的是出栈的顺序
//那么我们可以以出栈序列为基准 遍历入栈序列 一旦入栈数字和出栈数字相同 那就让它出栈 这样就确保了按照出栈顺序的顺序进行出栈
// 那么符合条件的话最后栈就是空的 可以用i和j两个下标来索引两个数组
// 这个题很容易出现进入死循环的情况 不能最外层循环是出栈序列 如果是的话·1很容易在结果为No的时候卡主出不来 因为如果是No j会卡主不动 而如果想要用i作为外层循环的话 里面pop的时候需要while循环不断pop 这样才能正确实现 不然因为i一共就会5次 但是不能保证每一次都pop 这样的话肯定pop不完 就会一直是No
int main() {
    int q;
    cin>>q;
    while(q--)
    {
        stack<int>st;
        int n;
        cin>>n;
        vector<int>pushed;
        vector<int>poped;
        for(int i=0;i<n;i++)
        {
            int a;
            cin>>a;
            pushed.push_back(a);
        }
        for(int i=0;i<n;i++)
        {
            int a;
            cin>>a;
            poped.push_back(a);
        }
        int i=0;
        int j=0;
        for(int i=0;i<n&&j<n;)
        {
            if(i<n){
                st.push(pushed[i]);
                i++;
            }
            if(st.empty()!=true){
                //依旧是empty要放在前面 不然容易出现段错误
                while(st.empty()!=true&&st.top()==poped[j])
                {
                    st.pop();
                    j++;
                }
            }
        }
        if(st.empty()==true)
        {
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
        }
    }
}
// 64 位输出请用 printf("%lld")