Advertisement
Guest User

Stack Min O(1)

a guest
Oct 17th, 2012
664
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.88 KB | None | 0 0
  1. /**
  2.  * Stack which, in addition to push and pop,
  3.  * also has a function min which returns the minimum element.
  4.  *
  5.  * push(), pop() and min() all operate in O(1) time
  6.  *
  7.  * @author while - mydevelopedworld.wordpress.com
  8.  *
  9.  */
  10. public class StackMin {
  11.  
  12.     private Element top;
  13.     private MinElement currentMin;
  14.  
  15.     public void push(Element item){
  16.         /* Empty Stack = item is the new minimum */
  17.         if(this.currentMin == null){           
  18.             this.currentMin = new MinElement(item.getValue(), null); /* lastMin = null */
  19.             this.top = this.currentMin;
  20.             return;
  21.         }
  22.         /* Found a new minimum */
  23.         if(currentMin.getValue() > item.getValue()){ /* Item pushed < currentMin */
  24.             MinElement newMin = new MinElement(item.getValue(), this.currentMin);
  25.             newMin.setBelow(this.top);
  26.             this.currentMin = newMin;  
  27.             this.top = this.currentMin;
  28.             return;
  29.         }
  30.         /* Normal push case */
  31.         item.setBelow(this.top);
  32.         this.top = item;
  33.     }
  34.  
  35.     public Element pop(){
  36.         /* Empty Stack */
  37.         if(this.currentMin == null){
  38.             return null;
  39.         }
  40.        
  41.         Element ret = this.top;
  42.        
  43.         /* Current minimum on the top */
  44.         if(this.top == this.currentMin){ /* Pop of the currentMin */
  45.             this.currentMin = this.currentMin.getLastMin(); /* currentMin = lastMin */
  46.             this.top = this.top.getBelow();
  47.             return ret;
  48.         }                  
  49.         /* Normal pop case */
  50.         this.top = ret.getBelow();
  51.         return ret;                
  52.     }
  53.  
  54.     public Element min(){
  55.         return currentMin; /* Return null if Empty Stack */
  56.     }
  57.  
  58.     public static void main(String args[]){
  59.         StackMin stack = new StackMin();       
  60.  
  61.         stack.push(new Element(10));
  62.         stack.push(new Element(100));
  63.         stack.push(new Element(5));
  64.         stack.push(new Element(17));
  65.         stack.push(new Element(20));
  66.        
  67.         System.out.println(stack.min()); // >> 5
  68.  
  69.         stack.push(new Element(1));
  70.  
  71.         System.out.println(stack.min()); // >> 1
  72.         System.out.println(stack.pop()); // >> 1
  73.         System.out.println(stack.pop()); // >> 20
  74.         System.out.println(stack.pop()); // >> 17
  75.         System.out.println(stack.min()); // >> 5
  76.         System.out.println(stack.pop()); // >> 5
  77.         System.out.println(stack.min()); // >> 10
  78.         System.out.println(stack.pop()); // >> 100
  79.         System.out.println(stack.min()); // >> 10
  80.         System.out.println(stack.pop()); // >> 10
  81.         System.out.println(stack.pop()); // >> null
  82.         System.out.println(stack.min()); // >> null
  83.        
  84.     }
  85.  
  86.  
  87.  
  88. }
  89.  
  90. class Element{
  91.     private int value;
  92.     private Element below = null;
  93.  
  94.     public Element(int value){
  95.         this.value = value;
  96.     }
  97.  
  98.     public int getValue(){ return this.value; }
  99.     public Element getBelow(){ return this.below; }
  100.  
  101.     public void setBelow(Element e){
  102.         this.below = e;
  103.     }
  104.  
  105.     public String toString(){
  106.         return this.value+"";
  107.     }
  108. }
  109.  
  110. class MinElement extends Element{
  111.     private MinElement lastMin;
  112.  
  113.     public MinElement(int value, MinElement lastMin){
  114.         super(value);
  115.         this.lastMin = lastMin;
  116.     }
  117.  
  118.     public MinElement getLastMin(){ return this.lastMin; }
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement