A stack is an abstract data type that has a "last$-$in$,$ first$-$out" structure for data or objects. Your goal is to implement a generic stack data structure. This means you have control over the type of objects stored on the stack.

Begin by creating a Stack class with the declaration public class Stack $\{\}.$ This will allow you to make arrays of generic objects. The Stack class should have the following methods:

public Stack$()$ The default constructor that should set the maximum size of the Stack to be $5.$

public Stack$($int size$)$ This constructor initializes the maximum size to be the size that is passed in$.$

public T pop$()$ throws StackException $$ This removes and returns the object at the top of the stack, and throws StackException if it is empty.

public void push$($T data$)$ throws StackException $$ This adds an element to the top of the stack if there is space, and throws StackException otherwise.

You can implement your stack using an array or linked list. A linked list is likely easier, and you can use the Node class provided on Canvas. If you wish, you can use an array as long as everything still works properly. Here is how you could initialize a generic node for your stack where the data is of type T:

Node node $=$ new Node$($data$,$ null$)$;

We recommend having an instance variable Node top that is a pointer to the top of the Stack. At initialization, this will be null. You need a variable int size that will keep track of the maximum number of elements in the Stack. In addition, you need a variable int curSize that tracks the number of elements in the Stack.

HINT: A simple way to implement a stack as a linked list is to add and remove it from the front of the list. This means you don't need to iterate through the entire list when pushing and popping, or that you don't need an additional pointer for the last node in the list. Be mindful of edge cases such as adding to an empty stack and removing from a stack with a current size of one.

The following is an example of creating a stack, pushing elements onto a stack, popping elements off of the stack, and handling exceptions. The following is an example. You still need to pass the JUnit tests.

Stack myStack $=$ new Stack$<>()$; try $\{$ myStack.push$(10)$; $$ myStack.push$(20)$; $$ myStack.push$(30)$; $$ System.out.println$($myStack$.$pop$())$; $//$ this should print $30$ myStack.push$(40)$; $$ myStack.push$(50)$; $$ myStack.push$(60)$; $$ myStack.push$(70)$; $//$ this causes an exception! $\}$ catch $($StackException e$)\{//$ catches any StackException that is thrown $$ System.out.println$("$Stack exception has occurred!"$)$; $\}$ finally $\{$ System.out.println$("$Goodbye$!")$; $\}$

Milestone $2$ Checkoff

Comment back in the tests for Milestone $2$ and run it$.$ Show a TA your Stack class, and tell them what underlying data structure you used.