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 }