To do inplace stack reversal u need a mechanism by which u can transfer the
first node to last of the stack making sure u have count of other nodes
here
Say u have stack
5<- top
4
3
2
1
The answer should generate the stack as
1-<top
2
3
4
5
This give hints to recursion . A normal recursive func willlook like
InplaceReverse(stack<int>&s){
if(s.empty()) return;
temp=s.top();
s.pop();
InplaceReverse(s);
}
Now if one had to print the stack nodes from bottom to top this would have
helped as we get to bottom of stack.But we need a storing mechanism so may
be one more recursive function can help so that we can pop the nodes first
and then insert the top node
Say the stack at a pt of time is
1<-top
2
Then to insert 3 at bottom we shud have some mechanism which can store
values 1 and 2
So u pop 1 and pop 2 ..Insert 2 and then Insert 1
1<- top
2
3
Only way to achieve this without using extra space is another recursion .So
I write a helper func which can help me here to achieve this. I call this
helper Func as something like ReverseHelper and push the temp variable to it
.
So
InplaceReverse(stack<int>&s){
if(s.empty()) return;
temp=s.top();
s.pop();
InplaceReverse(s);
ReverseHelper(s,temp);
}
ReverseHelper(stack<int>&s,int val){
if(s.empty()) {
s. push(val);
return;
}
temp = s.pop();
ReverseHelper(s,val);
s.push(temp);
}
Remember to pass stack as reference
Regards
Ankur
}
On Fri, Oct 7, 2011 at 7:54 PM, sravanreddy001 <[email protected]>wrote:
> in place means:
>
> use constant extra space
>
> in simple terms O(1) space
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/nDVS4k7fF34J.
>
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
