Koja je struktura?

Posmatramo nepoznatu strukturu podataka nad celim brojevima. Znamo da je ona tačno jedna od sledećih:

• stek (LIFO);
• red (FIFO).

Data je sekvenca operacija umetanja i izbacivanja. Za svako izbacivanje dato je koja vrednost je izašla iz strukture. Potrebno je utvrditi koja od dve strukture (ako ijedna) može da objasni celu sekvencu.

Ako su obe moguće, ispisati not sure. Ako nijedna ne odgovara, ispisati impossible. Ako je tačno jedna moguća, ispisati stack ili queue.

Opis ulaza

Sa standardnog ulaza se unisi broj upita \(q\) (\(1 \leq q \leq 1000\)). Za svaki upit, sa standardnog ulaza se unosi broj operacija \(n\) (\(1 \leq n \leq 1000\)). Zatim, se unosi \(n\) operacija oblika:

• i x — umetanje vrednosti x u strukturu.
• r x — izbačeni element iz strukture je x.

Vrednosti x je u opsegu od \(-10^5\) do \(10^5\).

Opis izlaza

Za svaki upit, na standardni izlaz ispisati jednu od četiri mogućnosti:

• stack: ako struktura je sigurno stek;
• queue: ako struktura je sigurno red;
• impossible: ako nijedna struktura ne odgovara;
• not sure: ako mogu biti obe strukture;

Primer

Ulaz

4
3
i 10
i 20
r 20
6
i 3
i 2
i 5
r 3
r 2
r 5
2
i 7
r 7
4
r 1
i 1
r 1
r 1

Izlaz

stack
queue
not sure
impossible

Objašnjenje

1. Umetanje 10, 20; izbacivanje 20: jedina moguća struktura je stek, jer bi red izbacio vrednost 10, a ne 20.
2. Umetanje 3, 2, 5; izbacivanje 3, 2, 5: jedina moguća struktura je red, jer di stek izbacio u redosledu 5, 2, 3.
3. Umetanje 7; izbacivanje 7: može biti i red i stek.
4. Izbacivanje 1 iz prazne strukture nije moguće.

Rešenje

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

void simulate(int n)
{
    stack<int> s;
    queue<int> q;

    bool is_stack = true, is_queue = true;
    while (n--) {
        char op; int x;
        cin >> op >> x;
        if (op == 'i') {
            if (is_stack) {
                s.push(x);
            }
            if (is_queue) {
                q.push(x);
            }
        } else { // op == 'r'
            if (is_stack) {
                if (!s.empty() && s.top() == x) {
                    s.pop();
                } else {
                    is_stack = false;
                }
            }
            if (is_queue) {
                if (!q.empty() && q.front() == x) {
                    q.pop();
                } else {
                    is_queue = false;
                }
            }
        }
    }

    if (!is_stack && !is_queue) {
        cout << "impossible" << endl;
    } else if (!is_queue) {
        cout << "stack" << endl;
    } else if (!is_stack) {
        cout << "queue" << endl;
    } else {
        cout << "not sure" << endl;
    }
}

int main() 
{
    int q; cin >> q;

    while (q--) {
        int n; cin >> n;
        simulate(n);
    }
  
    return 0;
}