ArrayDeque

Question 1

ArrayDeque Overview

Answer 1

We will learn about Java’s ArrayDeque class – which is an implementation of Deque interface.

An ArrayDeque (also known as an “Array Double Ended Queue”, pronounced as “ArrayDeck”) is a special kind of a growable array that allows us to add or remove an element from both sides.

An ArrayDeque implementation can be used as a Stack (Last-In-First-Out) or a Queue(First-In-First-Out).

Question 2

ArrayDeque The API at a Glance

Answer 2

For each operation, we basically have two options.

The first group consists of methods that throw exception if the operation fails.
The other group returns a status or a value.

Poll & Offer first/last do not throw exception.

Remove & Add first/last do throw exception.

Operations,

Insertion from Head,
offerFirst(e) addFirst(e)

Removal from Head pollFirst() removeFirst()

Retrieval from Head peekFirst() getFirst()

Insertion from Tail offerLast(e) addLast(e)

Removal from Tail pollLast() removeLast()

Retrieval from Tail peekLast() getLast()

Question 3

Using ArrayDeque as a Stack

Answer 3

We’ll start with an example of how we can treat the class as a Stack – and push an element:

@Test
public void whenPush_addsAtFirst() {
    Deque stack = new ArrayDeque<>();
    stack.push("first");
    stack.push("second");

assertEquals("second", stack.getFirst()); } Let’s also see how we can pop an element from the ArrayDeque – when used as a Stack:

@Test
public void whenPop_removesLast() {
    Deque stack = new ArrayDeque<>();
    stack.push("first");
    stack.push("second");

assertEquals("second", stack.pop()); } The pop method throws NoSuchElementException when a stack is empty.

Question 4

Using ArrayDeque as a Queue

Answer 4

Let’s now start with a simple example showing how we can offer an element in an ArrayDeque – when used as a simple Queue:

@Test
public void whenOffer_addsAtLast() {
    Deque queue = new ArrayDeque<>();
    queue.offer("first");
    queue.offer("second");

assertEquals("second", queue.getLast()); } And let’s see how we can poll an element from an ArrayDeque, also when used as a Queue:

@Test
public void whenPoll_removesFirst() {
    Deque queue = new ArrayDeque<>();
    queue.offer("first");
    queue.offer("second");

assertEquals("first", queue.poll()); } The poll method returns a null value if a queue is empty.

Question 5

Notes on ArrayDeque

Answer 5

Finally, a few more notes worth understanding and remembering about this particular implementation:

It’s not thread-safe
Null elements are not accepted
Works significantly faster than the synchronized Stack
Is a faster queue than LinkedList due to the better locality of reference
Most operations have amortized constant time complexity
An Iterator returned by an ArrayDeque is fail-fast
ArrayDeque automatically doubles the size of an array when head and tail pointer meets each other while adding an element

Question 6

ArrayDeque Code

Answer 6

Pending.