C++ Insertion sort on a queue

Question

I am trying to implement 'Insertion Sort' on two queues without using an array.

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

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

After the sorting they are as following :

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

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

They get sorted. But I sort the queue like if it was a list. I do not know how to deal with a FIFO structure.

My teacher said that my implementation is alright if it was for a list, but not for queue. I am supposed to use the push() and pop() functions (already implemented them) and a third queue for assistance. This is my current implementation of the sorting algorithm:

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 and setElemAt are additional functions I've written separately. How should I approach the problem of sorting with an additional queue?

Answer 1

@interjay the queues need to be sorted individualy , with the use of a 3rd assisting queue which is used when queue1 or queue2 is sorted. The queues must not be sorted at the same time because this will require 2 assisting queues