CS 231: Lab #5

Queues

The goal of this lab period is to give you an opportunity to implement a node-based queue. You could use a singly linked list, but it's more fun to make a doubly-linked list.

Tasks

1. Setup

   Make a new folder for this week's project.

   Make a file named MyQueue.java. Declare the class as:

   public class MyQueue<T> implements Iterable<T> {
// class body goes here
}

   Note: Although we are using Java's Queue interface as inspiration, we are not going to implement all of the methods in that interface (specifically, we are ignoring the larger set of Collections methods), so we will not say that our class "implements Queue". It will, however, implement Iterable.

2. Look up the Queue interface on the Java documentation

   Find the Queue interface documentation and see what the key functions are. What is the difference between the two sets of three functions?

3. Define the fields for a double-linked list

   Decide what fields you want for your class and for your private Node class. Make any additional methods that are required.

4. Implement the core Queue functions

   Implement the three interface functions that do not throw an exception (offer, poll, peek). The offer method should put the new node on the end (tail) of the queue; the poll method should remove and return the data in the node at the front (head) of the queue; and peek should return the value at the front without removing it from the queue.

5. Implement an iterator for the Queue class.

   Make sure the iterator loops over the linked list from the head to the tail of the queue.

6. Thoroughly test all of your methods

   Write code that causes every line of the code you have written to be executed. Make sure the results are as expected.

When you are done, go ahead and start the project.