//queue implementation using array
//Author: Konstantin Voevodski
//Date: 6/4/07

public class myArrayQueue<AnyType>
{
    private static final int DEFAULT_CAPACITY = 10;
    int head;
    int tail;
    AnyType[] items;
       
    public myArrayQueue()
    {
        head = 0;
        tail = 0;
        items = (AnyType[]) new Object[DEFAULT_CAPACITY];
    }
    
    public boolean isEmpty()
    {
        return(head == tail);
    }
       
    public void enqueue(AnyType x)
    {
        if(items.length == tail)
            ensureCapacity();
        items[tail++] = x;
    }
    
    
    public AnyType dequeue()
    {
        if(isEmpty())
        {
            throw new java.util.NoSuchElementException();
        }
	  AnyType val = items[head++];
        return (val);
    }
    
     public void ensureCapacity()
    //shift the array and enlarge its capacity
    {
        int newCapacity = Math.max((tail - head) * 2 + 1,DEFAULT_CAPACITY);
        AnyType[] old = items;
        items = (AnyType[]) new Object[newCapacity];
        //copy over the elements which have not been dequeued
        for(int x = head; x < tail; x++)
        {
            items[x-head] = old[x];
        }
        tail = tail - head;
        head = 0;
    }
}