Consider the following partial implementation of a generic LIFO $$MyStack$$

data structure that contains subtypes of Comparable and supports the operations

isEmpty$(),$ push$(),$ pop$()$ and returnMin$().$ Note that the latter merely returns the

minimum element stored in the MyStack but doesn$$t delete it$.$ We will assume that

MyStack always contains distinct elements.

The MyStack is expandable in the sense that the client code may push an arbitrary

number of elements to it$.$ Except for deleteMin$(),$ all operations must have worst$-$case

running time O$(1).$ We will assume compareTo$()$ has worst$-$case running time O$(1).$

The following is a partial implementation of MyStack, with method stubs:

public class MyStack$>\{$

private class Node $\{$

public Node next;

public T obj;

public Node$($ Node next, T obj$)\{$

this.next $=$ next;

this.obj $=$ obj;

$\}$

$\}$

public boolean isEmpty$()\{//$ Must be O$(1)$

return false;

$\}$

public void push$($T obj$)\{//$ Must be O$(1)$

$\}$

public T pop$()\{//$ Must be O$(1)$

return null;

$\}$

public T returnMin$()\{//$ Must be O$(1)$

return null;

$\}$

public void deleteMin$()\{$

$//$ DO NOT IMPLEMENT THIS METHOD!

$\}$

$\}$

$($a$)$ Provide a valid Java implementation of MyStack that achieves the run$-$

ning time requirements listed above. However, DO NOT implement deleteMin$()$

and DO NOT add code that explicitly checks for or filters out duplicate objects $($we

will assume the client code never attempts to add a duplicate element$).$

You must use the given starter code. Don$$t use any built$-$in classes beyond what is

referenced in the starter code. All MyStack methods must be implementations of

deterministic, sequential, and comparison$-$based algorithms. The latter requirement

means that the methods must only call compareTo$()$ on the contained elements.

Full credit will be given to code that is self$-$documenting and formatted in a con$-$

sistent manner.

There is no $$Put your answer here$$ box for this part. Please put your code in

a corresponding MyStack.JAVA file and include it with your submission.

$($b$)$ Assume all MyStack methods, including deleteMin$(),$ are correct im$-$

plementations of deterministic, sequential, and comparison$-$based algorithms. Is it

possible to implement all of them, including deleteMin$(),$ to have worst$-$case run$-$

ning time O$(1)?$ Justify your answer. DO NOT implement or discuss any particular

$($potential$)$ implementation of deleteMin$().$

Hint: Full credit will not be given to solutions that discuss details of a particular

implementation of deleteMin$().$