Introduction to the Java ArrayDeque

1. Overview

In this tutorial, we’ll show how to use the 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).

2. The API at a Glance

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:

OperationMethodMethod throwing Exception
Insertion from HeadofferFirst(e)addFirst(e)
Removal from HeadpollFirst()removeFirst()
Retrieval from HeadpeekFirst()getFirst()
Insertion from TailofferLast(e)addLast(e)
Removal from TailpollLast()removeLast()
Retrieval from TailpeekLast()getLast()

3. Using Methods

Let’s look at a few simple example of how we can make use of the ArrayDeque.

3.1. Using ArrayDeque as a Stack

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<String> 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<String> stack = new ArrayDeque<>();
    stack.push("first");
    stack.push("second");
 
    assertEquals("second", stack.pop());
}

The pop method throws NoSuchElementException when a stack is empty.

3.2. Using ArrayDeque as a Queue

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<String> 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<String> 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.

4. How’s ArrayDeque Implemented


Under the hood, the ArrayDeque is backed by an array which doubles its size when it gets filled.

Initially, the array is initialized with a size of 16. It’s implemented as a double-ended queue where it maintains two pointers namely a head and a tail.

Let’s see this logic in action – at a high level.

4.1. ArrayDeque as Stack


As can be seen, when a user adds in an element using the push method, it moves the head pointer by one.

When we pop an element, it sets the element at the head position as null so the element could be garbage collected, and then moves back the head pointer by one.

4.2. ArrayDeque as a Queue


When we add in an element using the offer method, it moves the tail pointer by one.

While when user polls an element, it sets the element at the head position to null so the element could be garbage collected, and then moves the head pointer.

4.3. Notes on ArrayDeque

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

5. Conclusion

In this short article, we illustrated the usage of methods in ArrayDeque.

The implementation of all these examples can be found in the GitHub project; this is a Maven-based project, so it should be easy to import and run as is.

Related posts:

Java Program to Test Using DFS Whether a Directed Graph is Strongly Connected or Not
HttpClient Timeout
Java Program to Create a Minimal Set of All Edges Whose Addition will Convert it to a Strongly Conne...
Tránh lỗi NullPointerException trong Java như thế nào?
Java Program to Implement Patricia Trie
Thao tác với tập tin và thư mục trong Java
Java – Rename or Move a File
Spring Boot - Application Properties
Hướng dẫn Java Design Pattern – State
Java Program to Implement Sieve Of Eratosthenes
Converting a Stack Trace to a String in Java
Java Program to Perform Postorder Recursive Traversal of a Given Binary Tree
Cachable Static Assets with Spring MVC
Merging Two Maps with Java 8
Configuring a DataSource Programmatically in Spring Boot
How to Convert List to Map in Java
Quick Guide to @RestClientTest in Spring Boot
Hướng dẫn sử dụng Java Reflection
Java Program to Implement Hamiltonian Cycle Algorithm
Java Program to Implement Pollard Rho Algorithm
Call Methods at Runtime Using Java Reflection
Java Program to Implement CopyOnWriteArrayList API
Anonymous Classes in Java
Java Program to Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself
Java Program to Implement Direct Addressing Tables
Returning Custom Status Codes from Spring Controllers
Spring Boot - Runners
Spring Boot - Logging
Spring Data JPA Delete and Relationships
Introduction to Liquibase Rollback
Java Program to Find k Numbers Closest to Median of S, Where S is a Set of n Numbers
Check If Two Lists are Equal in Java

1 Trackback / Pingback

  1. Data Structure and Types - VietMX's Blog

Comments are closed.