Friday, July 3, 2015

Implementation of a stack in java which, in addition to push and pop, also has a function min which returns the minimum element. Push, pop and min should all operate in O(1) time


import java.util.Stack;

public class StackWithMin extends Stack{
                private static final long serialVersionUID = 1L;
                Stack s;
               
                StackWithMin(){
                                s=new Stack();
                }
               
 public   void push(int n) {
                                if(n<=min()) {
                                                s.push(n);
                                }
                                super.push(n);
                }
               
                public Integer pop() {
                                int value=super.pop();
                                if(value==s.peek()) {
                                                s.pop();
                                }
                                return value;
                }
               
                int min() {
                                if(s.isEmpty()) {
                                                return Integer.MAX_VALUE;
                                }else {
                                return   s.peek();
                                }
                }

                public static void main(String[] args) throws IOException {
                                // Test harness
                                int[] arr= {1,0,2,7,-2,8,12,5,3};
                                StackWithMin stck=new StackWithMin();
                                for(int i=0;i<arr.length;i++){
                                                stck.push(arr[i]);                             
                                }
                                System.out.println("min element: "+stck.min());
                                System.out.println("Now popping the element one by one from stack and find minimum element on the stack as below: ");
                               
                                while(!stck.isEmpty()) {
                                                System.out.print("popped elemnet: "+stck.pop());
                                                if(!stck.isEmpty()) {
                                                    System.out.println(" now min element on the stack is: "+stck.min());
                                                }else {
                                                                System.out.println(" Now Stack is empty");
                                                }
                                }
                }
               
               
               


}

No comments:

Post a Comment