Implementing a Deque Using an Array - Feature ImageImplementing a Deque Using an Array - Feature Image
HappyCoders Glasses

Implement a Deque Using an Array

Sven Woltmann
Sven Woltmann
June 7, 2022

In this part of the tutorial series, I will show you how to implement a deque using an array – more precisely: with a circular array.

We start with a bounded deque, i.e., one with a fixed capacity, and then expand it to an unbounded deque, i.e., one that can hold an unlimited number of elements.

If you have read the article "Implementing a Queue Using an Array", many things will look familiar to you. That's because the deque implementation is an extension of the queue implementation.

Let's start with the bounded deque.

Implementing a Bounded Deque with an Array

We start with an empty array and two variables:

  • headIndex – points to the head of the deque, i.e., the element that would be taken next from the head of the deque
  • tailIndex – points to the field next to the end of the deque, i.e., the field that would be filled next at the end of the deque
  • numberOfElements – the number of elements in the deque

We first have the index variables point to the middle of the array so that we have enough space to add elements to both the head and the tail of the deque:

Implementing a deque with an array: empty deque
Implementing a deque with an array: empty deque

How the Enqueue Operations Work

To add an element to the end of the deque, we store it in the array field pointed to by tailIndex; then, we increment tailIndex by one.

The following image shows the deque after we have added the "banana" and "cherry" elements to its end:

Implementing a deque with an array: two elements added at the end
Implementing a deque with an array: two elements added at the end

To insert an element at the head of the deque, we decrease headIndex by one and then store the element in the array field pointed to by headIndex.

In the following image, you can see how the elements "grape", "lemon", and "coconut" (in this order) have been inserted at the head of the deque:

Implementing a deque with an array: two elements added at the head
Implementing a deque with an array: two elements added at the head

How the Dequeue Operations Work

To remove elements, we proceed in precisely the opposite way.

To take an element from the end of the deque, we decrease tailIndex by one, read the array at position tailIndex, and then set this field to null.

The following image shows the deque after we have taken three elements from its end ("cherry", "banana", "grape"):

Implementing a deque with an array: three elements removed from the end
Implementing a deque with an array: three elements removed from the end

To take an element from the head of the deque, we read the array at position headIndex, set that field to null, and increment headIndex by one.

The following image shows the deque after we have taken an element from its head ("coconut"):

Implementing a deque with an array: one element removed from the head
Implementing a deque with an array: one element removed from the head

With this, we have covered the four essential functions of a deque – enqueue at front, enqueue at back, deque at front, and deque at back.

However, we could (without additional logic) add only two more elements at the head of the deque, although only one of eight fields is occupied. Likewise, we could add a maximum of five elements to the end of the deque.

To be able to fill the deque up to its capacity (no matter in which direction), we have to make the array circular.

You will learn how this works in the next section.

Circular Array

To show how a circular array works, I've drawn the array from the previous example as a circle:

Deque implementiert mit einem Ringpuffer ("circular array") - 1 Element

To insert elements at the head of the deque, we write them counterclockwise into the array. The following example shows that the elements "mango", "fig", "pomelo", and "apricot" were inserted at positions 1, 0, 7, and 6:

Deque implementiert mit einem Ringpuffer ("circular array") - 5 Elemente

If we display the array "flat" again, it looks like this. For clarity, I added an arrow at the head of the deque.

Deque with "flat" representation of the ring buffer
Deque with "flat" representation of the ring buffer

In both representations, it is easy to see that the element "pomelo" at index 7 precedes the element "fig" at index 0.

Similarly, we insert and remove elements at the end of the deque. In summary, we perform the operations as follows:

  • Enqueue at back: increase tailIndex by 1; when tailIndex reaches 8, set it to 0.
  • Enqueue at front: decrease headIndex by 1; if headIndex reaches -1, set it to 7.
  • Deque at back: decrease tailIndex by 1; when tailIndex reaches -1, set it to 7.
  • Deque at front: increase headIndex by 1; when headIndex reaches 8, set it to 0.

