In the first part of this lab, we will be creating our own implementation of the queue data structure to better understand how to implement the FIFO property. Java already provides an interface called Queue that defines all the methods that a queue should have, as well as an AbstractQueue abstract class that implements some of the basic functionality of the Queue interface (that could be shared by other types of queues that are not backed by an array list like the one we will create below). We’ll again be using generics for the implementation so that the queue 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 MyQueue.java. Within this file, you should create a new class called MyQueue<T> that inherits from Java’s AbstractQueue<T>.
For our MyQueue data structure, we will be using an ArrayList to store all of the items in the queue. This ArrayList is the only necessary instance variable in your MyQueue 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 MyQueue class should implement the following six public methods. The first three are the primary behavior of a Queue data structure:
public boolean offer(T item) that adds a given item to the end of the queue and returns true to indicate the item was added. This is equivalent to our enqueue operation from class.public T poll() that removes and returns the item at the front of the queue if one exists, else it returns null if the queue is empty. This is equivalent to our dequeue operation from class.public T peek() that returns (but does not remove) the item at the front of the queue if one exists, else it returns null if the queue is empty. This can be a helpful access method for looking at the front item without removing it.The remaining three are required by Java’s Queue interface in order for your code to compile:
public boolean isEmpty() that returns true if the queue is empty and false if it is not.public int size() that returns the current size of the queue (i.e., the size of items).public Iterator<T> iterator() that just returns the interator being used by items.After you implement the offer and poll methods, do not forget to create a couple unit tests to help you debug (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 offer, then call poll the same number of times and verify that the items were dequeued in the same order that they were enqueued, as well as (2) alternating multiple calls to offer and poll 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.