Solution of 11995 - I Can Guess the Data Structure!

Problem Description
source:https://uva.onlinejudge.org/external/119/p11995.pdf

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). 

Output 

For each test case, output one of the following:

Sample Input

4 1 1 1 1 2 1 2 1

5 1 10 2 10 2 20 2 30 1 40

Sample Output

not sure
impossible


Solution :

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

int main()
{
    long int  i, n, t, x, flags, flagq, flagp;

    while(scanf("%ld",&n)==1)
    {
        stack<long int> mystack;
        queue<long int> myqueue;
        priority_queue<long int> mypq;

        flags=0;
        flagq=0;
        flagp=0;

        for(i=1;i<=n;i++)
        {
            scanf("%ld%ld", &t,&x);
            if(t==1)
            {
                mystack.push(x);
                myqueue.push(x);
                mypq.push(x);

                flags+=1;
                flagq+=1;
                flagp+=1;
            }
            else if(t==2)
            {
                if(!mystack.empty() && mystack.top()==x )
                {
                    mystack.pop();
                    flags+=1;
                }
                if(!myqueue.empty() && myqueue.front()==x )
                {
                    myqueue.pop();
                    flagq+=1;
                }
                if(!mypq.empty() && mypq.top()==x )
                {
                    mypq.pop();
                    flagp+=1;
                }
            }
        }
        if((flags==n && flagq==n)||(flags==n&&flagp==n)||(flagp==n&&flagq==n))
            printf("not sure\n");
        else if(flagp!=n && flagq!=n &&flags!=n)
            printf("impossible\n");
        else if(flags==n)
            printf("stack\n");
        else if(flagq==n)
            printf("queue\n");
        else
            printf("priority queue\n");

    }
    return 0;
}

No comments:

Post a Comment

Write your comment - Share Knowledge and Experience