[Java] MaxStack, a Stack that tracks the maximum element in it at any given time

This exercise is about defining a data structure MaxStack which behaves exactly like a Stack but offers a method max that can return at any given time which element is the biggest in the stack.

It is fairly quick to see we can create a class that wraps the Stack and has O(N) cost for the max function and O(1) cost for push and pop.

If we use additional structures to reduce the cost of max operation, we end up using additional space O(N), for example using a MaxHeap will provide the result of max in O(1) time but increases our push and pop cost to O(log N).

We can notice however that a Stack is simply a list where we always insert and remove from the head. Additionally, at each given level (node) the maximum in the stack can only be the maximum between the node value and all elements before it.

This means we can track two pieces of information: value and max and add a bit of logic to our push so that we always know at each level what is the maximum in the stack until that point. Specifically, each new node will compare its value with the maximum of the previous node and set its local maximum to the biggest of the two.

This has the additional benefit of using O(1) extra space AND keeps our operations O(1) time too.

You can find my implementation of MaxStack on my Gist along with some tests in MaxStackJTests. I use a helper MaxStackNode structure but could just as easily have used a List of Pair instead.

The class accepts a generic type as content, however the type must implement Comparable interface. It is also possible to explicitly provide a Comparator in input in case you require a specific ordering (eg: reverse of natural ordering).

Null values are always placed last in the calculation of the maximum.