CSSE 220 – Object-Oriented Software Development

Fixed Length Queue In-Class Exercise

Objectives

The FixedLengthQueue abstract data type that you will implement today is useful for the first phase of the Markov Program.

Description

This assignment is to be done by a pair of students; the same pairs as assigned for the Markov Program. I suggest that you have the student who feels least confident be the one who does the “driving” then it will be easier to make sure that both of you understand what you are doing.

A "fixed length queue" is a very simple abstract data type. It behaves (sort of) like a queue that holds Objects. When constructed, it is given a fixed capacity, and it initially contains no objects.

When the queue is already filled to capacity, we have some extra work to do to add another object. The object that was the head of the queue before the addition is “pushed out”, and what was the second object in the queue becomes the new head.

• Whenever we add an object to the queue, if the queue is already filled to capacity
  • the object that was the head of the queue before the addition is “pushed out”, and
  • what was the second object in the queue becomes the new head.

There is no explicit remove operation. Perhaps it should be there, but it is not part of this assignment due to time constraints.

The only other public operation besides add is toString, which simply calls each object’s toString method, and concatenates all of the resulting strings (in queue order of course), separated by a space.

Thus you only have three public methods to implement:

• constructor,
• add,
• toString.

A FixedLengthQueue should be implemented using an array, so only a fixed amount of space is ever allocated for a given queue. The add method should be a constant-time operation (i.e. the running time for this method should not depend on the capacity of the queue, as evidenced by no loops or recursive calls in its code). Hint: treat the array as a circle. The % (mod) operator may be helpful here.

Tasks

Get help if you’re stuck. This exercise is intended to take about 25 minutes in class.

1. Check out the FixedLengthQueue project from your Markov team repository.
2. Notice that two test classes are provided:
   • FixedLengthQueueTest is a JUnit test class; we’ll use this in grading your work.
   • TestFixedLengthQueue has a main() method that you may find useful for experimenting. Here’s what its output should be when you’ve implemented the data structure correctly:

     ---------- Queue length = 4
     I
     I heard
     I heard it
     heard it through
     it through the
     through the grapevine.
     
     ---------- Queue length = 4
     I
     I saw
     I saw her
     I saw her again
     saw her again last
     her again last night.
     
     Exception occurred as expected.
     

3. Complete the TODO items in FixedLengthQueue.
4. Add code to the constructor to prohibit construction of a FixedLengthQueue whose capacity is less than 1.

Turn-in Instructions

Turn in your work by committing it to your SVN repository.