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

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;

}