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.

Check out the FixedLengthQueue project from your Markov team repository.
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.
```
Complete the TODO items in FixedLengthQueue.
Add code to the constructor to prohibit construction of a FixedLengthQueue whose capacity is less than 1.

Remember, in all your code:

Write appropriate comments:
- Javadoc comments for public fields and methods.
- Explanations of anything else that is not obvious.
Give self-documenting variable and method names:
- Use name completion in Eclipse, Ctrl-Space, to keep typing cost low and readability high.
Use Ctrl-Shift-F in Eclipse to format your code.
Take care of all auto-generated TODO’s.
- Then delete the TODO comment.
Correct ALL compiler warnings.
- Quick Fix is your friend!

Here is the grading rubric for this assignment.

Turn-in Instructions

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