Exercise 1

Download CircularArrayQueue.java, QueueADT.java and EmptyCollectionException.java from the sample code page and fill in the missing code in the methods. The code for the helper method expandCapacity is given; note that it is different from the expandCapacity of the regular array implementations that we have seen for the Stack ADT and Queue ADT.

first is similar to dequeue, but doesn't remove the element

isEmpty and size are trivial

for toString, setting up the string is similar in concept to the toString method in ArrayStack.java, which was similar to the following:

public String toString(){ String result = ""; for (int i=0; i < top; i++) result = result + stack[i].toString() + " "; return result; } 

Of course the attributes are no longer called stack and top, so you need to change those. But, more importantly, you will not be starting the array index at 0. The counter for the loop can still go from 0 to count, since you will still go through the for loop as many times as there are items in the queue. But the array index will need to be a different variable, that starts at the value in the attribute front. You will need to increment the array index in the body of the for loop, taking into account that it may need to wrap around to the beginning of the array again. It is the same idea as how rear is incremented in the enqueue method, and how front is incremented in the provided expandCapacity method.

Exercise 2

Download the given test driver TestCAQ.java to test your implementation of the CircularArrayQueue class. This test driver is provided as an example of a test program that does thorough testing, in a way that displays whether or not the test results are the expected results.

Answer the questions below before running TestCAQ on your circular array queue implementation, to make sure you understand how it works. Make corrections in your CircularArrayQueue.java until all the tests have been completed successfully.In the main method, what is the purpose of the second parameter in all the calls to the testing methods, for example the first 3 calls:

t_isEmpty(first, true); t_size(first, 0); t_toString(first, ""); 

Is it possible to enqueue objects of different types to the queue first, for example:

first.enqueue(new Integer()); first.enqueue(new Float(i*10)); 

What is the type of the objects being enqueued in the following statements?

first.enqueue("A"); first.enqueue("S");

CircularArrayQueue.java

/** * CircularArrayQueue represents an array implementation of a queue in * which the indexes for the front and rear of the queue circle back to 0 * when they reach the end of the array. * * @author Dr. Lewis * @author Dr. Chase * @version 1.0 08/12/08 */ public class CircularArrayQueue implements QueueADT { private final int DEFAULT_CAPACITY = 100; private int front, rear, count; private T[] queue; /** * Creates an empty queue using the default capacity. */ public CircularArrayQueue() { front = rear = count = 0; queue = (T[]) (new Object[DEFAULT_CAPACITY]); } /** * Creates an empty queue using the specified capacity. * * @param initialCapacity the integer representation of the initial * size of the circular array queue */ public CircularArrayQueue (int initialCapacity) { front = rear = count = 0; queue = ( (T[])(new Object[initialCapacity]) ); } /** * Adds the specified element to the rear of this queue, expanding * the capacity of the queue array if necessary. * * @param element the element to add to the rear of the queue */ public void enqueue (T element) { if (size() == queue.length) expandCapacity(); queue[rear] = element; rear = (rear+1) % queue.length; count++; } /** * Removes the element at the front of this queue and returns a * reference to it. Throws an EmptyCollectionException if the * queue is empty. * * @return the reference to the element at the front * of the queue that was removed * @throws EmptyCollectionException if an empty collections exception occurs */ public T dequeue() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException ("queue"); T result = queue[front]; queue[front] = null; front = (front+1) % queue.length; count--; return result; } /** * Returns a reference to the element at the front of this queue. * The element is not removed from the queue. Throws an * EmptyCollectionException if the queue is empty. * * @return a reference to the first element in the * queue * @throws EmptyCollectionException if an empty collections exception occurs */ public T first() throws EmptyCollectionException { // left as programming project } /** * Returns true if this queue is empty and false otherwise. * * @return returns true if this queue is empty and false if otherwise */ public boolean isEmpty() { // left as programming project } /** * Returns the number of elements currently in this queue. * * @return the integer representation of the size of this queue */ public int size() { // left as programming project } /** * Returns a string representation of this queue. * * @return the string representation of this queue */ public String toString() { // left as programming project } /** * Creates a new array to store the contents of this queue with * twice the capacity of the old one. */ public void expandCapacity() { T[] larger = (T[])(new Object[queue.length *2]); for(int scan=0; scan < count; scan++) { larger[scan] = queue[front]; front=(front+1) % queue.length; } front = 0; rear = count; queue = larger; } }

EmptyCollectionException.java /** * @author Lewis and Chase * * Represents the situation in which a collection is empty. */ public class EmptyCollectionException extends RuntimeException { /** * Sets up this exception with an appropriate message. * @param collection String representing the name of the collection */ public EmptyCollectionException (String collection) { super ("The " + collection + " is empty."); } }

TestCAQ.java

/* ** A java class that tests the implementation of CircularArrayQueue ** ** @author Ben Stephenson ** @version 0.2 ** edited for CS1027 2007, 2009 ** */ public class TestCAQ { // test isEmpty method public static void t_isEmpty(CircularArrayQueue