Dynamic shrinking. With the array implementations of stack and queue, we doubled the size of the array when it wasn’t big enough to store the next element. If we perform a number of doubling operations, and then delete a lot of elements, we might end up with an array that is much bigger than necessary. Implement the following strategy: whenever the array is 1/4 full or less, shrink it to half the size. Explain why we don’t shrink it to half the size when it is 1/2 full or less.

Stack + max. Create a data structure that efficiently supports the stack operations (pop and push) and also return the maximum element. Assume the elements are integers or reals so that you can compare them.