CS 231: Lab #5

Title image Spring 2018


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 horribly inefficient for a queue. Use a doubly-linked list and make yourself happy.


  1. Make a new folder for this week's project.
  2. Make a file named MyQueue.java. Declare your class:

    public class MyQueue<T> implements Iterable<T>

    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.

  3. Find the Queue interface documentation and see what the key functions are. What is the difference between them?
  4. With a doubly-linked list, decide what fields you want for your class and for your private Node class. Make any additional methods that are required.
  5. 4. Implement the three interface functions that do not throw 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 node at the front without removing it from the queue..
  6. Implement your iterator. Make sure your iterator loops over the linked list from the head to the tail of the queue.
  7. Thoroughly test all of your methods. That means to write code that causes every line of the code you have written to be executed.

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