题解 | 验证栈序列

解决这道题的关键在于模拟匹配的过程，先将入栈和出栈的数据存储到两个数组中，再用栈和这两个数组来模拟进出栈的过程。

1.当栈为空或者栈顶元素和出栈的元素不相同时，则将入栈序列的下一个元素输入.

2.当栈顶元素和出栈的元素相同时，则输出栈顶元素，将出栈序列的指针下移一位，再次进行判断。

当a中所有元素全部入栈后再进行一轮判断，直到栈顶元素和输出序列不同为止。

最后检查栈s中的元素，如果为空则为合法序列，不超过则非法.

#include <iostream>
#include<stack>
using namespace std;
void solve() {
    int n;
    cin >> n;
    int a[n], b[n];
    stack<int> s;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        
    }
    int i=0;//i用于表示入栈序列的指针
    int j=0;
    while(j<n && i!=n){
        if(s.empty()){
            s.push(a[i]);
            i++;
        }else{
            while(!s.empty() && s.top() == b[j]){
                s.pop();
                j++;
            }
            if(i<n){
                s.push(a[i]);
                i++;
            }
            
        }
    }
    while(!s.empty() && s.top() == b[j]){
        s.pop();
        j++;
    }
    if(s.empty()){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    






}

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