CS 231: Data Structures and Algorithms (Lab Page)

Title image Lab 6
Fall 2016

Queues

The goal of this lab period is to give you an opportunity to implement a queue using your own linked list.

Tasks

  1. Make a new folder for this week's project.
  2. Copy LinkedList.java from last week and add a method that allows you to remove a particular item:

    public void remove(T thing).

    Test your new method. This means you should test (at a very minimum) adding to an and removing from an empty list, a list with one item, and a list with multiple items. For a list with multiple items, you should test its ability to add to the list and remove from the beginning of the list, the middle of the list, and the end of the list.

  3. 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.

  4. Find the Queue interface documentation and see what the key functions are. Implement the six interface functions (though note that you do not need to support a maximum or initial capacity). The add and offer methods should put the new node on one end of the queue, and the remove and poll methods should remove and return the data in the node from the other end of the queue.

    Note that you do not need to begin from scratch. Use your LinkedList class from the last project to implement the queue. Your Queue methods can simply call LinkedList methods in the appropriate manner. You will likely need to add some methods to your LinkedList class to make it straight-forward (i.e. you will need either a removeFromHead or removeFromTail, depending on which end you add to).

  5. Make sure your iterator loops over the linked list from the head to the tail of the queue.
  6. Thoroughly test all of your methods.

Once you have completed the lab, go on to the project.