Queue with two stacks

queue-with-two-stacks.cpp

template <typename T>
class QueueWithTwoStacks {
private:
    stack<T> S1, S2;
public:
    void enqueue(T& x) {
        S2.push(x);
    }

    T dequeue() {
        if (S1.empty()) {
            while (!S2.empty()) {
                T top = S2.top(); S2.pop();
                S1.push(top);
            }
        }

        if (S1.empty())
            throw "queue empty";
        T top = S1.top(); S1.pop();
        return top;
    }

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

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