Fixed Length Queue Programming problem
in-class exercise

The FixedLengthQueue abstract data type that you will implement today is useful for the first phase of the Markov Program. We will refer to it occasionally later in the term as well.

This assignment is to be done by a pair of students. 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.

If the number of students in class today is odd, I will ask for a "solo" volunteer.

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.

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 performs 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 % operator may be helpful here.

 

Code that uses a FixedLengthQueue

The following test program should clarify the behavior of the operations:

public class TestFixedLengthQueue {

  public static void main(String[] args) {
    // Tests standard behavior
    FixedLengthQueue q = new FixedLengthQueue(3);
    String testString = "I heard it through the grapevine.";
    String[] splitString = testString.split(" ");
    for (int i = 0; i < splitString.length; i++) {
      q.add(splitString[i]);
    System.out.println(q);
    }

    // Tests undersized queue:
    try {
      q = new FixedLengthQueue(0);
    } catch (IllegalArgumentException e) {
      System.out.println("Exception occurred as expected.");
    }
  }
}


/* Correct output:

I
I heard
I heard it
heard it through
it through the
through the grapevine.
Exception occurred as expected.


*/

The Process