queue with clown sort

#include <bits/stdc++.h>

using namespace std;

namespace my_namespace {

    class queue_empty_exception : public exception {
    public:
        char *what() const throw() {
            return "Error: Queue is empty!";
        }
    };

    template<typename T>
    struct queue {

        queue() : queue_size(0) {}

        ~queue() {
            clear();
        }

        void clear() {
            for (node *it = begin; it != nullptr; begin = it) {
                it = begin->next;
                delete begin;
            }
            queue_size = 0;
        }

        void push(T value) {
            if (!queue_size) {
                end = new node(value);
                begin = end;
            } else {
                end->next = new node(value);
                end = end->next;
            }
            ++queue_size;
        }

        void pop() {
            if (!queue_size) {
                throw queue_empty_exception();
            }
            --queue_size;
            node *next = begin->next;
            delete begin;
            begin = next;
        }

        T front() {
            if (!queue_size) {
                throw queue_empty_exception();
            }
            return begin->value;
        }

        bool empty() {
            return queue_size <= 0;
        }

        size_t size() {
            return queue_size;
        }

    private:

        struct node {
            T value;
            node *next;

            node(T value, node *next = nullptr) : value(value), next(next) {}
        };

        size_t queue_size;
        node *begin = nullptr;
        node *end = nullptr;

    };

    template<typename T>
    void shift_queue(size_t count, queue<T> &q) {
        for (size_t i = 0; i < count; ++i) {
            q.push(q.front());
            q.pop();
        }
    }


    template<typename T>
    ostream &operator<<(ostream &os, queue<T> &q) {
        for (size_t i = 0; i < q.size(); ++i) {
            os << q.front() << ' ';
            q.push(q.front());
            q.pop();
        }
        return os;
    }

    void sort(size_t l, size_t r, queue<int> &q) {
        size_t size = q.size(), mid_index = (r + l) / 2;
        shift_queue(mid_index, q);
        queue<int> less_q, equal_q, greater_q;
        int mid_value = q.front();
        equal_q.push(mid_value);
        q.pop();
        for (size_t i = 0; i < r - mid_index - 1; ++i) {
            if (q.front() > mid_value)
                greater_q.push(q.front());
            else if (q.front() < mid_value)
                less_q.push(q.front());
            else
                equal_q.push(q.front());
            q.pop();
        }
        shift_queue(size - r + l, q);
        for (size_t i = 0; i < mid_index - l; ++i) {
            if (q.front() > mid_value)
                greater_q.push(q.front());
            else if (q.front() < mid_value)
                less_q.push(q.front());
            else
                equal_q.push(q.front());
            q.pop();
        }
        shift_queue(size - r + l, q);
        size_t l_size = less_q.size(), g_size = greater_q.size();
        for (; !less_q.empty();) {
            q.push(less_q.front());
            less_q.pop();
        }
        for (; !equal_q.empty();) {
            q.push(equal_q.front());
            equal_q.pop();
        }
        for (; !greater_q.empty();) {
            q.push(greater_q.front());
            greater_q.pop();
        }
        shift_queue(size - r, q);
        if (g_size > 1)
            sort(r - g_size, r, q);
        if (l_size > 1)
            sort(l, l + l_size, q);
    }
}

int main() {
    my_namespace::queue<int> q;
    while (true) {
        int a;
        cin >> a;
        if (a == -1)
            break;
        else if (a == 1) {
            int b;
            cin >> b;
            q.push(b);
        } else if (a == 2) {
            try {
                q.pop();
            } catch (exception& e) {
                cout << e.what() << endl;
            }
        } else if (a == 3) {
            try {
                cout << q.front() << endl;
            } catch (my_namespace::queue_empty_exception& e) {
                cout << e.what() << endl;
            }
        } else if (a == 4) {
            q.clear();
        } else if (a == 5) {
            cout << q << endl;
            my_namespace::sort(0, q.size(), q);
            cout << q << endl;
        } else if (a == 6) {
            int b;
            cin >> b;
            for (int i = 0; i < b; ++i) {
                q.push(rand() % 1000);
            }
        }
    }
}