title: C++ Insertion sort on a queue
body: <p>I am trying to implement 'Insertion Sort' on two queues without using an array.</p>
  <blockquote>
  <p>Queue 1 - 4, 5, 11, 8, 3</p>
  <p>Queue 2 - 2, 3, 4, 5, 2, 11</p>
  </blockquote>
  <p>After the sorting they are as following :</p>
  <blockquote>
  <p>Queue 1 - 3, 4, 5, 8, 11</p>
  <p>Queue 2 - 2, 2, 3, 4, 5, 11</p>
  </blockquote>
  <p>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.</p>
  <p>My teacher said that my implementation is alright if it was for a list, but not for queue. I am supposed to use the <code>push()</code> and <code>pop()</code> functions (already implemented them) and a third queue for assistance. This is my current implementation of the sorting algorithm:</p>
  <pre><code>void InsertionSort(queue* &amp;left, queue* &amp;right)
  {
      int x, i = 0, j;
      queue *p = left;
      while (p)
      {
          x = getElemAt(i, left, right);
          j = i - 1;
          while (j &gt;= 0 &amp;&amp; x &lt; getElemAt(j, left, right))
          {
              setElemAt(j + 1, getElemAt(j, left, right), left, right);
              j--;
          }
          setElemAt(j + 1, x, left, right);
          p = p-&gt;next;
          i++;
     }
  }
  </code></pre>
  <p><code>getElemAt</code> and <code>setElemAt</code> are additional functions I've written separately. How should I approach the problem of sorting with an additional queue?</p>