Queue with Minimum - Preparation to IOI Part 3

Queue with Minimum - Preparation to IOI Part 3

struct MinStack {
    stack<int> st;  // основной стек
    stack<int> mn;  // стек минимумов

    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;

    // добавить в конец
    void push(int x) {
        in.push(x);
    }

    // удалить из начала
    void pop() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        out.pop();
    }

    // получить минимум
    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();
    }
};