Indexes 8 and 7 apply to the example above. In general, we use elements.length instead of 8 and element.length - 1 instead of 7.

Full Deque vs. Empty Deque

For both a full and an empty deque, tailIndex and headIndex point to the same array field. To detect whether the deque is full or empty, we also store the number of elements in numberOfElements.

There are other ways to distinguish a full deque from an empty one:

  • We store the number of elements – and tailIndex or headIndex. We can then calculate the other index by adding or subtracting the number of elements. This variant leads to more complex and less readable code.
  • We do not store the number of elements and recognize an empty deque by the fact that – if tailIndex and headIndex are equal – the array is empty at that position.
  • We do not fill the deque completely but leave at least one field empty. We waste one array field but save the storage space for the numberOfElements variable.

Source Code for the Bounded Deque Using an Array

The implementation of the algorithm described above is not complicated, as you will see in the following sample code. You can find the code in the BoundedArrayDeque class in the GitHub repository.

public class BoundedArrayDeque<E> implements Deque<E> { private final Object[] elements; private int headIndex; private int tailIndex; private int numberOfElements; public BoundedArrayDeque(int capacity) { if (capacity < 1) { throw new IllegalArgumentException("Capacity must be 1 or higher"); } elements = new Object[capacity]; } @Override public void enqueueFront(E element) { if (numberOfElements == elements.length) { throw new IllegalStateException("The deque is full"); } headIndex = decreaseIndex(headIndex); elements[headIndex] = element; numberOfElements++; } @Override public void enqueueBack(E element) { if (numberOfElements == elements.length) { throw new IllegalStateException("The deque is full"); } elements[tailIndex] = element; tailIndex = increaseIndex(tailIndex); numberOfElements++; } @Override public E dequeueFront() { E element = elementAtHead(); elements[headIndex] = null; headIndex = increaseIndex(headIndex); numberOfElements--; return element; } @Override public E dequeueBack() { E element = elementAtTail(); tailIndex = decreaseIndex(tailIndex); elements[tailIndex] = null; numberOfElements--; return element; } @Override public E peekFront() { return elementAtHead(); } @Override public E peekBack() { return elementAtTail(); } private E elementAtHead() { if (isEmpty()) { throw new NoSuchElementException(); } @SuppressWarnings("unchecked") E element = (E) elements[headIndex]; return element; } private E elementAtTail() { if (isEmpty()) { throw new NoSuchElementException(); } @SuppressWarnings("unchecked") E element = (E) elements[decreaseIndex(tailIndex)]; return element; } private int decreaseIndex(int index) { index--; if (index < 0) { index = elements.length - 1; } return index; } private int increaseIndex(int index) { index++; if (index == elements.length) { index = 0; } return index; } @Override public boolean isEmpty() { return numberOfElements == 0; } }
Code language: Java (java)

Please note that BoundedArrayDeque does not implement the Deque interface of the JDK, but a custom one that defines only the methods enqueueFront(), enqueueBack(), dequeueFront(), dequeueBack(), peekFront(), peekBack(), and isEmpty() (see Deque interface in the GitHub repository):

public interface Deque<E> { void enqueueFront(E element); void enqueueBack(E element); E dequeueFront(); E dequeueBack(); E peekFront(); E peekBack(); boolean isEmpty(); }
Code language: Java (java)

You can see how to use BoundedArrayDeque in the DequeDemo demo program.

Implementing an Unbounded Deque with an Array

If our deque is not to be size limited, i.e., unbounded, it gets a bit more complicated. That's because we need to grow the array. Since that is not possible directly, we have to create a new, larger array and copy the existing elements over to it.

We have to take into account the circular character of the array. That is, we cannot simply copy the elements to the beginning of the new array.

The following image (I extended the deque from the previous example by adding the elements "papaya" at the tail and "melon" and "kiwi" at the head) shows what would happen:

Extending a deque: Copying to a new array – not like this!
Copying to a new array – not like this!

