首页 > > 程序设计 > C/C++ >

T4308 数据结构判断

2018-06-17 22:39:39来源：未知阅读 ()

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：

2
1 1
2 1

输出样例#1：

YES
YES
YES

说明

对于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         else
25         {
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 }