Queue with min operation using deque

queue-with-min-using-deque.cpp

template <typename T>
class QueueWithMin {
private:
    queue<T> Q;
    deque<T> D;
public:
    void enqueue(T& x) {
        Q.push(x);
        while (!D.empty() && D.back() > x)
            D.pop_back();
        D.push_back(x);
    }

    T dequeue() {
        if (Q.empty())
            throw "queue empty";
        if (D.front() == Q.front())
            D.pop_front();
        T top = Q.front(); Q.pop();
        return top;
    }

    T getMin() {
        return D.front();
    }

    int size() {
        return Q.size();
    }

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