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().

 

Let’s 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. Let’s 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.

 

‘A’

‘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’);

 

‘A’

‘B’

‘C’

‘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;


Let’s look at our example again.

  1. q.enqueue(‘A’) ΰ front =0, rear = 1
  2. q.enqueue(‘B’) ΰ front = 0, rear = 2
  3. q.enqueue(‘C’) ΰ front = 0, rear = 3
  4. q.dequeue( ) ΰ front = 1, rear = 3
  5. q.dequeue( ) ΰ front = 2, rear = 3
  6. q.enqueue(‘D’) ΰ front = 2, rear = 4
  7. q.enqueue(‘E’) ΰ front = 2, rear = 5
  8. q.enqueue(‘F’) ΰ front = 2, rear = 0
  9. q.dequeue( ) ΰ front = 3, rear = 0

 

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).