# Implement a Deque Using an Array

Sven Woltmann
Last update: 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:

### 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:

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:

### 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"):

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"):

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:

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:

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

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:

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:

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.