import [Link].
Iterator;
import [Link];
class ArrayQueue<E>
{
// Data Fields
private E[] theData; // Array to hold the data.
private int front; // Index of the front of the queue.
private int rear; // Index of the rear of the queue.
private int size; // Current size (actual number of elements)
// of the queue.
private int capacity; // Current capacity of the queue.
private static final int DEFAULT_CAPACITY = 10;
// Default capacity of the queue.
// 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)
{ if(initCapacity <= 0)
capacity = DEFAULT_CAPACITY;
else
capacity = initCapacity;
theData = (E[]) new Object[capacity];
front = 0;
rear = capacity - 1;
size = 0;
}
/** Copy constructor: Construct a new queue as copy of the existing
* queue passed as parameter.
* @param other The original queue
* copy is made in “this object”
*/
public ArrayQueue(ArrayQueue<E> other)
{
capacity = [Link];
size = [Link];
front = [Link];
rear = [Link];
theData = (E[]) new Object[capacity];
int index = front;
for (int i = 0; i < size; i++) {
theData[index]= [Link][index];
index = (index + 1) % capacity;
}
}
// Public Methods
/**
* Return true, if the queue is empty
* @return True if the queue is empty
*/
public boolean isEmpty()
{
return (size == 0);
}
/**
* 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)
*/
public boolean offer(E item)
{
if (size == capacity) {
reallocate();
}
size++;
rear = (rear + 1) % capacity;
theData[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
*/
public E peek()
{
if (size == 0) {
return null;
}
else {
return theData[front];
}
}
/**
* Removes the entry at the front of the queue and returns it,
* if the queue is not empty.
* @return The item removed if queue is not empty, else return null.
*/
public E poll()
{
if (size == 0) {
return null;
}
E result = theData[front];
front = (front + 1) % capacity;
size--;
return result;
}
/**
* Returns an iterator to the elements in the queue
* @return an iterator to the elements in the queue
*/
public Iterator<E> iterator()
{
return new Iter();
}
// Private Method
/**
* Double the capacity and reallocate the data.
* @pre The array is filled to capacity.
* @post The capacity is doubled and the first half of the
* expanded array is filled with data.
*/
@SuppressWarnings("unchecked")
private void reallocate()
{
int newCapacity = 2 * capacity;
E[] newData = (E[]) new Object[newCapacity];
int j = front;
for (int i = 0; i < size; i++) {
newData[i] = theData[j];
j = (j + 1) % capacity;
}
front = 0;
rear = size - 1;
capacity = newCapacity;
theData = newData;
}
public int size() { return size;}
/** Inner class to implement the Iterator<E> interface. */
private class Iter implements Iterator<E>
{
// Data Fields
private int index; // Index of next element
private int count; // Count of elements accessed so far
// Methods
// Constructor
/**
* Initializes the Iter object to reference the first queue element.
*/
public Iter()
{
index = front;
count = 0;
}
/**
* @return true, if there are more elements in the queue to access.
*/
public boolean hasNext()
{
return (count < size);
}
/**
* 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
*/
public E next()
{
if (!hasNext()) {
throw new NoSuchElementException();
}
E returnValue = theData[index];
index = (index + 1) % capacity;
count++;
return returnValue;
}
public void remove()
{
throw new UnsupportedOperationException();
}
} // end inner class Iter
}