題目： UVa - 11995 - I Can Guess the Data Structure!

題目說明

給一個整數 n，代表接下來有 n 行的指令，若指令為 1 加上一個數字，代表將該數字放入容器中，若為 2 加上一個數字，代表容器的 top() 或 front() 為該數字，同時將該數字 pop() 出。結束後判斷該容器為 Stack 或 Queue 還是 Priority_queue，若三者都不是則輸出 "impossible"，若兩者以上的容器皆可則輸出 "not sure"。

解題思路

使用三個容器去模擬操作即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <stack>
#include <queue>

using namespace std;

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int main()
{
    int n, cmd, val;
    while (cin >> n)
    {
        bool S = true, Q = true, PQ = true;
        stack<int> s;
        queue<int> q;
        priority_queue<int> pq;
        while (n--)
        {
            cin >> cmd >> val;
            switch (cmd)
            {
            case 1:
                s.push(val), q.push(val), pq.push(val);
                break;
            case 2:
                if (S)
                {
                    if (!s.empty() && s.top() == val) s.pop();
                    else S = false;
                }
                if (Q)
                {
                    if (!q.empty() && q.front() == val) q.pop();
                    else Q = false;
                }
                if (PQ)
                {
                    if (!pq.empty() && pq.top() == val) pq.pop();
                    else PQ = false;
                }
                break;
            }
        }
        if ((S && Q) || (S && PQ) || (Q && PQ)) cout << "not sure\n";
        else if (S) cout << "stack\n";
        else if (Q) cout << "queue\n";
        else if (PQ) cout << "priority queue\n";
        else cout << "impossible\n";
    }
}