/**
   The ArrayQueue class implements the Queue interface by means of
   a circular array.
 
   @author      Franck van Breugel
   @version     1.3    June 13, 2001
*/
public class ArrayQueue implements Queue 
{

    public static final int CAPACITY = 1000; // default capacity of array

    private int capacity;                    // maximum capacity of array
    private Object[] queue;                  // holds elements of queue
    private int front;                       // index where the next element will be dequeued
    private int rear;                        // index where the next element will be enqueued
 
    /** 
       Constructs a queue of default capacity - 1. 
    */
    public ArrayQueue() 
    {
        this(CAPACITY);
    }

    /** 
       Constructs a queue of specified capacity - 1. 
     
       @param capacity the capacity of the queue - 1. 
    */
    public ArrayQueue(int capacity) 
    {
        this.capacity = capacity;
        this.queue = new Object[capacity];
        this.front = 0;
	this.rear = 0;
    }
 
    public int size() 
    {
        return ((capacity - front + rear) % capacity);
    }

    public boolean isEmpty() 
    {
        return (front == rear);
    }

    public Object front() throws QueueEmptyException 
    {
        if (isEmpty()) 
        {
            throw new QueueEmptyException("Queue is empty.");
        }
        return queue[front];
    }

    public void enqueue(Object element) 
    {
        if (size() == capacity - 1) 
        {
            throw new QueueFullException("Queue overflow.");
        }
        queue[rear] = element;
        rear = (rear + 1) % capacity;
    }

    public Object dequeue() throws QueueEmptyException 
    {
        if (isEmpty()) 
        {
            throw new QueueEmptyException("Queue is empty.");
        }
        Object temp = queue[front];
        queue[front] = null;
        front = (front + 1) % capacity;
        return temp;
    }    

    /**
       Returns a string representation of this queue.
     
       @return A string representation of this queue.
    */
    public String toString() 
    {
        String rep = "";
        for (int i = 0; i < size(); i++) 
        {
        /* rep = queue[front % capacity].toString() + "\n" + ... + queue[(front + i - 1) % capacity].toString() + "\n" */
            rep += queue[(front + i) % capacity].toString();
            rep += "\n";
        }
        return rep;
    }
}