Lab on Queues with Circular Lists

Summary

This laboratory provides practice in using a circular list to implement queues. Specifically, class Queue207Implementation will implement the Queue207.java interface, using a QueueNode class to store specific queue items.

Acknowledgement

Most of this reading is an edited version of Henry M. Walker, Computer Science 2: Principles of Software Engineering, Data Types, and Algorithms, Little, Brown, and Company, 1989, Section 5.6, with programming examples translated from Pascal to Java. This material is used with permission from the copyright holder.

Introduction

In the original pointer implementation of queues in the lab on Queues with Singly-linked Lists, a queue was implemented as a singly linked list, and elements of the list were objects of class QueueNode . Insertion into the queue took place at the head of the list, whereas deletion took place at the tail of the list.

One alternative approach to this implementation simplifies this structure so that the head element of the list follows the tail element, as shown in the following figure.

This structure illustrates another commonly used list structure, called a circular list, in which the last list item points back to the first one.

In this list, each item points to the next, and this chain of pointers eventually forms a loop back to the first one. With this structure, we need only one pointer to the tail of the queue, and, from this last element, the next field specifies the location of the head of the queue. This requirement of only one pointer allows the declarations to be simplified considerably:

• a single tail field references the last item.
• a numberItems field provides a quick way to determine the current size of a queue.

The following notes outline some additional implementation details.

• exceptions:

  • check the specifications for Java's Queue interface to identify conditions under which exceptions are to be thrown.

• constructor:

  • numberItems is set to 0
  • tail is set to null

• insert:

  • a new QueueNode is created with the specified data.
  • if the queue previously was empty:
    • the next field of the new QueueNode references the QueueNode
    • the tail field of the queue references the new QueueNode
  • if the queue previously was not empty:
    • the next field of the new QueueNode references the logical head of the queue — the item after the previous tail
    • the old tail node points to the new QueueNode
    • the queue's tail is updated to point to the new QueueNode

• remove:

  • data are retrieved from the node after the current tail of the queue
  • if removing the node from the queue results in an empty queue
    • the tail of the queue becomes null
  • if nodes will remain on the queue
    • the next field for tail node is updated to the next node in the list

Steps for this Lab

1. Write class Queue207Implementation2 that provides a circular-list implementation of the Queue207 interface, including a default constructor and methods add, remove, element, and size.

2. Test your implementation with the test suite that you developed in the lab on queues and testing.

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/207.sp012/labs/lab-queues-circular.shtml

created 1 April 2012 last revised 4 April 2012
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.