Saturday 18 July 2015

Reverse a stack

Given a stack, following program recursively reverses it:
/**
 * @author vikky.agrawal
 * Stack reversal
 */

public class StackImpl {

 Node top =null; 
 
 public static void main(String[] arg){ 
  
  StackImpl stack=new StackImpl();
  stack.stackOperations();
 }
 
 
 public void stackOperations(){
  

  for (int i = 1; i < 10; i++) {
   push((int) (Math.random() * 100));
  }
  
  printStack();
  
  top=this.reverseStack(top);
  System.out.println("Stack after reverse");
  printStack();
  
  
 }
 
 
 
 public Node reverseStack(Node tos){
  
  
  ///base case
  if(tos==null || tos.getLink()==null){
   return tos;
  }  
  
  //point temp to last node and then set link recursively.
  Node temp=reverseStack(tos.getLink());
  
  tos.getLink().setLink(tos);  //a->b->c->null,set b's backward link a<-b<-c;  
                                             // and set b's forward link as null
  tos.setLink(null);
  
  return temp; //always last node, hence top of reversed Stack
 }

 
 /**
  * Helper functions for stack operations
  */
 
 public void push(int data){
  if(top==null){
   top=new Node(data);
  }else{
   Node temp=new Node(data);
   temp.setLink(top);
   top=temp;
  }
 }
 
 public int pop(){
  if(top==null){
   return -1;
  }else{
   Node temp=top;
   top=top.getLink();
   return temp.getData();
  }
 }
 
 public int peek(){
  if(top!=null){
   return top.getData();
  }else{
   return -1;
  }
 }
 
 
 public boolean isEmpty(){
  if(top==null)
   return true;
  return false;
 }
 
 
 public int size(){
  int size=0;
  Node temp=top;
  
  while(temp!=null){
   size++;
   temp=temp.getLink();
  }
  return size;
 }
 
 public void printStack(){
  Node temp=top;
  System.out.print("Top->\n");
  while(temp!=null){
   System.out.println(temp.getData()+"\n|");
   temp=temp.getLink();
  }
  System.out.println("/null");
 }
 
 /**
  * static inner class to be used for Stack Data Structure
  */
  static class Node{
   private int data;
   private Node link;    
      
      Node(){
            
      }
      
      Node(int data){
       //mergedList=new Node();
          this.setData(data);
          this.setLink(null);       
      }
      
      public int getData(){
          return this.data;
      }
        
      public Node getLink(){
          return this.link;
      }
      
      public void setData(int data){
          this.data=data;
      }       
      
      public void setLink(Node link){
          this.link=link;
      }  
 }
 
}

No comments:

Post a Comment