洛谷题单指南-线性表-P4387 【深基15.习9】验证栈序列

原题链接：https://www.luogu.com.cn/problem/P4387

题意解读：判断一组序列入栈后，出栈序列的合法性。

解题思路：

数据长度100000，直接模拟堆栈的入栈和出栈即可

遍历每一个入栈元素，依次入栈，

每一个元素入栈后，比较栈顶元素和出栈序列第一个，

如果相等，则出栈，持续进行比较、出栈直到不相等或者堆栈空，

最后，如果堆栈空，表示出栈序列有效，否则表示无效。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int a[N]; //入栈序列
int b[N]; //出栈序列

int t, n;

int main()
{
    cin >> t;
    while(t--)
    {
        stack<int> stk;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++) cin >> b[i];
        int j = 1;
        for(int i = 1; i <= n; i++)
        {
            stk.push(a[i]); //依次按入栈序列入栈
            while(stk.size() && stk.top() == b[j]) //如果栈顶元素等于出栈序列第一个,持续出栈
            {
                stk.pop(); //栈顶弹出
                j++; //出栈序列指针移到下一个
            }
        }
        if(stk.empty()) cout << "Yes" << endl; //堆栈为空则说明出栈序列合法
        else cout << "No" << endl;
    }

    return 0;
}