Queue with min operation

queue-with-min.cpp

template <typename T>
class QueueWithMin {
private:
    stack< pair<T, T> > S1, S2;
public:
    void enqueue(T& x) {
        S2.push(pair<T, T>(x, S2.empty() ? x : min(x, S2.top().second)));
    }

    T dequeue() {
        if (S1.empty()) {
            while (!S2.empty()) {
                pair<T, T> top = S2.top(); S2.pop();
                top.second = S1.empty() ? top.first : min(top.first, S1.top().second);
                S1.push(top);
            }
        }

        if (S1.empty())
            throw "empty queue";
        pair<T, T> top = S1.top(); S1.pop();
        return top.first;
    }

    T getMin() {
        if (empty())
            throw "empty queue";
        return S1.empty() ? S2.top().second : (S2.empty() ? S1.top().second : min(S1.top().second, S2.top().second));
    }

    bool empty() {
        return S1.empty() && S2.empty();
    }

    int size() {
        return S1.size() + S2.size();
    }
};