Queues

The goal of this lab period is to augment your LinkedList class from last week by implementing a Queue interface. However, we will first add a tail pointer to our LinkedList class to get both offer and poll to be constant time operations.

Setup

This week's project involves downloading a few files and copying over your LinkedList from last week. Follow these steps to get set up:

1. Make a new folder for this week's project.
2. Copy over your LinkedList.java file from last week (make sure to copy it so you still have last week's version to refer back to if you break anything)
3. Download the following files:
   • The Queue interface
   • The QueueTests
   • The Job class
   • The JobMaker class
   • The ServerFarmViz class
   • The ServerFarmSimulation class

Tasks

Adding a Tail Pointer to your Linked List

We'll continue working with the Linked List implementation you wrote for the last project. We'll use it as the basis for implementing a Queue in the next step. However we will first add a tail pointer to the LinkedList. This is important for getting both offer and poll to run in constant time! We'll need this for the project.

To add a tail pointer, you will first add a tail field of type Node <T> to your LinkedList class. Then, add the following methods to your LinkedList class from last week:

• public void addLast(T item) inserts the item at the end of the list. Remember to update the tail pointer!
• public T removeLast() removes the last item of the list and returns it. Remember to update the tail pointer!
• public T getLast() returns the item at the end of the list.

Now, we will update some of the existing Linked List methods as follows:

• public LinkedList() update your constructor so it sets the tail field to null.
• public void clear() update this so it sets the tail field to null
• public void add(T item) update this so that if the linked list was previously empty, the tail points at the new node that was just added
• public T remove() update this so that if the list becomes empty, the tail pointer is set to null
• public void add(int index, T item) Check if the index is the end of the linked list. If so, use your addLast method.
• public T remove(int index) Check if the index is the end of the linked list. If so, user your removeLast method.
• public T get(int index) Check if the index is the end of the linked list. If so, use your getLast method.

Implementing a Queue

We will implement a Queue by extending our LinkedList class to implement the Queue interface. To do this, edit the declaration of your LinkedList class to implement the Queue interface: public class LinkedList<T> implements Queue<T>

After adding this implementation declaration, your IDE might tell you you're missing a few methods. If you check the Queue interface, you'll probably see that your LinkedList is missing the offer, peek, and poll methods. Implement these methods by calling the appropriate method from your LinkedList.

The trick here is to figure out which side of your LinkedList (the head or tail) to add items to, and which side to remove them from. With the tail pointer we added, there's an answer that makes both operations run in constant time! If you get it wrong, you'll know when you try to run the QueueTester we supplied below because it won't terminate.

Note, when we tell you to make a Queue in the Project, you will actually create a LinkedList since it now implements all of the Queue methods.

Lab checkpoint: Show us your code passes the tests in the QueueTests to get credit for the lab! It checks that your Queue methods work as expected, that you got those constant runtimes, and that your previous LinkedList methods still work as expected.

---

When you are done, you can proceed to the project.

---