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.

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

Output for the Sample Input

queue
not sure
impossible
stack
priority 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!

好久没A题了，，今天刷会题，整理整理，，下个月恢复状态！！！！

大概题意：输入输出几组数据，，要你判断是哪一种数据结构（栈，队列，优先队列，或者全部是，或者两者及以上）

注意执行pop操作时要注意调用一下empty（），否则可能会异常退出。。。

思路：调用STL，，然后模拟其过程。。。

AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

int main()
{
	int n;
	while(scanf("%d", &n) != EOF)
	{
		int st = 1, qu = 1, pr = 1;
		stack<int> s;
		queue<int> q;
		priority_queue<int> p;
		int a, b;
		while(n--)
		{
			scanf("%d %d", &a, &b);
			if(a == 1) 
			{
				s.push(b);
				q.push(b);
				p.push(b);
			}
			else 
			{
				if(!s.empty() && s.top() == b) s.pop();
				else st = 0;
				if(!q.empty() && q.front() == b) q.pop();
				else qu = 0;
				if(!p.empty() && p.top() == b) p.pop();
				else pr = 0;
			}
		}
		if(st + qu + pr >= 2) printf("not sure\n");
		else if(st == 1) printf("stack\n");
		else if(qu == 1) printf("queue\n");
		else if(pr == 1) printf("priority queue\n");
		else if(st == 0 && qu == 0 && pr == 0) printf("impossible\n");
	}
	return 0;
}

UVA - 11995 - I Can Guess the Data Structure! （基础数据结构练习题！）