Queue via Stacks

3.4 Queue via Stacks: Implement a MyQueue class which implements a queue using two stacks.

• The idea is that stack.top() pushed back into another stack consequtively reverses the stack, so it can effectively become a queue.

template <class T>
class MyQueue {
public:
    MyQueue() {
    }

    void enqueue(T thing) {
        s1.push(thing);
    }

    T front() {
        if (empty()) return INT_MAX;
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }

        return s2.top();
    }

    void dequeue() {
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        if (s2.empty()) return;
        s2.pop();
    }

    bool empty() {
        return s2.empty() && s1.empty();
    }

private:
    stack<T> s1, s2;
};

int main() {
    MyQueue<int> q;
    cout << "enqueueing..." << endl;
    for (int i = 0; i < 100; i++) {
        q.enqueue(i);
        cout << i << " ";
    }
    cout << endl;

    cout << "dequeueing..." << endl;
    while (!q.empty()) {
        cout << q.front() << " ";
        q.dequeue();
        //pause();
    }

    pause();

    cout << "enqueueing..." << endl;
    for (int i = 0; i < 10; i++) {
        q.enqueue(i);
        cout << i << " ";
    }
    cout << endl;

    q.dequeue();
    q.dequeue();
    q.dequeue();

    cout << "dequeueing..." << endl;
    while (!q.empty()) {
        cout << q.front() << " ";
        q.dequeue();
        pause();
    }

}