Queue with Minimum - Course 3

Queue with Minimum - Course 3

struct MinStack {
    stack<int> st;  // main stack
    stack<int> mn;  // stack of minimums

    void push(int x) {
        st.push(x);
        if (mn.empty()) {
            mn.push(x);
        } else {
            mn.push(min(x, mn.top()));
        }
    }

    void pop() {
        st.pop();
        mn.pop();
    }

    int top() {
        return st.top();
    }

    int get_min() {
        return mn.top();
    }

    bool empty() {
        return st.empty();
    }
};

struct MinQueue {
    MinStack in, out;

    // add to the end
    void push(int x) {
        in.push(x);
    }

    // remove from the beginning
    void pop() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        out.pop();
    }

    // get the minimum
    int get_min() {
        if (in.empty()) {
            return out.get_min();
        }
        if (out.empty()) {
            return in.get_min();
        }
        return min(in.get_min(), out.get_min());
    }

    bool empty() {
        return in.empty() && out.empty();
    }
};