This class implements the data structures necessary for an ArrayQueue
/** * This class implements the data structures necessary for an ArrayQueue which throws * proper exceptions and is expandable when the queue fills up. Much of the code below * is adapted from code on pages 194-195, 205-208 of Data Structures & Algorithms in Java by * Michael T. Goodrich and Roberto Tamassia. * * @author Alex Laird * @version 1.0 * File: ArrayQueue.java * Created: Oct 2008 * * @param defines the generics for the queue */ public class ArrayQueue implements Queue { public static final int CAPACITY = 1000; // default queue capacity protected int capacity; // current queue capacity protected int front; // index of the first element in queue protected int next; // index of the next available array cell in queue protected E[] genArray; // generic array used to implement the queue
/** * Default constructor. Passes the default capacity for the array if one is not specified. */ public ArrayQueue() { this(CAPACITY); }
/** * A constructor which will define the generic array used to implement the queue and set it's size. * * @param cap */ public ArrayQueue(int cap) { capacity = cap + 1; genArray = (E[]) new Object[capacity];
front = next = 0; }
/** * Inserts an element at the rear of the queue. * * @param element the element to be inserted */ public void enqueue(E element) { // check to see if array capacity has been reached if(size() == capacity - 1) { int newSize = capacity * 2;
// expand the array E[] newArray = (E[]) new Object[newSize];
for(int i = 0, j = front; i < size(); i++) { newArray[i] = genArray[j];
j = (++j)%capacity; }
// in case of wrap-around, assign front and next properly front = 0; next = capacity - 1;
// set old array pointer to new array capacity = newSize; genArray = newArray; }
// insert element, increment next pointer (wrap-around supported) genArray[next] = element; next = (++next)%capacity; } /** * Removes the element at the rear of the queue. * * @throws QueueEmptyException if the queue is empty * @return the removed element */ public E dequeue() throws Exception { E element;
if(isEmpty()) throw new Exception("Queue is empty.");
// remove element, null and increment front pointer (wrap-around supported) element = genArray[front]; genArray[front] = null; front = (++front)%capacity;
return element; }
/** * Returns, but does not remove, the front element of the queue. * * @throws QueueEmptyException if the queue is empty * @return the front element of the queue */ public E front() throws Exception { if(isEmpty()) throw new Exception("Queue is empty.");
return genArray[front]; }
/** * Returns the current number of elements in the queue. * * @return the number of elements in the queue */ public int size() { // return the size, wrap-around supported return(capacity - front + next)%capacity; }
/** * Checks to see if the queue is empty. * * @return true of false, depending on whether the queue is empty or not */ public boolean isEmpty() { return(front == next); }
/** * Will set all values of an array to null * * @param array is the array who's values are to be set to null * @return the array with each value set to null */ public static Object[] nullArray(Object[] array) { for(int i = 0; i < array.length; i++) { array[i] = null; }
return array; }
/** * The main method from which the program executes; it handles all testing and exception handling. * * @param args unused */ public static void main(String[] args) throws Exception { Object[] check = new Object[15]; Object[] answers = new Object[15]; boolean pass = false;
/* * Test #1: Compliance with Integer */
System.out.println("Test #1: Check to see if queue works properly with Integer objects.");
ArrayQueue iQueue = new ArrayQueue();
// valid output for test answers[0] = 1; answers[1] = 2; answers[2] = 3; answers[3] = 4; answers[4] = 5;