8.2

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 0(1) space and O(n) running time. public String max() {...} Enter your answer here Q8.2 Update push() and pop() 5 Points Write a method max() using O(n) space and O(1) run time. You may update the push and pop methods as needed. public void push {...} public String pop() {...} public String max() {...}