Tuesday, December 20, 2011

How to reverse a stack in place ?

Reverse a stack, using just push(), pop(), top() operations, in its place itself.
You can not assign any known memory address.
Solution:
Simple methodology for this problem is, take last element from the stack i.e. you need to empty the stack [do it recursively, keeping other elements in memory].
Push the last element in the stack again.
Now while pushing each of earlier elements, first empty whole stack and then push them.
This will ultimately turn into reversed stack.
Code:
void reverse(Stack st)
{
  int m = (int)st.Pop();
  if (st.Count != 1)//checking for last element
  reverse(st);//popping out all the elements for reversing
  Push(st , m);//now the last element popped out i.e. the bottom element will be pushed to stack, which is now empty
}


void Push(Stack st , int a)
{
  int m = (int)st.Pop(); // if stack has already some elements then pop them out
  if (st.Count != 0)
    Push(st , a); // new items will be pushed to the bottom-most position.
  else
    st.Push(a); 
  st.Push(m); //now atlast push the item popped out first i.e. the last element from original stack
} 

Time complexity : O(n2)
Space complexity : O(n)

0 comments:

Post a Comment