这道题比较简单。
需要注意的一些地方：
1、impossible: 所有的标记量都是false
2、not sure：同时存在2种情况或者同时存在三种情况.
Problem I
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
61 11 21 32 12 22 361 11 21 32 32 22 121 12 241 21 12 12 271 21 51 11 32 51 42 4
Output for the Sample Input
queuenot sureimpossiblestackpriority queue
Rujia Liu's Present 3: A Data Structure Contest Celebrating the 100th Anniversary of Tsinghua University
Special Thanks: Yiming Li
Note: Please make sure to test your program with the gift I/O files before submitting!
直接对三种数据结构进行模拟，注意当前数据结构为空的时候的判断。
代码如下:
/* * UVA_11995.cpp * * Created on: 2014年12月28日 * Author: Administrator */#include <iostream>#include <cstdio>#include <queue>#include <stack>#include <cstring>using namespace std;const int maxn = 1010;int n;int id[maxn];int x[maxn];bool isStack(){ stack<int> s; int i; for(i = 0 ; i < n ; ++i){ if(id[i] == 1){ s.push(x[i]); }else{ if(s.empty() != true){ int val = s.top(); s.pop(); if(x[i] != val){ return false; } }else{ return false; } } } return true;}bool isQueue(){ queue<int> q; int i; for(i = 0 ; i < n ; ++i){ if(id[i] == 1){ q.push(x[i]); }else{ if(q.empty() != true){ int val = q.front(); q.pop(); if(x[i] != val){ return false; } }else{ return false; } } } return true;}bool isPriority_Queue(){ priority_queue<int> q; int i; for(i = 0 ; i < n ; ++i){ if(id[i] == 1){ q.push(x[i]); }else{ if(q.empty() != true){ int val = q.top(); q.pop(); if(x[i] != val){ return false; } }else{ return false; } } } return true;}int main(){ while(scanf("%d",&n) != EOF){ memset(id,-1,sizeof(id)); memset(x,-1,sizeof(x)); int i; for(i = 0 ; i < n ; ++i){ scanf("%d%d",&id[i],&x[i]); } bool st = isStack(); bool q = isQueue(); bool pq = isPriority_Queue(); if(st == false && q == false && pq == false){ printf("impossible\n"); }else if((st == true && q == true && pq == true) || (st == true && q == true && pq == false) || (st == true && q == false && pq == true) || (st == false && q == true && pq == true)){ printf("not sure\n"); }else if(st == true && q == false && pq == false){ printf("stack\n"); }else if(q == true && st == false && pq == false){ printf("queue\n"); }else if(pq == true && st == false && q == false){ printf("priority queue\n"); } } return 0;}