Queue

My notes on the queue abstract data type with an implementation using an array in Java.

You can find the complete code for this and other data structures here: data structures and algorithms

A queue is an abstract data type that has a First In First Out (FIFO) behavior which means items will going to come out of the queue in the same order they were enqueued.

Common Operations for a queue includes:

Operation	Complexity
enqueue(element)	O(1)
dequeue()	O(1)

In this implementation we are using a normal array, and we need to keep track of a few things:

• size: which will hold the current size of the queue
• dequeueIndex: the index where the next element to be dequeued is located.
• enqueueIndex: the index where a new element will be placed.

Enqueue will add a new element to the queue.

public boolean enqueue(T valueToPush) {
    if(size == innerArray.length) {
        return false;
    }
    innerArray[enqueueIndex] = valueToPush;
    if (enqueueIndex == innerArray.length - 1) {
        enqueueIndex = 0;
    } else {
        enqueueIndex++;
    }
    size++;

    return true;
}

If size of the queue is equal to the capacity of the inner array then it means that queue is full and we don’t enqueue more items.

In the case the enqueueIndex is already at the end of the of the inner array we circle back to the beginning of the array.

Dequeue takes out an element of the queue and returns it.

public T dequeue() {
    if(size == 0) {
        throw new NullPointerException("empty queue");
    }
    T valueToDequeue = innerArray[dequeueIndex];
    innerArray[dequeueIndex] = null;
    if (dequeueIndex == innerArray.length - 1) {
        dequeueIndex = 0;
    } else {
        dequeueIndex++;
    }
    size--;
    return valueToDequeue;
}

Similarly to the enqueue method, if the dequeueIndex is at the end of the array we circle back to the beginning.

Download the complete code for this and other data structures here: data structures and algorithms.