26 Jan 2014

Stack Reversal

Problem Statement:
         In-place stack reversal using recursion.
Fig: In-place Stack Reversal
Source Code
Solution:
   Using recursion start from the bottom most element in the stack using the 1st Function Call(reverse()) , push each element to the bottom of the stack through recursion using another function call(pushToBottom()).

Below is the implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 *  Inplace reversal of Stack
 * @author Prateek
 */
public class ReverseStackRecursion {
 /**
  * Subroutine to Reverse the element of stack 
  * @param stack : input stack
  */
 public void reverseStack(Stack<Integer> stack){
  if(stack.isEmpty())
   return ;

  int val= stack.pop();
  reverseStack(stack);

  pushToBottom(stack,val);
  return ;
 }

 /**
  * Pushes the incoming element or item to the bottom of the stack 
  */
 private void pushToBottom(Stack<Integer> stack,int item){
  if(stack.isEmpty()){
   stack.push(item);
   return ;
  }

  int val= stack.pop();
  pushToBottom(stack,item);
  stack.push(val);
 }
}

Happy Coding !! :)

No comments:

Post a Comment