Home > Applied Algorithms, Recursion, Stack > Reverse a stack without using any other data structures. (in-place)

Reverse a stack without using any other data structures. (in-place)

This was a question that was asked to one of my friends in Microsoft’s IDC interview. No other data structures, eh? And I am pretty sure that  I would need all the values to reverse the stack. So there is only one way to this. Solve the problem using recursion!

But how? How do you utilize recursion to do this? Here is how you should proceed. Recurse down to the second last element in the stack and call a function with the stack as it is right now (with only 1 element) and the current element (the second last one). Now go on to pop an element. Then you should do one of the two things. If the size is not equal to zero, call this function again with the element you received from the function (2nd last). If the size is zero, just push the element you received from the call onto the stack.

So you are basically inserting each element in reverse order utilizing 2 functions. Here is a small pseudo-code:

void reverse(Stack s) //called at the start
{
int num = (int)s.Pop();
if (s.Count != 1)
reverse(s);
Push(s , num);
}
void Push(Stack s , int a)
{
int num = (int)s.Pop();
if (s.Count != 0)
Push(s , a);
else
s.Push(a);
s.Push(num);
}

You got it, right? If not, try running this for a basic input stack with values 1,2,3,4,5 (bottom -> top). You’ll certainly get it then. 🙂

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: