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);
}


Below is the complete program with the tracing facility. Compile the program with the command given below to enable tracing
g++ -DDEBUG=1 stack_reverse.cpp

  1 #include <iostream>
  2 #include <stack>
  3 #define MAX 10
  4 
  5 //File: stack_reverse.cpp
  6 
  7 void stack_reverse(std::stack<int>&);
  8 void push_to_bottom(std::stack<int>&, int);
  9 void get_stack_elements(std::stack<int>&);
 10 void print_stack_elements(std::string const &str, std::stack<int>);
 11 
 12 int main(int argc, char *argv[])
 13 {
 14   std::stack<int> s;
 15   get_stack_elements(s);
 16   print_stack_elements("ORIGINAL STACK", s);
 17 
 18 #ifdef DEBUG
 19   std::cout << "TRACE ENABLED" << std::endl;
 20 #endif
 21 
 22   stack_reverse(s);
 23   print_stack_elements("REVERSED STACK", s);
 24   return 0;
 25 }
 26 
 27 //pop out all the elements, use function stack to store the elements
 28 void stack_reverse(std::stack<int> &s)
 29 {
 30 #ifdef DEBUG
 31   std::cout << "TRACE[stack_reverse]: Checking if given stack 's' is empty" << std::endl;
 32 #endif
 33 
 34   if(s.empty())
 35   {
 36 #ifdef DEBUG
 37   std::cout << "TRACE[stack_reverse]: All the elements of the given stack 's' have been popped, recursion terminates, return" << std::endl;
 38 #endif
 39     return;
 40   }
 41 
 42   int elem = s.top(); s.pop();
 43 #ifdef DEBUG
 44   std::cout << "TRACE[stack_reverse]: Given stack 's' is NOT EMPTY" << std::endl;
 45   std::cout << "TRACE[stack_reverse]: Element [" << elem << "] popped and stored in the function stack" << std::endl;
 46   std::cout << "TRACE[stack_reverse]: Calling stack_reverse(s)" << std::endl;
 47 #endif
 48   stack_reverse(s);
 49 
 50   //pass the element obtained during the unwinding of the function 
 51   //stack and store it at the bottom of the given stack 's'
 52 #ifdef DEBUG
 53   std::cout << "TRACE[stack_reverse]: Got element " << elem << " from function stack unwinding. Calling push_to_bottom(s, " << elem << ")" << std::endl;
 54 #endif
 55   push_to_bottom(s, elem);
 56 }
 57 
 58 void push_to_bottom(std::stack<int> &s, int elem)
 59 {
 60   //stack is empty so elem will be placed at the bottom of the stack 's'
 61 #ifdef DEBUG
 62   std::cout << "TRACE[push_to_bottom]: Pushing element " << elem << " at the bottom of the given stack 's'" << std::endl;
 63 #endif
 64   if(s.empty())
 65   {
 66 #ifdef DEBUG
 67   std::cout << "TRACE[push_to_bottom]: Given stack 's' is empty. " << elem << " moved to the bottom of the stack 's'. Return" << std::endl;
 68 #endif
 69     s.push(elem);
 70     return;
 71   }
 72 
 73   //stack is not empty, so popping out the elements, using function
 74   //stack to store the elements and storing the given element at the
 75   //bottom of the given stack 's'
 76   int top = s.top(); s.pop();
 77 #ifdef DEBUG
 78   std::cout << "TRACE[push_to_bottom]: Given stack 's' is NOT empty. " << top << " popped from the stack 's'." << std::endl;
 79   std::cout << "TRACE[push_to_bottom]: Calling push_to_bottom(s, " << elem << ")" << std::endl;
 80 #endif
 81   push_to_bottom(s, elem);
 82 
 83 #ifdef DEBUG
 84   std::cout << "TRACE[push_to_bottom]: Got element " << top << " from function stack unwinding. Pushing to the stack 's'." << std::endl;
 85 #endif
 86   s.push(top);
 87 }
 88 
 89 void get_stack_elements(std::stack<int> &s)
 90 {
 91   for(int i = 1; i < MAX; ++i)
 92   {
 93     s.push(i);
 94   }
 95 }
 96 
 97 void print_stack_elements(std::string const &str, std::stack<int> s)
 98 {
 99   std::cout << str.c_str() << std::endl;
100   for(int i = 1; i < MAX; ++i)
101   {
102     std::cout << s.top() << std::endl;
103     s.pop();
104   }
105   std::cout << std::endl;
106 }

No comments :

Post a Comment