Saturday, 18 July 2015

Find minimum in a stack


Question: Design a data structure where it supports LIFO and a function min which gives min of the elements present at the moment in that structure.

Solution: To implement LIFO we can use Stack data structure, but to maintain current minimum we can use auxiliary space, here I am implementing it using another auxiliary stack. Initialize auxiliary stack with first element pushed in the stack as it would be the minimum at present. Now whenever a new element is pushed we check whether it is less than top element in auxiliary stack?if this condition satisfies then push it to auxiliary stack too. While popping through the stack, again check whether top of auxiliary is same as popped element, then pop from auxiliary also. At any time top of auxiliary will give min of the elements present in the stack.

Following program implements above logic.
/**
 * @author vikky.agrawal
 * Min should return minimum of elements present at the moment in stack.
 * 
 */

public class StackImpl {

 Node top =null; 
 
 public static void main(String[] arg){ 
   
  //Find min implementation
  
  StackImpl stack1=new StackImpl();
  StackImpl auxiliary=new StackImpl();
  
  for (int i = 1; i < 10; i++) {
   int data=(int) (Math.random() * 100);
   stack1.push(data);
   
   if(auxiliary.top==null){
    auxiliary.push(data);
   }else{
    int temp=auxiliary.peek();
    if(temp>0 && temp>data){
     auxiliary.push(data);
    }
   }
   
  }
  System.out.println("Original stack :");
  stack1.printStack();
  
  System.out.println("Auxiliary stack : ");
  auxiliary.printStack();
  
  //System.out.println("Min element right now is :"+auxiliary.peek());
  
  for (int i = 1; i < 5; i++) {
   
   int popped=stack1.pop();
   
   System.out.println("Popped element is :"+popped);
   
   if(auxiliary.peek()== popped){
    auxiliary.pop();
   }   
            System.out.println("Next Min element right now is :"+auxiliary.peek()); 
  }
 }
  
 /**
  * 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;
      }  
 }
 
 
}