Deque and ArrayDeque

A Deque is a double-ended queue: elements go in and come out at both ends, in constant time. That one interface is both the queue a breadth-first search uses and the stack that a depth-first search uses, and ArrayDeque implements it over a circular array. The names of the methods are the part to learn, because the same operation has two of them, one that throws on an empty deque and one that answers null or false.

A queue with offer and poll

A queue is first in, first out. offer adds at the tail, poll removes from the head and returns it, and peek reads the head without removing it:

import java.util.ArrayDeque; import java.util.Deque; public class Queue { public static void main(String[] args) { Deque<String> queue = new ArrayDeque<>(); queue.offer("first"); queue.offer("second"); queue.offer("third"); System.out.println(queue); System.out.println(queue.peek()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue); System.out.println(queue.size()); } }

javac -Xlint:all Queue.java
java Queue

[first, second, third]
first
first
second
[third]
1

The first line is the deque printed head first, which is the order toString uses. peek answers first and leaves it, the two poll calls take the first two, and one element is left. The same four operations are the whole of a breadth-first search, with the neighbours of a node offered as it is polled.

A stack with push and pop

The same class used from the other end is a stack, last in, first out. push is addFirst and pop is removeFirst, so the newest element is at the head:

import java.util.ArrayDeque; import java.util.Deque; public class Stack { public static void main(String[] args) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack); System.out.println(stack.peek()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack); } }

javac -Xlint:all Stack.java
java Stack

[3, 2, 1]
3
3
2
[1]

The print shows the stack top first, so three elements pushed in the order 1, 2, 3 print as [3, 2, 1]. That is the order the internal array has, not a reversal by the print. The two pops take 3 and then 2, and the first element is left, which is the last-in-first-out rule.

An empty deque

Every operation has two forms. poll, peek, offer and removeFirst's nullable cousin answer null or false when the deque is empty. remove, pop, element and add throw:

import java.util.ArrayDeque; import java.util.Deque; import java.util.NoSuchElementException; public class Empty { public static void main(String[] args) { Deque<String> deque = new ArrayDeque<>(); System.out.println(deque.poll()); System.out.println(deque.peek()); try { deque.remove(); } catch (NoSuchElementException e) { System.out.println("remove: " + e.getClass().getSimpleName()); } try { deque.pop(); } catch (NoSuchElementException e) { System.out.println("pop: " + e.getClass().getSimpleName()); } } }

javac -Xlint:all Empty.java
java Empty

null
null
remove: NoSuchElementException
pop: NoSuchElementException

An ArrayDeque does not accept null elements, so a poll that answers null can only mean the deque is empty; that is why the class refuses null in the first place. A loop that reads until the deque is empty uses while ((item = queue.poll()) != null), and a loop that must not treat empty as an error uses the throwing form inside a try.

A deque at both ends

A palindrome is the classic use of both ends: push the characters into the deque, then compare the first and the last until one or none is left. The same class also reverses a word by pushing every character and popping them out:

import java.util.ArrayDeque; import java.util.Deque; public class Palindrome { public static void main(String[] args) { for (String word : new String[] {"level", "radar", "java", "ab"}) { System.out.println(word + " " + isPalindrome(word)); } System.out.println(reverse("deque")); } static boolean isPalindrome(String word) { Deque<Character> chars = new ArrayDeque<>(); for (char c : word.toCharArray()) { chars.addLast(c); } while (chars.size() > 1) { if (!chars.removeFirst().equals(chars.removeLast())) { return false; } } return true; } static String reverse(String word) { Deque<Character> chars = new ArrayDeque<>(); for (char c : word.toCharArray()) { chars.push(c); } StringBuilder builder = new StringBuilder(); while (!chars.isEmpty()) { builder.append(chars.pop()); } return builder.toString(); } }

javac -Xlint:all Palindrome.java
java Palindrome

level true
radar true
java false
ab false
euqed

java fails at the first pair, j against a, and the method returns before it has read the whole word. The reverse of deque is euqed, which is the same push-and-pop pattern of the stack above, on characters.

Deque, Stack and LinkedList

java.util.Stack still exists and should not be used in new code: it extends Vector, so every method is synchronised, and its iterator walks the stack from the bottom. The documentation of Deque says to use ArrayDeque instead.

LinkedList also implements Deque, so it can be a queue or a stack as well. It allocates a node per element where ArrayDeque uses one array, so it is slower and larger for the same operations, and lesson 069 measured the same difference for lists. The choice in practice is ArrayDeque unless the list is also used by index.

Exercises

  1. Use a Deque as a queue in a loop that prints its elements until it is empty.
  2. Check a sentence for a palindrome, ignoring spaces.
  3. Reverse the order of the words of a sentence with a deque of strings.
  4. Call element on an empty deque and print the exception.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Which method removes the head of a queue and answers null when it is empty?

    Answer

    poll

    The nullable form is poll; remove and pop throw on an empty deque.

  2. Which end does push add to?

    Answer

    The head, as addFirst

    push and pop work on the head, which is what makes the deque a stack.

  3. Why does ArrayDeque refuse null elements?

    Answer

    So that a null from poll or peek can only mean the deque is empty

    The nullable methods use null as the empty answer, so null must not be a value.

  4. What does this program print? import java.util.ArrayDeque; import java.util.Deque; public class Q1 { public static void main(String[] args) { Deque<Integer> d = new ArrayDeque<>(); d.offer(1); d.offer(2); d.offer(3); System.out.println(d.poll()); System.out.println(d.peek()); System.out.println(d.size()); } }

    Answer

    1 / 2 / 2

    A queue takes one from the head, then peeks the next, and two are left.

  5. What does this program print? import java.util.ArrayDeque; import java.util.Deque; public class Q2 { public static void main(String[] args) { Deque<String> d = new ArrayDeque<>(); d.push("a"); d.push("b"); System.out.println(d.pop()); System.out.println(d.pop()); } }

    Answer

    b / a

    The last push is at the head, so it comes out first.

  6. What does this program print? import java.util.ArrayDeque; import java.util.Deque; public class Q3 { public static void main(String[] args) { Deque<String> d = new ArrayDeque<>(); System.out.println(d.poll()); System.out.println(d.isEmpty()); } }

    Answer

    null / true

    poll answers null on an empty deque and leaves it empty.

  7. What does this program print? import java.util.ArrayDeque; import java.util.Deque; public class Q4 { public static void main(String[] args) { Deque<Integer> d = new ArrayDeque<>(); d.addLast(1); d.addLast(2); d.addFirst(0); System.out.println(d); } }

    Answer

    [0, 1, 2]

    The first element goes to the head and the last two to the tail, in order.

  8. What does this program print? import java.util.ArrayDeque; import java.util.Deque; public class Q5 { public static void main(String[] args) { Deque<String> d = new ArrayDeque<>(); try { d.pop(); } catch (RuntimeException e) { System.out.println("caught"); } } }

    Answer

    caught

    NoSuchElementException is a RuntimeException, so the catch takes it.

  9. Which class is the modern replacement for Stack?

    Answer

    ArrayDeque

    Stack extends Vector and is synchronised and slow; the Deque documentation names ArrayDeque.

  10. What is the cost of adding at either end of an ArrayDeque?

    Answer

    Constant time, because the array is circular

    The circular buffer wraps around, so both ends are available without a shift.

The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.

Article author: Arthur Isaev