CSS3垂直时间轴-Demo马航失联
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). The size of input file does not exceed 1MB.
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
Output for the Sample Input
queue not sure impossible stack priority queue
题意:有一个类似”包“的数据结构,支持两种操作:
1 a 把元素a放进包里
2 a 从包里取出a
给出一系列操作,问你这个包代表的是什么.可能是栈,可能是队列,也有可能是优先队列(数值大的先出)或者其他的东西。
分析:题目不难,要注意一个问题:当”包“为空时,不能从包里取东西。
代码:
#include<stdio.h> #include<stack> #include<queue> using namespace std; int main() { int n, i, k, a, f[4]; while(~scanf("%d",&n)) { stack<int> s; queue<int> q; priority_queue<int, vector<int>, less<int> > pq; for(i = 0; i < 3; i++) f[i] = 1; for(i = 0; i < n; i++) { scanf("%d%d",&k,&a); if(k == 1) { s.push(a); q.push(a); pq.push(a); } else { if(!s.empty()) { if(s.top() != a) f[0] = 0; s.pop(); } else f[0] = 0; if(!q.empty()) { if(q.front() != a) f[1] = 0; q.pop(); } else f[1] = 0; if(!pq.empty()) { if(pq.top() != a) f[2] = 0; pq.pop(); } else f[2] = 0; } } int cnt = 0; for(i = 0; i < 3; i++) if(f[i] == 1) cnt++; if(cnt == 0) printf("impossible\n"); else if(cnt > 1) printf("not sure\n"); else { if(f[0] == 1) printf("stack\n"); else if(f[1] == 1) printf("queue\n"); else printf("priority queue\n"); } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。