CPSC 170 Lab 8: Queue

In this lab you are going to implement a linked list that can have objects added to the back and removed from the front, otherwise known as a queue.

Linked List Add

The file LinkedList.java contains a template for a linked list class. It has instance data for references to the first and last nodes in the list. These references are of type Node, which is a private sub-class of LinkedList. The node class has two public instance variables, object and next. The object instance variable is a generic type that is a reference to the data stored in the linked list. The next instance variable is a reference to the next node in the linked list. If the next reference is null, then the node is the last element in the list.

The LinkedList class contains a method stub, addLast, for adding to the linked list. The method should add the specified object to the end of the linked list. The method should begin by creating a new node with the object set to the object to add and the next reference set to null (because it is the end of the list). Next, if the list is empty, it should set the first and last instance variables to reference the new node. If the list is not empty, it should update the current last node in the list to reference the new node as the next node and update the last instance variable to reference the new node. Finally, increment the size instance variable.

Printing

Before testing the add method you will need to be able to print a linked list. Complete the toString method. The method should return a string that is a concatenation of all of the elements in the linked list. In order to generate this string you should create a Node variable that is initialized to the first node in the list and write a loop that concatenates a string representation of the object in the current node to the return string and updates the current node to be the next node in the list. The loop should terminate when there is no next element. Write a program that tests both the add and the toString method. Be sure to test the to string on an empty list as well as a full list.

Removing

Complete the removeFirst method. The method should remove the first element from the linked list. If the list is empty, the method should throw a NoSuchElementException exception. If the list contains only one element, the method should set the first and last references to null. If the list contains more than one element, the method should set the first reference to be the second element in the list. Finally, decrement the size variable. Note, the remove method does not actually delete any data. It simply changes references such that there are no variables that reference the deleted node. Eventually, the Java garbage collector will delete the node and its data from memory. Test your remove method before proceeding.

Storing Future Operations in a Queue

Queues are useful for storing data that needs to be processed. In the maze traversal program that we created in class we needed to store the location of branches in the path for future processing. Using a queue it is possible to create a looping version of the maze traversal program.

The file Maze.java contains the maze traversal program that we created in class. Rewrite the canTraverse method to use a loop and a queue instead of recursion. The looping version should begin by adding the location of the start cell to an empty queue. Then, while the queue is not empty it should remove a cell from the queue. If the removed cell is the end cell then the loop should stop and the method should return true. If the cell is not the end cell it should add all of its neighboring cells that are valid to the queue. If the queue becomes empty without ever traversing to the end cell, then the method should return false.

Submission

Submit a zip file of your code on the course Inquire site that uses your last names as the file name.