首页 > 代码库 > T4308 数据结构判断

T4308 数据结构判断

https://www.luogu.org/record/show?rid=2143639

题目描述

在世界的东边,有三瓶雪碧。

——laekov

黎大爷为了虐 zhx,给 zhx 出了这样一道题。黎大爷搞了一个数据结构,但

是他没有告诉 zhx 这到底是什么数据结构,我们只知道这是一个数据结构。为了

让 zhx 知道这是什么数据结构,黎大爷制造了很多次的输入和输出操作。每次加

入操作,黎大爷会告诉你他向这个数据结构加入了一个数并告诉你这是多少;每

次取出操作,黎大爷会从数据结构之中取出一个数并告诉这是多少。黎大爷希望

zhx 根据这些操作来判断这是什么数据结构,但是 zhx 觉得这题太难了所以跑路

了,于是黎大爷把这道题扔给了你。

输入输出格式

输入格式:

第一行一个整数N代表操作的数目。

接下来N行,每行两个整数opt,v。如果opt = 1,代表黎大爷把v加入了数据

结构;如果opt = 2,代表了黎大爷从数据结构中取出了一个数,值是v。

输出格式:

输出总共三行,第一行代表数据结构是否可能是栈,第二行代表数据结构是

否可能是队列,第三行代表数据结构是否可能大根堆。每一行的结果都只可能是

“YES”或者“NO” 。

输入输出样例

输入样例#1:
21 12 1
输出样例#1:
YESYESYES

说明

对于100%的数据,1 ≤ n ≤ 10 3 。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<stack> 6 using namespace std; 7 int ans1,ans2,ans3;//默认是目标数据结构  8 stack<int>s; 9 queue<int>q;10 priority_queue<int>heap;11 int main()12 {13     int n;14     cin>>n;15     for(int i=1;i<=n;i++)16     {17         int p,d;18         cin>>p;19         if(p==1)20         {21             cin>>d;22             s.push(d);q.push(d);heap.push(d);23         }24         else25         {26             cin>>d;27             if(s.size()==0||q.size()==0||heap.size()==0)28             {29                 cout<<"NO"<<endl;30                 cout<<"NO"<<endl;31                 cout<<"NO"<<endl;32                 return 0;33             }34             if(d!=s.top())ans1=1;35             if(s.size()!=0)36             s.pop();37             38             if(d!=q.front())ans2=1;39             if(q.size()!=0)40             q.pop();41             42             if(d!=heap.top())ans3=1;43             if(heap.size()!=0)44             heap.pop();45             46         }47     }48     if(ans1==0)49     cout<<"YES"<<endl;50     else cout<<"NO"<<endl;51     if(ans2==0)52     cout<<"YES"<<endl;53     else cout<<"NO"<<endl;54     if(ans3==0)55     cout<<"YES"<<endl;56     else cout<<"NO"<<endl;57     return 0;58 }

 

 

T4308 数据结构判断