The Queue Data Structure
A queue is a data structure that stores elements in an ordered list that permits access at two ends, front and rear. Items are added at the rear and removed from the front. A queue implements a FIFO, First In First Out, policy. A description of some operations for the array implementation of the queue follows.
ADT queue is
Data
int front references first item in the queue
int rear references the next available memory location in the array
int arraySize the capacity of the array
Object [] data the array to hold the elements
Operations
Constructor
Initial values: front = rear = 0. arraySize set to default value, and
data is initialized to arraySize.
Process: Initialize the object.
enqueue
Input: A java.lang.Object.
Preconditions: The array is not full.
Process: Add the element to the rear of the queue. Increment
rear.
Output: None.
Post Condition: Object is at the rear of the queue.
dequeue
Input: None.
Preconditions: The array is not empty.
Process: Assign an Object reference the value of data[front].
Increment front.
Output: java.lang.Object.
Post Condition: front references the next item in the queue.
size
Input: None.
Preconditions: None.
Process: Compute the number of elements in the queue using
the formula (arraySize front + rear) % arraySize.
Output: int.
Post Condition: The queue is unchanged.
We leave it to you to describe the other queue operations including isFull() and isEmpty().
Lets look at our implementation. Given a 6 element array queue, we can implement it in one of two ways. We can add items to the queue and increment the rear, and as we remove items, we can increment front. Lets look at the following .
Queue q;
q.enqueue(A);
q.enqueue(B);
q.enqueue(C);
q.dequeue();
The following is a depiction of our data array after the operations.

B 
C 



^front ^rear
Now front = 1 and rear = 3. If we complete the following operations, what is the value of front and rear? What is the value returned by size() or isFull()?
q.dequeue();
q.dequeue();
What happens after q.enqueue(D) and q.enqueue(E);



D 
E 

^front ^rear
How do you know when the queue is empty? If you notice, this implementation can leave holes. Another way to do this is to move all items up every time you call the dequeue method. In this manner when we first called dequeue to get A off the queue, then we would move B down followed by C and decrement rear. In other words we keep front at zero. There is a lot of overhead in implementing the array queue in this manner; in fact it has a time complexity of O(n).
If we can imagine stretching our array around so that the last element meets the first one, it looks a lot like a circle.
Now we can just move around the circle and not worry about holes or overhead moving all the elements up when you dequeue. All we need is an algorithm to move around the queue without exceeding the array bounds. To do this, we can use the modulo, or remainder, function.
front = (front + 1) % arraySize;
rear = (rear + 1) % arraySize;
Lets look at our example again.
The time complexity is much better for the enqueue and dequeue operations with the circular queue implementation. In fact each operation is done in constant time, O(1).