The last part of the tutorial series was aboutimplementing a queue with a linked list. In this part, we implement a queue with an array – first a bounded queue (i.e., one with a fixed capacity) – and then an unbounded queue (i.e., one whose capacity can change).

Let's start with the simple variant, the bounded queue.

Implementing a Bounded Queue with an Array

We create an empty array and fill it from left to right (i.e., ascending from index 0) with the elements inserted into the queue.

The following image shows a queue with an array calledelements, which can hold eight elements. So far, six elements have been inserted into the queue.tailIndex always indicates the next insertion position:

When dequeuing the elements, we also read them from left to right and remove them from the array.headIndex always shows the next read position:

The following illustration shows the queue after we have retrieved the first four of the six elements:

Now that we are near the end of the array, we could (without additional logic) write only two more elements to the queue. To fill up the queue to eight elements again, there are two possible solutions:

1. We move the remaining elements to the left, to the beginning of the array. This operation is costly, especially for large arrays.
2. The better solution is a circular array. This means that when we reach the end of the array, we continue at its beginning. This applies to both the enqueue and dequeue operations.

Circular Array

To illustrate how a ring buffer works, I have rendered the array from the example as a circle:

We insert additional elements clockwise. In the following example, we add "mango", "fig", "pomelo", and "apricot" to positions 6, 7 – and then 0 and 1:

Back in the "flat" representation, the array now looks like this:

Both in the circle representation and this one, it is easy to see that the element "fig" at index 7 is followed by the element "pomelo" at index 0.

Dequeueing the elements works in the same way. With each dequeue operation,headIndex moves one position to the right, where 7 is not followed by 8 but by 0.

Full Queue vs. Empty Queue

tailIndex andheadIndex are in the same position for both an empty and a full queue. To be able to recognize when the queue is full, we also store the number of elements.

This is what a full queue might look like:

And so an empty one (e.g., after all eight elements have been taken from the queue just shown):

Storing the number of elements is not the only – but a very simple – way to distinguish a full queue from an empty one. Alternatives are, for example:

• Storing (besides the number of elements) only thetailIndexor theheadIndex; then calculating the other from the number of elements (this, however, makes the code much more complex).
• Not storing the number of elements and detecting a full queue by checking thattailIndex is equal toheadIndex and that the array does not contain any element at thetailIndex position.
• You do not fill the queue completely, but always leave at least one field empty.

Source Code for the Bounded Queue Using an Array

Implementing a bounded queue with an array is quite simple. You can also find the following code in theBoundedArrayQueue class in the GitHub repository.

publicclassBoundedArrayQueue<E>implementsQueue<E>{privatefinal Object[] elements;privateint headIndex;privateint tailIndex;privateint numberOfElements;publicBoundedArrayQueue(int capacity){if (capacity <1) {thrownew IllegalArgumentException("Capacity must be 1 or higher");    }    elements =new Object[capacity];  }@Overridepublicvoidenqueue(E element){if (numberOfElements == elements.length) {thrownew IllegalStateException("The queue is full");    }    elements[tailIndex] = element;    tailIndex++;if (tailIndex == elements.length) {      tailIndex =0;    }    numberOfElements++;  }@Overridepublic Edequeue(){final E element = elementAtHead();    elements[headIndex] =null;    headIndex++;if (headIndex == elements.length) {      headIndex =0;    }    numberOfElements--;return element;  }@Overridepublic Epeek(){return elementAtHead();  }private EelementAtHead(){if (isEmpty()) {thrownew NoSuchElementException();    }@SuppressWarnings("unchecked")    E element = (E) elements[headIndex];return element;  }@OverridepublicbooleanisEmpty(){return numberOfElements ==0;  }}Code language:Java(java)

Note thatBoundedArrayQueue doesnot implement thejava.util.Queue interface, but a custom one that defines only the four methodsenqueue(),dequeue(),peek(), andisEmpty() (seeQueue in the GitHub repository):

publicinterfaceQueue<E>{voidenqueue(E element);Edequeue();Epeek();booleanisEmpty();}Code language:Java(java)

Find out how to useBoundedArrayQueue (and all other implementations of theQueue interface) in theQueueDemo program.

