CSC 207 Grinnell College Spring, 2012
 
Algorithms and Object-Oriented Design
 

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.

A Circular List Implementation of a Queue

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:

The following notes outline some additional implementation details.

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
Valid HTML 4.01! Valid CSS!
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.