uva 11995 判别数据类型

2023-12-06 12:39:58

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

题目大意：根据数据的操作<1>插入<2>删除判别是哪一种数据类型，有栈、队列、优先队列几种类型，如三种
都不符合输出impossbile，符合两种以上输出not sure,只符合一种的对应输出它的类型名称。

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#define Max 1010
using namespace std;

int N;
int op[Max],num[Max];
stack<int> S;
queue<int> Q;
priority_queue<int> PQ;
int check_stack()
{
    int i,t;
    while(!S.empty()) S.pop();
    for(i=0;i<N;i++)
    {
        if(op[i]==2)
        {
            if(S.empty()) return 0;
            t=S.top();S.pop();
            if(t!=num[i]) return 0;
        }
        else S.push(num[i]);
    }
    return 1;
}
int check_queue()
{
    int i,t;
    while(!Q.empty()) Q.pop();
    for(i=0;i<N;i++)
    {
        if(op[i]==2)
        {
            if(Q.empty()) return 0;
            t=Q.front();Q.pop();
            if(t!=num[i]) return 0;
        }
        else Q.push(num[i]);
    }
    return 1;
}
int check_priorityqueue()
{
    int i,t;
    while(!PQ.empty()) PQ.pop();
    for(i=0;i<N;i++)
    {
        if(op[i]==2)
        {
            if(PQ.empty()) return 0;
            t=PQ.top();PQ.pop();
            if(t!=num[i]) return 0;
        }
        else PQ.push(num[i]);
    }
    return 1;
}
int main()
{
    int i;
    int s,q,pq;
    while(scanf("%d",&N)!=EOF)
    {
        for(i=0;i<N;i++) scanf("%d %d",op+i,num+i);
        s=check_stack();
        q=check_queue();
        pq=check_priorityqueue();
        if(!s && !q && !pq) printf("impossible\n");
        else if(s && !q && !pq) printf("stack\n");
        else if(!s && q && !pq) printf("queue\n");
        else if(!s && !q && pq) printf("priority queue\n");
        else printf("not sure\n");
    }
    return 0;
}