CircularArrayQueue.java.html

  1  import java.util.NoSuchElementException;
  2  
  3  /**
  4     An implementation of a queue as a circular array.
  5  */
  6  public class CircularArrayQueue
  7  {
  8     private Object[] elements;
  9     private int currentSize;
 10     private int head;
 11     private int tail;
 12  
 13     /**
 14        Constructs an empty queue.
 15     */
 16     public CircularArrayQueue() 
 17     {
 18        final int INITIAL_SIZE = 10;
 19        elements = new Object[INITIAL_SIZE];
 20        currentSize = 0;
 21        head = 0;
 22        tail = 0;
 23     }
 24  
 25     /**
 26        Checks whether this queue is empty.
 27        @return true if this queue is empty
 28     */
 29     public boolean empty() { return currentSize == 0; }
 30  
 31     /**
 32        Adds an element to the tail of this queue.
 33        @param newElement the element to add
 34     */
 35     public void add(Object newElement)
 36     {
 37        growIfNecessary();
 38        currentSize++;
 39        elements[tail] = newElement;
 40        tail = (tail + 1) % elements.length;
 41     }
 42  
 43     /**
 44        Removes an element from the head of this queue.
 45        @return the removed element
 46     */
 47     public Object remove() 
 48     {
 49        if (currentSize == 0) { throw new NoSuchElementException(); }
 50        Object removed = elements[head];
 51        head = (head + 1) % elements.length;
 52        currentSize--;
 53        return removed;
 54     }
 55  
 56     /**
 57        Grows the element array if the current size equals the capacity.
 58     */
 59     private void growIfNecessary()
 60     {
 61        if (currentSize == elements.length)
 62        {
 63           Object[] newElements = new Object[2 * elements.length];
 64           for (int i = 0; i < elements.length; i++) 
 65           { 
 66              newElements[i] = elements[(head + i) % elements.length]; 
 67           }      
 68           elements = newElements;
 69           head = 0;
 70           tail = currentSize;
 71        }
 72     }
 73  }