题目描述：

给定一个队列，请用一系列合法的队列操作函数，包括：

（1） int IsEmptyQ(Queue Q)
（2） void AddQ(Queue Q, ElementType item)
（3） ElementType DeleteQ(Queue Q)

将队列中的元素从小到大排序。

注意：不能直接通过数组下标直接访问队列（数组）中的元素。可以使用一个辅助队列。排序后的结果应存放在原队列中。

算法分析：

一开始我想用一般的思路, 队列的特性就是只能从头部出(pop), 只能从尾部进入(push). 那么每次都把队列论一圈找到最小的元素然后把这个元素放到队列的尾部, N圈以后就排序好了, 但是时间复杂度不行O(N^2) 大数据会超时, 那么想想是不是有O(NlogN)的算法, O(NlogN)的算法就那么几种, merge sort, quick sort(均摊), 最后其实merge sort在这里可以实现, 需要再借助第二个queue. 实现代码如下(可以AC):

void merge_sort_queue(queue<int> &q, int n) {
    if(n <= 1) return ;

    queue<int> q_copy;
    int k = 1;
    int remain = n;
    int k1 = 1;
    int k2 = 1;
    while(k < n) {
        remain = n;
        while(remain > 0) {
            k1 = min(remain, k);
            for(int i = 0; i < k1; ++i) {
                q_copy.push(q.front());
                q.pop();
            }
            remain -= k1;
            k2 = min(remain, k);
            remain -= k2;
            while(k1 > 0 && k2 > 0) {
                if(q.front() >= q_copy.front()) {
                    q.push(q_copy.front());
                    q_copy.pop();
                    k1--;
                }
                else {
                    q.push(q.front());
                    q.pop();
                    k2--;
                }
            }
            while(k1--) { q.push(q_copy.front()); q_copy.pop(); }
            while(k2--) { q.push(q.front()); q.pop(); }
        }
        k = k * 2;
    }
    return ;
}

注意点：

只有两个test case无坑点, 只要注意大数据别超时就可以了.