Question 3.  Maximum Value Stack

You are designing a new class MaxStack that specializes the java.util.Stack class to Comparable objects and provides a new method max() that will return the maximum 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 MaxStack (with no parameters), override methods push(e) and pop(), and implement the method max().  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 the slides, which does not return anything (i.e., public void push(E element)).  We are 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 testMaxStack that provides a test case. You should, however, test your program using a broader range of test cases. Pay particular attention to boundary conditions.

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