Implementing an Unbounded Queue with an Array

Implementing an unbounded queue, i.e., a queue with no size limit, is somewhat more complex. An array cannot grow. And even if it did – it could not grow at the end but would have to create free space at precisely the location wheretailIndex andheadIndex are pointing.

Let's look again at the full queue from the end of the previous example:

To insert another element, we need to increase the queue's capacity by increasing the size of the array.

(For reasons of space in the graphical representation, we increase the capacity by only two elements. In reality, you usually find increases by a factor of 1.5 or 2.0).

However, we would have to create this free space between the tail and head of the queue, i.e., in the middle of the array:

This is not possible without further ado. An array cannot grow – and certainly not in the middle. Instead, we have to create a new array and copy the existing elements into it.

But if we have to recopy the elements anyway, we can copy them in the correct order to the beginning of the new array, like this:

The code for this is not that complicated, as you will see in the next section.

Source Code for the Unbounded Queue Using an Array

The following code shows theArrayQueue class from the tutorial GitHub repository.

There are two constructors: one that lets you specify the initial size of the array and a default constructor that sets the initial capacity to ten.

Each time theenqueue() method is called, it checks whether the array is full. If it is, it invokes thegrow() method.

Thegrow() method first callscalculateNewCapacity() to calculate the new size of the array. I have printed this method here in simplified form: it multiplies the current size by 1.5.

ThecalculateNewCapacity() method in the GitHub repository has a more sophisticated algorithm and ensures that a specific maximum size is not exceeded. However, the focus of this article should not be on determining the new size but on the actual expansion of the array.

Therefore, thegrowToNewCapacity() method creates the new array, copies the elements to the appropriate positions in the new array, and resetsheadIndex andtailIndex.

publicclassArrayQueue<E>implementsQueue<E>{privatestaticfinalint DEFAULT_INITIAL_CAPACITY =10;private Object[] elements;privateint headIndex;privateint tailIndex;privateint numberOfElements;publicArrayQueue(){this(DEFAULT_INITIAL_CAPACITY);  }publicArrayQueue(int capacity){if (capacity <1) {thrownew IllegalArgumentException("Capacity must be 1 or higher");    }    elements =new Object[capacity];  }@Overridepublicvoidenqueue(E element){if (numberOfElements == elements.length) {      grow();    }    elements[tailIndex] = element;    tailIndex++;if (tailIndex == elements.length) {      tailIndex =0;    }    numberOfElements++;  }privatevoidgrow(){int newCapacity = calculateNewCapacity(elements.length);    growToNewCapacity(newCapacity);  }privateintcalculateNewCapacity(int currentCapacity){return currentCapacity + currentCapacity /2;  }privatevoidgrowToNewCapacity(int newCapacity){    Object[] newArray =new Object[newCapacity];// Copy to the beginning of the new array: tailIndex to end of the old arrayint oldArrayLength = elements.length;int numberOfElementsAfterTail = oldArrayLength - tailIndex;    System.arraycopy(elements, tailIndex, newArray,0, numberOfElementsAfterTail);// Append to the new array: beginning to tailIndex of the old arrayif (tailIndex >0) {      System.arraycopy(elements,0, newArray, numberOfElementsAfterTail, tailIndex);    }// Adjust head and tail    headIndex =0;    tailIndex = oldArrayLength;    elements = newArray;  }// dequeue(), peek(), elementAtHead(), isEmpty() are the same as in BoundedArrayQueue}Code language:Java(java)

The methodsdequeue(),peek(),elementAtHead(), andisEmpty() are the same as in the BoundedArrayQueue from the section above. I have therefore not printed them again.

You may have noticed that the queue can grow but not shrink again. Perhaps our queue only needs to store a high number of elements during peak loads and would then occupy memory with a mostly empty array. We could extend the queue to copy its contents back to a smaller array after a certain grace period.

I leave this extension to you as a practice task.

Outlook

In the next and last part of this tutorial series, I will show youhow to implement a PriorityQueue yourself, based on a min-heap.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Thenclick here to sign up for the HappyCoders.eu newsletter.