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
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
Initial values: front = rear = 0. arraySize set to default value, and
data is initialized to arraySize.
Process: Initialize the object.
Input: A java.lang.Object.
Preconditions: The array is not full.
Process: Add the element to the rear of the queue. Increment
Post Condition: Object is at the rear of the queue.
Preconditions: The array is not empty.
Process: Assign an Object reference the value of data[front].
Post Condition: front references the next item in the queue.
Process: Compute the number of elements in the queue using
the formula (arraySize front + rear) % arraySize.
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 .
The following is a depiction of our data array after the operations.
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()?
What happens after q.enqueue(D) and q.enqueue(E);
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).