Question 3. Minimum Value Stack

You are designing a new class MinStack that specializes the java.util.Stack class to Comparable objects and provides a new method min() that will return the minimum value on the stack in O(1) time. In order to provide this functionality you will have to define some new private instance variables, provide a constructor for MinStack (with no parameters), override methods push(e) and pop(), and implement the method min().  All three of these operations must run in O(1) time. Note that the new class uses generics and should work on any subclass of Comparable.

(Please note that the interface for push(e) is public E push(E element). This is different from the push ADT defined by the book and in my slides, which does not return anything (i.e., public void push(E element)). I am following here the Stack class provided by java.util. Here, push returns the element just pushed onto the stack, i.e., element in push(E element). Please follow this convention.)

Here is a test program testMinStack that provides a test case. You should, however, test your program using a broader range of test cases. Pay particular attention to boundary conditions.

MinStack and testMinStack are both part of the package A1Q3, and should be downloaded to a directory of the same name. You need only submit MinStack.java.