package prog06;
import java.util.*;
/**
* Implements the Queue interface using a circular array.
**/
public class ArrayQueue<E> extends AbstractQueue<E>
implements Queue<E> {
// Data Fields
/** Index of the front of the queue. */
private int front;
/** Index of the rear of the queue. */
private int rear;
/** Current size of the queue. */
private int size;
/** Default capacity of the queue. */
private static final int DEFAULT_CAPACITY = 10;
/** Array to hold the items. */
private E[] theItems;
// Constructors
/**
* Construct a queue with the default initial capacity.
*/
public ArrayQueue () {
this(DEFAULT_CAPACITY);
}
/**
* Construct a queue with the specified initial capacity.
* @param initCapacity The initial capacity
*/
@SuppressWarnings("unchecked")
public ArrayQueue (int initCapacity) {
theItems = (E[]) new Object[initCapacity];
front = 0;
rear = theItems.length - 1;
size = 0;
}
// Public Methods
/**
* Inserts an item at the rear of the queue.
* @post item is added to the rear of the queue.
* @param item The element to add
* @return true (always successful)
*/
@Override
public boolean offer (E item) {
if (size == theItems.length)
reallocate();
size++;
rear = (rear + 1) % theItems.length;
theItems[rear] = item;
return true;
}
/**
* Returns the item at the front of the queue without removing it.
* @return The item at the front of the queue if successful;
* return null if the queue is empty
*/
@Override
public E peek () {
if (size == 0)
return null;
return theItems[front];
}
/**
* Removes the entry at the front of the queue and returns it
* if the queue is not empty.
* @post front references item that was second in the queue.
* @return The item removed if successful or null if not
*/
@Override
public E poll() {
// EXERCISE 3
if(size == 0)
return null;
else
{
size--;
E frontEntry = theItems[front];
front = (front+1)%theItems.length;
return frontEntry;
}
}
/**
* Return the size of the queue
* @return The number of items in the queue
*/
@Override
public int size () {
return size;
}
/**
* Returns an iterator to the elements in the queue
* @return an iterator to the elements in the queue
*/
@Override
public Iterator<E> iterator () {
return new Iter();
}
// Private Methods
/**
* Double the capacity and reallocate the items.
* @pre The array is filled to capacity.
* @post The capacity is doubled and the first half of the
* expanded array is filled with items.
*/
@SuppressWarnings("unchecked")
private void reallocate () {
int newCapacity = 2 * theItems.length;
E[] newItems = (E[]) new Object[newCapacity];
if(front > rear)
{
System.arraycopy(theItems, front, newItems, 0, theItems.length-front);
System.arraycopy(theItems, 0, newItems, theItems.length-front, size-theItems.length+front);
}
else
{
System.arraycopy(theItems, front, newItems, 0, size);
}
front = 0;
rear = size - 1;
theItems = newItems;
}
private boolean labSolution = false;
/** Inner class to implement the Iterator<E> interface. */
private class Iter implements Iterator<E> {
// Data Fields
// Index of next element */
private int index;
// Count of elements accessed so far */
private int count = 0;
// Methods
// Constructor
/**
* Initializes the Iter object to reference the
* first queue element.
*/
public Iter ()
{
if (labSolution) {
index = front;
}
else
{
if(size == 0)
index = -1;
else
index = front;
}
}
/**
* Returns true if there are more elements in the queue to access.
* @return true if there are more elements in the queue to access.
*/
@Override
public boolean hasNext () {
if (labSolution)
return count < size;
else {
// EXERCISE
return !(index == -1);
}
}
/**
* Returns the next element in the queue.
* @pre index references the next element to access.
* @post index and count are incremented.
* @return The element with subscript index
*/
@Override
public E next () {
if (!hasNext()) {
throw new NoSuchElementException();
}
E returnValue = theItems[index];
if (labSolution) {
index = (index + 1) % theItems.length;
count++;
}
else {
// EXERCISE
if(index == rear)
index = -1;
else
index++;
}
return returnValue;
}
/**
* Remove the item accessed by the Iter object -- not implemented.
* @throws UnsupportedOperationException when called
*/
@Override
public void remove () {
throw new UnsupportedOperationException();
}
}
}
package prog06;
import java.util.*;
public class Main {
public static void main (String[] args) {
System.out.println("ArrayQueue");
test(new ArrayQueue<Integer>());
// System.out.println("LinkedQueue");
// test(new LinkedQueue<Integer>());
// WordGame game = new WordGame();
}
static void test (Queue<Integer> queue) {
for (int i = 0; i < 5; i++)
queue.offer(i);
System.out.println(queue);
for (int i = 5; i < 15; i++) {
System.out.println(queue.poll());
queue.offer(i);
System.out.println(queue);
}
for (int i = 15; i < 25; i++)
queue.offer(i);
System.out.println(queue);
}
}