Feb 10, 2012

Reverse a stack in place

Write a C/C++ Program to reverse a stack in place?

You can only use the following ADT functions on the stack:
1. empty()
2. push()
3. pop()
4. top()

Solution:
1. Whenever in place conversion is required, use recursion which will make use of function stack to store the variables
2. Pop out all the elements from the given stack recursively and store them in a variable.
3. As the stack unwinding happens, push the variable obtained at each unwinding step to the bottom of the stack. Refer method push_to_bottom below

//pop out all the elements, use function stack to store the elements
void stack_reverse(std::stack<int> &s)
{
  if(s.empty())
  {
    return;
  }
  int elem = s.top(); s.pop();
  stack_reverse(s);

  //pass the element obtained during the unwinding of the function 
  //stack and store it at the bottom of the given stack 's'
  push_to_bottom(s, elem);
}

void push_to_bottom(std::stack<int> &s, int elem)
{
  //stack is empty so elem will be placed at the bottom of the stack 's'
  if(s.empty())
  {
    s.push(elem);
    return;
  }

  //stack is not empty, so popping out the elements, using function
  //stack to store the elements and storing the given element at the
  //bottom of the given stack 's'
  int top = s.top(); s.pop();
  push_to_bottom(s, elem);
  s.push(top);
}


Read more ...