ADA and Queue#11789

ADA and Queue (Editorial)

Solution

General Idea : The problem simulates a queue with five possible operations: push_back, toFront, front, back, and reverse.

A naive solution would physically reverse the queue each time we see the reverse command, but this would be too slow if done repeatedly.

Instead, we observe that reversing the queue only affects **how we interpret the front and back**, not the actual order stored in memory.

We maintain:

A deque to allow pushing and popping from both ends.
A boolean (or counter) flag rev indicating whether the queue is currently reversed.

Key Observation: If the queue is reversed, then:

front behaves like back
back behaves like front
push_back becomes push_front
toFront becomes push_back

So instead of reversing the deque, we just toggle the flag.

If a pop operation is requested while the deque is empty, we print: [ "Nothing to do in ADA" ]

Complexity: [ O(q) ] since each operation is handled in constant time.


#include <bits/stdc++.h>
using namespace std;

void solve() {
    int q;
    cin >> q;

    deque<int> dq;
    bool rev = false;

    while (q--) {
        string cmd;
        cin >> cmd;

        if (cmd == "toFront") {
            int x; cin >> x;
            if (!rev) dq.push_front(x);
            else dq.push_back(x);
        }
        else if (cmd == "push_back") {
            int x; cin >> x;
            if (!rev) dq.push_back(x);
            else dq.push_front(x);
        }
        else if (cmd == "front") {
            if (dq.empty()) {
                cout << "Nothing to do in ADA\n";
            } else {
                if (!rev) {
                    cout << dq.front() << "\n";
                    dq.pop_front();
                } else {
                    cout << dq.back() << "\n";
                    dq.pop_back();
                }
            }
        }
        else if (cmd == "back") {
            if (dq.empty()) {
                cout << "Nothing to do in ADA\n";
            } else {
                if (!rev) {
                    cout << dq.back() << "\n";
                    dq.pop_back();
                } else {
                    cout << dq.front() << "\n";
                    dq.pop_front();
                }
            }
        }
        else if (cmd == "reverse") {
            rev = !rev;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}