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

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 2

// 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 3

I realize this thread is long dead, but I believe I found a pretty good solution that meets all the requirements.

You'll only need one temp queue. What you do is as long as the original queue isn't empty, you move the last node in the queue to the front by setting a pointer to the last node and dequing and re-enquing the nodes into the original queue. Then you deqeueue from the original queue and enqueue into the temp queue. After, you just copy the temp back to the original queue.

Here's my solution in C, ADT style: (At least I don't have to worry about doing your homework for you)

QUEUE *reverseQueue (QUEUE *queue) {

QUEUE *temp;
QUEUE_NODE *pLast;
void *dataPtr;

//Check for empty queue
if(emptyQueue(queue))
    return NULL;

//Check for single node queue
if(queueCount(queue) == 1)
    return queue;

temp = createQueue();   
while(!emptyQueue(queue))
{   
    pLast = queue->rear;
    //Move last node to front of queue
    while(queue->front != pLast)
    {
        dequeue(queue, &dataPtr);
        enqueue(queue, dataPtr);
    }
    //Place last node in temp queue
    dequeue(queue, &dataPtr);
    enqueue(temp, dataPtr);

}
//Copy temp queue back to original queue
while(!emptyQueue(temp))
{
    dequeue(temp, &dataPtr);
    enqueue(queue, dataPtr);
}
destroyQueue(temp);
return queue;

}

Answer 4

To reverse a string from queue that is queue content we need two more queues in first queue dequeue all elements except last one and enqueue them in 2nd queue. Now enqueue last element in 3rd queue which is resulting queue.Do the transactions from 2nd to 1st queue and enqueue last element in 3rd stack. Repeats this untill both stack empty.

Answer 5

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;
}

Answer 6

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 7

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 8

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.