Q8 Max Stack- 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 (8.1) or updating push and pop methods to track max as the stack is changed in 8.2.

8.1- Implement the method max(). Write a method max() using O(1) space and O(n) running time.

public String max() (...)

8.2- Update the push and Pop. Write a method max() using O(n) space and O(1) run time. You may update the push and pop method as need.

public void push() (...)

public String pop() (..)

public String max() (...)