Reversing a queue without using any external datastructures

One thing that I learned today was the immense power of Recursion. Here is the problem definition.

Given a Queue and its basic operations Enqueue(item),Dequeue( ) and a method IsQEmpty( ) (Returns True if Empty else False). By using only these methods we need to reverse the given queue. No other data structure can be used.

Thought about the solution for a long time, but in vain. Struck my mind only when Mr.Suresh Lokhande revealed the secret. This can be achieved in 4 lines using the technique of recursion.

Find below the algorithm of the Recursive method for reversing a Queue.

Queue Q; (Globally declared)

void ReverseQueue( )
{
   Line 1:  if(!IsQEmpty( ))
    {
     Line 2:   int temp = Dequeue( );
     Line 3:   ReverseQueue( );
     Line 4:   Enqueue(temp);
     }
 }

main( )
{
   ReverseQueue( );
}

We will try to do a code trace taking a small queue
Consider Q has elements 1--2--3
ReverseQueue( ) is called.
Line 1: Queue is not empty, goes inside the if loop
Line 2: Dequeue( ), local variable temp = 1. Queue now contains 2--3
Line 3: ReverseQueue( ) is called. The entire activation record of this function call is pushed onto stack 
           internally
           Line 1 : Queue is not empty, goes inside the if loop
           Line 2 : Dequeue( ), local variable temp = 2. (Since temp is declared locally, this temp is different  
                        from  the temp in the previous method call). Queue now contains 3
           Line 3 : ReverseQueue is called
                       Line 1 : Queue is not empty, goes inside the if loop
                       Line 2 : Dequeue( ), local variable temp = 3.Queue is now empty.
                       Line 3 : ReverseQueue is called.
                                   Line 1 : Queue is empty. The call is returned.
                       Line 4 : Enqueue(temp), which is 3 is inserted into the Queue. Now the queue contains 3.
                                   The function call is returned.
           Line 4: Enqueue(temp), which is 2 is inserted into the Queue. Now the queue contains 3--2.                                       The function call is returned.
Line 4 : Enqueue(temp), which is 1 is inserted into the Queue. Now the queue contains 3--2--1.

Done!!!

The queue is reversed. Here instead of using a stack externally we are making use of the internal stack.

Hope what I have understood is correct, if there is any mistake please let me know. I think this is only one of the ways in which this can be done. There might be other alternatives.

Happy recursion,


Ram





                       
                       

Entering the world of Recursion

While dealing with the applications of the data structure Stack, Recursion which is one of its important applications came into the picture.  Even though I have been doing coding for some time now (in small scale) I have never been able to grab my complete control over recursion. I think my brain is not designed to think recursive logic. Still I have decided that I will try to gain some experience in the art of recursion by going through some of the famous recursion problems and its solutions. Special thanks to Mr. Suresh Lokhande who gave great insight into this topic.

If you do a simple Google search on recursion, you will find lots and lots of materials by which you can master the art. Here are a few links which I have decided to read and understand recursion.

http://www.devshed.com/c/a/Practices/Solving-Problems-with-Recursion/ 

http://www.animatedrecursion.com/home

http://introcs.cs.princeton.edu/java/23recursion/

http://erwnerve.tripod.com/prog/recursion/recintro.htm 

Will try to go step by step and learn the concepts clearly. Until next post.

Ram