首页 > 代码库 > uva 11995 I Can Guess the Data Structure!

uva 11995 I Can Guess the Data Structure!

There is a bag-like data structure, supporting two operations: 1 x Throw an element x into the bag. 2 Take out an element from the bag. Given a sequence of operations with return values, you’re going to guess the data structure. It is a stack (Last-In, First-Out), a queue (First-In, First-Out), a priority-queue (Always take out larger elements first) or something else that you can hardly imagine! Input There are several test cases. Each test case begins with a line containing a single integer n (1 ≤ n ≤ 1000). Each of the next n lines is either a type-1 command, or an integer 2 followed by an integer x. That means after executing a type-2 command, we get an element x without error. The value of x is always a positive integer not larger than 100. The input is terminated by end-of-file (EOF). Output For each test case, output one of the following: stack It’s definitely a stack. queue It’s definitely a queue. priority queue It’s definitely a priority queue. impossible It can’t be a stack, a queue or a priority queue. not sure It can be more than one of the three data structures mentioned above.

Sample Input

6 1 1 1 2 1 3 2 1 2 2 2 3 6 1 1 1 2 1 3 2 3 2 2 2 1 2 1 1 2 2 4 1 2 1 1 2 1 2 2 7 1 2 1 5 1 1 1 3 2 5 1 4 2 4

Sample Output

queue not sure impossible stack priority queue

————————————————————我是分割线——————————————————

纯模拟题目。

祝大家都ak愉快。

技术分享
 1 /* 2     Problem: 3     OJ: 4     User:    S.B.S. 5     Time: 6     Memory: 7     Length: 8 */ 9 #include<bits/stdc++.h>10 #include<iostream>11 #include<cstdio>12 #include<cstring>13 #include<cmath>14 #include<algorithm>15 #include<queue>16 #include<cstdlib>17 #include<iomanip>18 #include<cassert>19 #include<climits>20 #include<functional>21 #include<stack>22 #include<bitset>23 #include<vector>24 #include<list>25 #define F(i,j,k) for(int i=j;i<k;++i)26 #define M(a,b) memset(a,b,sizeof(a))27 #define FF(i,j,k) for(int i=j;i>=k;i--)28 #define maxn 1000129 #define inf 0x3f3f3f3f30 #define maxm 400131 #define mod 99824435332 #define LOCAL33 using namespace std;34 int read(){35     int x=0,f=1;char ch=getchar();36     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}37     while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}38     return x*f;39 }40 int n,m;41 struct POINT42 {43     int id;44     int data;45     friend bool operator < (POINT a,POINT b){return a.data < b.data;}46 }d[maxn];47 inline bool pdstk()48 {49     stack<int> stk;50     F(i,0,n){51         if(d[i].id==1) stk.push(d[i].data);52         if(d[i].id==2){53             if(stk.empty()) return false;54             if(stk.top()==d[i].data){stk.pop();continue;}55             else return false;56         }57     }58     return true;59 }60 inline bool pdque()61 {62     queue<int> q;63     F(i,0,n){64         if(d[i].id==1) q.push(d[i].data);65         if(d[i].id==2){66             if(q.empty()) return false;67             if (q.front()==d[i].data){q.pop();continue;}68               else return 0;69         }70     }71     return true;72 }73 inline bool pdheap()74 {75     priority_queue<POINT> h;76     F(i,0,n){77         if (d[i].id==1) h.push(d[i]);78         if(d[i].id==2){79               if(h.empty()) return false;80               if(h.top().data=http://www.mamicode.com/=d[i].data){h.pop();continue;}81               else return 0;82           }83     }84     return true;85 }86 int main()87 {88     std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;89     #ifdef LOCAL90     freopen("qu.in","r",stdin);91     freopen("qu.out","w",stdout);92     #endif93     cin>>n;94     F(i,0,n) cin>>d[i].id>>d[i].data;95     if(pdstk()) cout<<"YES"<<endl;else cout<<"No"<<endl;96     if(pdque()) cout<<"YES"<<endl;else cout<<"No"<<endl;97     if(pdheap()) cout<<"YES"<<endl;else cout<<"No"<<endl;98     return 0;99 }
uva 11995

 

uva 11995 I Can Guess the Data Structure!