A way to reverse queue using only two temporary queues and nothing more?

Question

Is there a way to reverse items' order in queue using only two temporary queues (and no other variables, such as counters)? Only standard queue operation are available: ENQUEUE(e), DEQUEUE(), EMPTY()?

Solutions in any language or pseudocode are welcome.

Answer 1

So the way to do it is to dequeue everything (except the last item) from the original queue to a temp queue, putting the last item in the final queue. Then repeat, each time copying every item except the last one from one temp queue to another, and the last one to the final queue. hmm.... is there a better way?

Answer 2

You can:

• Use the two queues to simulate a stack.
• Push all of the elements of the original queue to this stack.
• Now pop each element from the stack and add it to the original queue.

Answer 3

while(!queue.EMTPY())
{
    while(!finalQueue.EMPTY())
    {
        tempQueue.ENQUEUE(finalQueue.DEQUEUE());
    }
    finalQueue.ENQUEUE(queue.DEQUEUE());
    while(!tempQueue.EMPTY())
    {
        finalQueue.ENQUEUE(tempQueue.DEQUEUE());
    }
}

I think that should work. There is a more efficient way if you can swap the temp and final queues with each dequeue from the original queue.

Answer 4

The answer is yes. I'm tempted to leave it there because this sounds like a homework question, but I think its an interesting problem.

If you can only use those three operations, you have to use both temp queues.

Basically you have to dequeue from the main queue and put the item into temp queue A. Dequeue all items from temp queue B (empty at first) into A. Then do the same thing only reverse the order from A to B. You always enqueue into the temp queue that is empty, and then put in all the items from the other temp queue. When the queue to be reversed is empty, you can just dequeue from the non-empty temp queue and enqueue into the primary queue and you should be reversed.

I would give pseudo-code, but again, I'm worried I'm doing your homework for you.

Answer 5

// REVERSE OF QUEUE USING 1 QUEUE N OTHER DEQUEUE void reverse() { int q1[20],q2[20],f1,r1,f2,r2; while(f1!=r1) { q1[r2]=q1[f1]; r2=r2+1; f1=f1+1; } //whole elements of temporary queue is transfered to dequeue. while(r2!=f2) { q1[r1]=q2[r2]; r2=r2-1; r1=r1+1; } }

Answer 6

who can find the solution for the extended problem: reverse a queue by using only an additional queue! That is my homework! but you can use some none-array variables

Answer 7

This is kind of similar to the Tower of Hanoi puzzle :)

Here is a solution in C#:

static Queue<T> ReverseQueue<T>(Queue<T> initialQueue)
{
    Queue<T> finalQueue = new Queue<T>();
    Queue<T> intermediateQueue = new Queue<T>();

    while (initialQueue.Count > 0)
    {
        // Move all items from the initial queue to the intermediate queue, 
        // except the last, which is placed on the final queue.
        int c = initialQueue.Count - 1;
        for (int i = 0; i < c; i++)
        {
            intermediateQueue.Enqueue(initialQueue.Dequeue());
        }
        finalQueue.Enqueue(initialQueue.Dequeue());

        // Swap the 'initialQueue' and 'intermediateQueue' references.
        Queue<T> tempQueue = initialQueue;
        initialQueue = intermediateQueue;
        intermediateQueue = tempQueue;
    }

    return finalQueue;
}