andyli

题解 UVA11995 【I Can Guess the Data Structure!】
本题考察了栈、队列和优先队列3种$\text{ADT}$的概念。只要熟悉这些概念,本题不难解决。事实上,$\tex...
扫描右侧二维码阅读全文
18
2019/02

题解 UVA11995 【I Can Guess the Data Structure!】

本题考察了栈、队列和优先队列3种$\text{ADT}$的概念。只要熟悉这些概念,本题不难解决。事实上,$\text{STL}$ 中已经封装好了这3种数据结构,分别是stackqueuepriority_queue。这样,本题只需要依次判断输入是否有可能是栈,队列或优先队列,然后综合起来即可。注意到题目中说的“无错误的返回”,因此在执行pop操作的时候要调用一下empty(),否则可能会异常退出。

代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;

int A[maxn], B[maxn], n;
bool CheckStack()
{
    stack<int> s;
    for (int i = 0; i < n; i++)
    {
        if (A[i] == 2)
        {
            if (s.empty())
                return false;
            int x = s.top();
            s.pop();
            if (x != B[i])
                return false;
        }
        else
            s.push(B[i]);
    }
    return true;
}

bool CheckQueue()
{
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        if (A[i] == 2)
        {
            if (q.empty())
                return false;
            int x = q.front();
            q.pop();
            if (x != B[i])
                return false;
        }
        else
            q.push(B[i]);
    }
    return true;
}

bool CheckPQ()
{
    priority_queue<int> pq;
    for (int i = 0; i < n; i++)
    {
        if (A[i] == 2)
        {
            if (pq.empty())
                return false;
            int x = pq.top();
            pq.pop();
            if (x != B[i])
                return false;
        }
        else
            pq.push(B[i]);
    }
    return true;
}

int main()
{
    while (~scanf("%d", &n))
    {
        for (int i = 0; i < n; i++)
            scanf("%d%d", &A[i], &B[i]);
        int Stack = CheckStack(), Queue = CheckQueue();
        int sum = Stack + Queue + CheckPQ();
        if (!sum)
            printf("impossible");
        else if (sum > 1)
            printf("not sure");
        else if (Stack)
            printf("stack");
        else if (Queue)
            printf("queue");
        else
            printf("priority queue");
        printf("\n");
    }
    return 0;
}
Last modification:June 25th, 2019 at 11:19 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment