C++ 队列插入排序

Question

我正在尝试在不使用数组的情况下在两个队列上实现 'Insertion Sort'。

Queue 1 - 4, 5, 11, 8, 3

Queue 2 - 2, 3, 4, 5, 2, 11

排序后如下:

Queue 1 - 3, 4, 5, 8, 11

Queue 2 - 2, 2, 3, 4, 5, 11

他们得到排序。但是我对队列进行排序，就像它是一个列表一样。我不知道如何处理FIFO结构。

我的老师说我的实现如果是列表就可以，但队列就不行。我应该使用 push() 和 pop() 函数（已经实现）和第三个队列来寻求帮助。这是我当前的排序算法实现：

void InsertionSort(queue* &left, queue* &right)
{
    int x, i = 0, j;
    queue *p = left;
    while (p)
    {
        x = getElemAt(i, left, right);
        j = i - 1;
        while (j >= 0 && x < getElemAt(j, left, right))
        {
            setElemAt(j + 1, getElemAt(j, left, right), left, right);
            j--;
        }
        setElemAt(j + 1, x, left, right);
        p = p->next;
        i++;
   }
}

getElemAt 和 setElemAt 是我单独编写的附加函数。我应该如何解决使用附加队列进行排序的问题？

Answer 1

@interjay 队列需要单独排序，使用第三个辅助队列，在排序 queue1 或 queue2 时使用。队列不能同时排序，因为这将需要2个辅助队列

C++ 队列插入排序

C++ Insertion sort on a queue

c++

sorting

queue

implementation

insertion