The empty fields are at the end of the array but in the middle of the deque.

Therefore, when copying to the new array, we must either copy the right elements (the left part of the deque) to the right edge of the new array. Or we copy the right elements to the beginning of the new array and the left elements (the right part of the deque) next to it.

The following illustration shows the second strategy, which is easier to implement in code:

Extending a deque: Copying into a new array with reallocation
Copying into a new array with reallocation

Thus, the empty fields are in front of the first element ("kiwi") or behind the last element ("papaya"), and we can insert new elements on both sides.

Source Code for an Unbounded Deque Using an Array

The following is the code for a circular array-based, unbounded deque.

The class has two constructors: one where you can pass the initial capacity of the deque as a parameter – and a default constructor that sets the initial capacity to ten elements.

The enqueueFront() and enqueueBack() methods check whether the deque's capacity is reached. If so, they invoke the grow() method. This, in turn, calls calculateNewCapacity() and then growToNewCapacity() to copy the elements into a new, larger array, as shown above.

You can find the code in the ArrayDeque class in the GitHub repository.

public class ArrayDeque<E> implements Deque<E> { private static final int DEFAULT_INITIAL_CAPACITY = 10; private Object[] elements; private int headIndex; private int tailIndex; private int numberOfElements; public ArrayDeque() { this(DEFAULT_INITIAL_CAPACITY); } public ArrayDeque(int capacity) { if (capacity < 1) { throw new IllegalArgumentException("Capacity must be 1 or higher"); } elements = new Object[capacity]; } @Override public void enqueueFront(E element) { if (numberOfElements == elements.length) { grow(); } headIndex = decreaseIndex(headIndex); elements[headIndex] = element; numberOfElements++; } @Override public void enqueueBack(E element) { if (numberOfElements == elements.length) { grow(); } elements[tailIndex] = element; tailIndex = increaseIndex(tailIndex); numberOfElements++; } private void grow() { int newCapacity = calculateNewCapacity(elements.length); growToNewCapacity(newCapacity); } static int calculateNewCapacity(int currentCapacity) { return currentCapacity + currentCapacity / 2; } private void growToNewCapacity(int newCapacity) { Object[] newArray = new Object[newCapacity]; // Copy to the beginning of the new array: from tailIndex to end of old array int oldArrayLength = elements.length; int numberOfElementsAfterTail = oldArrayLength - tailIndex; System.arraycopy(elements, tailIndex, newArray, 0, numberOfElementsAfterTail); // Append to the new array: from beginning to tailIndex of old array if (tailIndex > 0) { System.arraycopy(elements, 0, newArray, numberOfElementsAfterTail, tailIndex); } // Adjust head and tail headIndex = 0; tailIndex = oldArrayLength; elements = newArray; } // The remaining methods are the same as in BoundedArrayDeque: // - dequeFront(), dequeBack(), // - peekFront(), peekBack(), // - elementAtHead(), elementAtTail(), // - decreaseIndex(), increaseIndex(), isEmpty() }
Code language: Java (java)

The methods listed in the comments at the end of the source code are identical to those of the BoundedArrayDeque presented in the penultimate section. Therefore I have refrained from reprinting them here.

I have simplified the calculateNewCapacity() method here compared to the code on GitHub. The method in the repository doubles the array size as long as it is shorter than 64 elements; after that, it only increases it by a factor of 1.5. Furthermore, the method checks whether a maximum size for arrays has been reached.

Our ArrayDeque now grows as soon as its capacity is no longer sufficient for a new element.

What it can't do is shrink again when lots of elements have been removed, and a large amount of the array fields are no longer needed. I will leave such an extension to you as a practice task.

Summary and Outlook

In today's part of the tutorial series, you have implemented a deque with an array (more precisely: with a circular array). Feel free to check out the article "Implementing a Queue Using an Array" – there, you will find a similar implementation for a queue.

In the two upcoming parts of the deque series, I will summarize the differences between a deque and a stack, and between a deque and a queue.

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