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

We start with abounded deque, i.e., one with a fixed capacity, and then expand it to anunbounded 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 thebounded 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 bytailIndex; then, we incrementtailIndex 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 decreaseheadIndex by one and then store the element in the array field pointed to byheadIndex.

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 decreasetailIndex by one, read the array at positiontailIndex, and then set this field tonull.

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 positionheadIndex, set that field tonull, and incrementheadIndex 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, anddeque 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: increasetailIndex by 1; whentailIndex reaches 8, set it to 0.
• Enqueue at front: decreaseheadIndex by 1; ifheadIndex reaches -1, set it to 7.
• Deque at back: decreasetailIndex by 1; whentailIndex reaches -1, set it to 7.
• Deque at front: increaseheadIndex by 1; whenheadIndex reaches 8, set it to 0.

Indexes 8 and 7 apply to the example above. In general, we useelements.length instead of 8 andelement.length - 1 instead of 7.

Full Deque vs. Empty Deque

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

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

• We store the number of elements – andtailIndexorheadIndex. 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 donot store the number of elements and recognize an empty deque by the fact that – iftailIndex andheadIndex 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 thenumberOfElements 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 theBoundedArrayDeque class in the GitHub repository.

publicclassBoundedArrayDeque<E>implementsDeque<E>{privatefinal Object[] elements;privateint headIndex;privateint tailIndex;privateint numberOfElements;publicBoundedArrayDeque(int capacity){if (capacity <1) {thrownew IllegalArgumentException("Capacity must be 1 or higher");    }    elements =new Object[capacity];  }@OverridepublicvoidenqueueFront(E element){if (numberOfElements == elements.length) {thrownew IllegalStateException("The deque is full");    }    headIndex = decreaseIndex(headIndex);    elements[headIndex] = element;    numberOfElements++;  }@OverridepublicvoidenqueueBack(E element){if (numberOfElements == elements.length) {thrownew IllegalStateException("The deque is full");    }    elements[tailIndex] = element;    tailIndex = increaseIndex(tailIndex);    numberOfElements++;  }@Overridepublic EdequeueFront(){    E element = elementAtHead();    elements[headIndex] =null;    headIndex = increaseIndex(headIndex);    numberOfElements--;return element;  }@Overridepublic EdequeueBack(){    E element = elementAtTail();    tailIndex = decreaseIndex(tailIndex);    elements[tailIndex] =null;    numberOfElements--;return element;  }@Overridepublic EpeekFront(){return elementAtHead();  }@Overridepublic EpeekBack(){return elementAtTail();  }private EelementAtHead(){if (isEmpty()) {thrownew NoSuchElementException();    }@SuppressWarnings("unchecked")    E element = (E) elements[headIndex];return element;  }private EelementAtTail(){if (isEmpty()) {thrownew NoSuchElementException();    }@SuppressWarnings("unchecked")    E element = (E) elements[decreaseIndex(tailIndex)];return element;  }privateintdecreaseIndex(int index){    index--;if (index <0) {      index = elements.length -1;    }return index;  }privateintincreaseIndex(int index){    index++;if (index == elements.length) {      index =0;    }return index;  }@OverridepublicbooleanisEmpty(){return numberOfElements ==0;  }}Code language:Java(java)

Please note thatBoundedArrayDeque doesnot implement theDeque interface of the JDK, but a custom one that defines only the methodsenqueueFront(),enqueueBack(),dequeueFront(),dequeueBack(),peekFront(),peekBack(), andisEmpty() (seeDeque interface in the GitHub repository):

publicinterfaceDeque<E>{voidenqueueFront(E element);voidenqueueBack(E element);EdequeueFront();EdequeueBack();EpeekFront();EpeekBack();booleanisEmpty();}Code language:Java(java)

You can see how to useBoundedArrayDeque in theDequeDemo 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 endof the array but in the middleof 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.

TheenqueueFront() andenqueueBack() methods check whether the deque's capacity is reached. If so, they invoke thegrow() method. This, in turn, callscalculateNewCapacity() and thengrowToNewCapacity() to copy the elements into a new, larger array, as shown above.

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

publicclassArrayDeque<E>implementsDeque<E>{privatestaticfinalint DEFAULT_INITIAL_CAPACITY =10;private Object[] elements;privateint headIndex;privateint tailIndex;privateint numberOfElements;publicArrayDeque(){this(DEFAULT_INITIAL_CAPACITY);  }publicArrayDeque(int capacity){if (capacity <1) {thrownew IllegalArgumentException("Capacity must be 1 or higher");    }    elements =new Object[capacity];  }@OverridepublicvoidenqueueFront(E element){if (numberOfElements == elements.length) {      grow();    }    headIndex = decreaseIndex(headIndex);    elements[headIndex] = element;    numberOfElements++;  }@OverridepublicvoidenqueueBack(E element){if (numberOfElements == elements.length) {      grow();    }    elements[tailIndex] = element;    tailIndex = increaseIndex(tailIndex);    numberOfElements++;  }privatevoidgrow(){int newCapacity = calculateNewCapacity(elements.length);    growToNewCapacity(newCapacity);  }staticintcalculateNewCapacity(int currentCapacity){return currentCapacity + currentCapacity /2;  }privatevoidgrowToNewCapacity(int newCapacity){    Object[] newArray =new Object[newCapacity];// Copy to the beginning of the new array: from tailIndex to end of old arrayint 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 arrayif (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 theBoundedArrayDeque presented in the penultimate section. Therefore I have refrained from reprinting them here.

I have simplified thecalculateNewCapacity() method here compared to thecode 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.

OurArrayDeque 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 thedifferences between a deque and a stack, andbetween 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? Thenclick here to sign up for the HappyCoders.eu newsletter.