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:

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:

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

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.