Q8 Max Stack

10 Points

Suppose that you are asked to modify the Stack class to add a new operation max() that returns the current maximum of the stack comparable objects. Assume that pop and push operations are currently implemented using array a as follows, where item is a String and n is the size of the stack.

Note: if x and y are objects of the same type, use x.compareTo(y) to compare the objects x and y.

public void push ( String item ) { a[n++] = item; } public String pop () { return a[--n]; }

Implement the max operation in two ways, by writing a new method using array a (in 8.1), or updating push and pop methods to track max as the stack is changed (in 8.2).

Q8.1 Implement method max()

5 Points

Write a method max() using O(1) space and O(n) running time.

public String max() {...}