/**
 * A Queue with fixed capacity.
 * Operations are constant-time except for construction
 * which is O(capacity).
 */

public class CircularQueue implements Queue {
 
  /** The number of elements in me. */
  private int size;
  
  /** The index of the head and tail of the queue. */
  private int head, tail;
  
  /** The items in me, stored in contents[head..tail],
   *  with wraparound */
  private Object[] contents;
  
  /* Representation invariant
   *   Let capacity be contents.length
   *   size >= 0
   *   If size is 0, I am empty.
   *   If size > 0:
   *      contents[head] is the head
   *      contents[tail] is the tail
   *      if head <= tail, 
   *        contents[head..tail] contains the Objects 
   *        in the order they were inserted.
   *      if head > tail,
   *        contents[head.. capacity-1, 0..tail] contains
   *        the Objects in the order they were inserted,
   *        size = tail - head + 1 + capacity
   */
  
  /** A CircularQueue with capacity for n elements. */
  public CircularQueue(int n) {
    contents = new Object[n];
    tail = contents.length -1;
  }
  
  /** Append o to me. */
  public void enqueue(Object o) throws QueueFullException {
  
  	if(size == contents.length) {
  		throw new QueueFullException("Your queue is not big enough (size = " 
  		                             + contents.length + ")");
  	}
    tail = (tail + 1) % contents.length;
    contents[tail] = o;
    size++;
  }
  
  
  /** Remove and return my front element.
   *  Requires: size() > 0. */
  public Object dequeue() {
    Object result = contents[head];
    
    head = (head + 1) % contents.length;
    size--;
    return result;
  }
  
  /** Return my front element 
   *  Requires: size() > 0 */
  public Object head() {
    return contents[head];
  }
  
  /** Return the number of elements in me. */
  public int size() {
    return size;
  }
}