题解 P4387 【【深基15.习9】验证栈序列】

· · 题解

蒟蒻的第二篇题解~STL大法好

在红题里找黄题做

通过简单地阅读题目可知，对于给定的入栈序列 poshed话说为什么不是pushed，错字受，验证序列poped是否为入栈序列可能的一个出栈序列。

由于数据范围比较小(n≤100000)不会爆栈，那为什么不用STL来模拟呢（STL大法好！破音~）

下面是最爱的代码

#include<iostream>
#include<stack>
using namespace std;
stack<int>q;//栈q 
int p,n;//p组数据，n为序列长度 
int main()
{
    cin>>p;
    while(p--)
    {
        cin>>n;
        int a[n+1],b[n+1],sum=1;//入栈队列a，待检验队列b，计数器sum 
        for(int i=1;i<=n;i++)
        cin>>a[i];
        for(int i=1;i<=n;i++)
        cin>>b[i];//平平无奇的输入 
        for(int i=1;i<=n;i++)
        {
            q.push(a[i]);//入栈 
            while((q.top())==b[sum])//当栈顶元素与b中当前元素相同时出栈 
            {
                q.pop(),sum++;//sum++到b下一个元素 
                if(q.empty())break;//注意这里，第一次RE就因为当栈空时还用了出栈操作，所以要手动结束循环 
            }
        }
        if(q.empty()) cout<<"Yes"<<endl;//如果栈为空说明出栈序列b正确 
        else cout<<"No"<<endl;
        while(!q.empty())q.pop();//清空栈 
    }
    return 0;//谢幕 
}

喜欢就点个赞吧！