In the second part of this lab, we will be creating our own implementation of the stack data structure to better understand how to implement the LIFO property (in contrast with our FIFO queue data structure in Part 1). Interestingly, Java does not have a built in interface for stacks, but it does have a class called Stack that implements all of the methods that a stack should have. Instead, we have provided you in your GitHub repository with an interface called StackADT that uses the same method naming scheme as Java’s built in Stack. As in Part 1, we will create our own stack implementation following this interface by using an array list as our backing data structure. We’ll again be using generics for the implementation so that the stack can store any type of data as elements.
Open up your GitHub repository for this assignment in Visual Studio Code, then create a new file called MyStack.java. Within this file, you should create a new class called MyStack<T> that implements the interface StackADT<T> (provided in StackADT.java).
For our MyStack data structure, we will be using an ArrayList to store all of the items in the stack. This ArrayList is the only necessary instance variable in your MyStack class, but you are welcome to add more if they are helpful for you. That means that the only job of the constructor is to create this ArrayList (and anything else you’ve added).
Your MyStack class should implement the following five public methods:
public void push(T item) that adds a given item to the top of the stack.public T pop() that removes and returns the item at the top of the stack if one exists, else it returns null if the stack is empty.public T peek() that returns (but does not remove) the item at the top of the stack if one exists, else it returns null if the stack is empty. This can be a helpful access method for looking at the front item without removing it.public boolean empty() that returns true if the stack is empty and false if it is not.public int size() that returns the current size of the queue.After you implement the push and pop methods, do not forget to create a couple unit tests to help you debug (again you might have to have all of the methods created, but not fully implemented, before you can run unit tests). Useful strategies might be to (1) add a few items using push, then call pop the same number of times and verify that the items were removed in the opposite order that they were added, as well as (2) alternating multiple calls to push and pop to make sure that items are properly added even after others are removed. Don’t forget to also create a unit test to verify your peek method.
Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.