Design a stack that supports getMin() in O(1) time with extra space  
 Original problem statement from geeksforgeeks.org  
 This is the generic implementation of this stack data structure.  
 package com.raj.ds.stack;  
 import java.util.Comparator;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  */  
 public interface IStack <T>{  
  /**  
  * <p>This method will be used to push the element onto stack.<p>  
  *  
  * @param t  
  */  
  public void push(T t);  
  /**  
  * <p>This method will be used to get and remove the top element from stack.<p>  
  * @return  
  */  
  public T pop();  
  /**  
  * It will return the current size of the stack.<p>  
  * @return  
  */  
  public int size();  
  /**  
  * @return  
  * <p> returns <code>true</code> if stack reached its capacity else <code>false</code>.<p>  
  */  
  public boolean isFull();  
  /**  
  *  
  * @return  
  * returns <code>true</code> if stack empty else <code>false</code>.<p>  
  */  
  public boolean isEmpty();  
  /**  
  * <p>It will return minimum element at current position of the stack.<p>  
  * @return  
  *  
  */  
  public T minElement();  
  /**  
  *  
  * @return  
  * <p>It will return user defined {@link Comparator}<p>  
  */  
  Comparator<? super T> comparator();  
 }  
 #################################################################################  
 package com.raj.ds.stack;  
 import java.util.Comparator;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  *<p>Question: Design a Data Structure SpecialStack that supports all the stack operations<p>   
  *<p>like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should <p>  
  *<p>return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1).<p>  
  *<p> To implement SpecialStack, you should only use standard Stack data structure and no other data<p>  
  *  
  *  
  */  
 public class MinStack<T> implements IStack<T>{  
  /**This Object array will be used to store elements for stack data structure **/  
  private Object stack[];  
  /**This Object array will be used to store minimum elements for stack data structure **/  
  private Object minStack[];  
  /** Capacity will be used to define the maximum size of stack**/  
  private int capacity;  
  /** Index will be used to store the element in Object array.**/  
  private int index;  
  /** DEFAULT_CAPACITY is the maximum default capacity of stack**/   
  private final static int DEFAULT_CAPACITY=10;  
  /**   
  * <p>{@linkplain Comparator} Will be used to compare the current minimum element with new element for user define class.<p>  
  * <p>User defined class must implement {@linkplain Comparator} interface.<p>  
  * **/  
  private final Comparator<? super T> comparator;  
  /**  
  * <p>This Constructor can be used for all wrapper classes with default {@link MinStack#capacity}<p>  
  */  
  public MinStack() {  
  this.capacity = DEFAULT_CAPACITY;  
  this.comparator = null;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /**  
  * <p>This Constructor can be used for all wrapper classes with user defined {@link MinStack#capacity}<p>  
  * @param capacity  
  */  
  public MinStack( int capacity) {  
  this.capacity = capacity;  
  this.comparator = null;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /**  
  *<p>This Constructor can be used for all user defined classes and comparator with default {@link MinStack#capacity}<p>  
  * @param comparator  
  */  
  public MinStack(Comparator<? super T> comparator) {  
  this.capacity = DEFAULT_CAPACITY;  
  this.comparator = comparator;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /**  
  * <p>This Constructor can be used for all user defined classes and comparator with user defined {@link MinStack#capacity}<p>  
  * @param comparator  
  * @param capacity  
  */  
  public MinStack(Comparator<? super T> comparator, int capacity) {  
  this.capacity = capacity;  
  this.comparator = comparator;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#push(java.lang.Object)  
  */  
  @SuppressWarnings("unchecked")  
  @Override  
  public void push(T t) {  
  if(this.isFull()){  
   throw new RuntimeException("Stack is over flow.");  
  }  
  if(this.isEmpty()){  
   minStack[index] = t;  
  }else if(null != comparator && 0<=comparator.compare((T)minStack[index-1],t)){  
   minStack[index]=t;  
  }else if(0<=((Comparable< ? super T>)minStack[index-1]).compareTo(t)){  
   minStack[index]=t;  
  }else{  
   minStack[index]=minStack[index-1];  
  }  
  stack[index++] = t;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#pop()  
  */  
  @Override  
  public T pop() {  
  @SuppressWarnings("unchecked")  
  T t = (T)stack[--index];  
  stack[index] = null;  
  minStack[index]= null;  
  return t;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#size()  
  */  
  @Override  
  public int size() {  
  return index;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#isFull()  
  */  
  @Override  
  public boolean isFull() {  
  return this.capacity==index;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#isEmpty()  
  */  
  @Override  
  public boolean isEmpty() {  
  return 0==index;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#minElement()  
  */  
  @SuppressWarnings("unchecked")  
  @Override  
  public T minElement() {  
  return (T)minStack[index-1];  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#comparator()  
  */  
  @Override  
  public Comparator<? super T> comparator() {  
  return comparator;  
  }  
 }  
 #################################################################################  
 package com.raj.ds.stack;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  */  
 public class User {  
  public int id ;  
  public User(int id) {  
  this.id=id;  
  }  
  /* (non-Javadoc)  
  * @see java.lang.Object#toString()  
  */  
  @Override  
  public String toString() {  
  return "id = "+id;  
  }  
 }  
 #################################################################################  
 package com.raj.ds.stack;  
 import java.util.Comparator;  
 public class Main {  
  public static void main(String[] args) {  
  MinStack<String> minStack = new MinStack<>(3);  
  minStack.push("A");  
  minStack.push("C");  
  minStack.push("B");  
  minStack.pop();  
  MinStack<User> userDefinedClassMinStack = new MinStack<>(new Comparator<User>() {  
   @Override  
   public int compare(User o1, User o2) {  
   return o1.id > o2.id ? 1: o1.id == o2.id ? 0 : -1;  
   }  
  });  
  User t = new User(1);  
  User t1 = new User(2);  
  User t3 = new User(3);  
  userDefinedClassMinStack.push(t);  
  userDefinedClassMinStack.push(t1);  
  userDefinedClassMinStack.push(t3);  
  userDefinedClassMinStack.pop();  
  }  
 }