- 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
- #include <iostream>
- #include <queue>
- #include <stack>
- #include<cstdio>
- using namespace std;
- int main()
- {
- int n;
- int i,x,y;
- while(cin>>n)
- {
- stack<int>s;
- queue<int>q;
- priority_queue<int>pq;
- int flag=0; // 判断输入符合几种情况
- int a[3]={1,1,1}; // 三个数组元素, 分别对应三种数据结构
- for(i=0;i<n;i++)
- {
- cin>>x>>y;
- if(x==1) // 将输入的数字分别放进三种数据结构里
- {
- s.push(y);
- q.push(y);
- pq.push(y);
- }
- else //x=2 的情况, 也就是将每种数据结构元素拿出来和输入的数进行比较
- {
- if(!q.empty()&&a[0]==1) // 不为空且 a=1
- {
- int b=q.front(); // 判断
- q.pop();
- if(y!=b) // 不相同, 把 a 置零反之 a=1
- a[0]=0;
- }
- else a[0]=0; // 为空的情况 a 也是等于 1
- if(!s.empty()&&a[1]==1)
- {
- int b=s.top();
- s.pop();
- if(y!=b)
- a[1]=0;
- }
- else a[1]=0;
- if(!pq.empty()&&a[2]==1)
- {
- int b=pq.top();
- pq.pop();
- if(y!=b)
- a[2]=0;
- }
- else a[2]=0;
- }
- }
- for(i=0;i<3;i++) // 计算有多少种数据结构满足输入条件
- {
- if(a[i]==1)
- flag++;
- }
- if(flag==0)
- cout<<"impossible"<<endl;
- else if(flag==1)
- {
- if(a[0]==1)
- cout<<"queue"<<endl;
- else if(a[1]==1)
- cout<<"stack"<<endl;
- else if(a[2]==1)
- cout<<"priority queue"<<endl;
- }
- else if(flag>1)
- cout<<"not sure"<<endl;
- }
- return 0;
- }
大概思路: 1 的数字输入完之后, 进入 2 数字判断, y 与每种数据结构出来的元素进行判断.
顺, 别忘记判断为空的情况
来源: http://www.bubuko.com/infodetail-2944751.html