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
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
.jpg)
7 comments:
thank you so much for your explanation it really helped me
Thanks for the help, had the code and did not understand how recursion will help reversing the queue, your post made everything clear.
Maybe it's too late but you have a problem there.
if you have N elements in Q,
using a recursive method with one int variable is acutally creating N variables called "temp" each one in it's own scope.
So your solution is equall (in terms of memory) to creating an array in length of N.
RAM had given pseudocode..
here's the tested recursion code in c
void insertReverseOrder(struct Queue *Q,int data)
{
enqueue(Q,data);
return;}
void reverseQueueElem(struct Queue *Q)
{
int tmp;
if(isEmptyQueue(Q))
return;
tmp=dequeue(Q);
reverseQueueElem(Q);
insertReverseOrder(Q,tmp);
}
That's an amazing way I must say, tried this in JAVA as well, Here is the code.. Hope it helps -
import java.util.LinkedList;
import java.util.Queue;
public class ReversingQueue {
static void ReverseQueue(Queue queue) {
int temp;
if (!queue.isEmpty()) {
temp = Dequeue(queue);
ReverseQueue(queue);
Enqueue(queue, temp);
}
}
static int Dequeue(Queue queue) {
int temp = queue.poll();
return temp;
}
static void Enqueue(Queue queue, int temp) {
queue.add(temp);
return;
}
public static void main(String[] args) {
Queue queue = new LinkedList();
int limit = 8;
for (int i = 0; i <= limit; i++) {
Enqueue(queue, i);
}
System.out.println(queue);
ReverseQueue(queue);
System.out.println(queue);
}
}
Sir, please develop an algorithm for polynomial subtraction and the data structure should be doubly linked list
I wish I kwen this during my test. I spent three days wondering how to do it. It's incredible. Always look for ispiration
Post a Comment