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

for toString, setting up the string is 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.

------------ 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; } }

------------

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."); } }