CS 231: Lab #6

Title image Spring 2020

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.

Video: Queues (also on Courses/CS231/Course_Materials/Videos)

Tasks

  1. Setup

    Make a new folder for this week's project and 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 doubly-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.

    public boolean offer(T item) {
        // Inserts item into this queue if possible. Returns true if successful.
    }
    
    public T peek() {
        // Returns, but does not remove, the head of this queue, or returns null if this queue is empty.
    }
    
    public T poll() {
        // Returns and removes the head of this queue, or returns null if this queue is empty.
    }
  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.

    Video: Iterators

  6. Thoroughly test all of your methods

    Write a main method to test your Queue class. Your test code should 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.