How do you sort a queue?

Answer 1

You don't. Queues are a first in, first out structure, specifically used to process incoming data in the same order it arrives. If you want to sort a data sequence then use an array or a list.

Answer 2

Not to be pedantic, but if you merge and sort one queue into another queue then it is no longer a queue (first in, first out). The result is a sorted list. Regardless, there are a number of ways to merge and sort.

If both queues can themselves be sorted, then you can simply sort them and then traverse both queues simultaneously, extracting the smaller node of the two and inserting it into a new list. Continue in this fashion until both queues are empty.

If the queues cannot be sorted individually, create a temporary one-dimensional array of pointers to the data type, with enough elements to accommodate all nodes from both queues. Then traverse each queue and sequentially update the array with the data pointers. Then sort the array (do not compare pointers, compare what they point at, via indirection). Once the array is sorted, you can instantiate a new list and sequentially copy data indirectly from the array pointers. Note that both queues must remain constant during this entire process. Once the new, sorted list is built, you can delete the temporary array (but do not delete the pointers in the array).

Alternatively, if you have a list that can itself be sorted, you can forego using an array and simply copy data from the queues directly into the list, and then sort the list.

Answer 3

Data Mining in C++