Problems-Solving/C++/GuessDequePriorityQueue.cpp at develop · hienmv/Problems-Solving · GitHub

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/** https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3146
 * #queue #stack #priority-queue
 * provided that the data structure is used is queue/stack/priorityQueue(maxHeap).
 */
#include<iostream>
#include<stack>
#include<queue>

using namespace std;

int main() {
    int n;
    while(cin >> n) {
        if (n == 0) {
            break;
        }
        bool stackFlg = true;
        bool queueFlg = true;
        bool priorityQueueFlg = true;
        stack<int> st;
        queue<int> q;
        priority_queue<int> pq;
        for (int i=0; i < n; i++) {
            int command, val;
            cin >> command;
            cin >> val;
            if (command == 1) {
                if (stackFlg) st.push(val);
                if (queueFlg) q.push(val);
                if (priorityQueueFlg) pq.push(val);
            } else {
                if (stackFlg && !st.empty() && st.top() == val){
                    st.pop();
                } else {
                    stackFlg = false;
                }
                if (queueFlg && !q.empty() && q.front() == val) {
                    q.pop();
                } else {
                    queueFlg = false;
                }
                if (priorityQueueFlg && !pq.empty() && pq.top() == val) {
                    pq.pop();
                } else {
                    priorityQueueFlg = false;
                }
            }
        }

        string result[3];
        int count = 0;
        if (queueFlg) {
            result[count++] = "queue";
        }
        if (stackFlg) {
            result[count++] = "stack";
        }
        if (priorityQueueFlg) {
            result[count++] = "priority queue";
        }
        if (count == 0) {
            cout << "impossible" << endl;
        } else if (count == 1) {
            cout << result[0] << endl;
        } else {
            cout << "not sure" << endl;
        }
    }

    return 0;
}