Classe Java ArrayDeque | W3Docs Learn Java

ArrayDeque<E> est un tableau circulaire qui s'agrandit à la demande. Il implémente à la fois Queue<E> et Deque<E>, ce qui lui permet de jouer le rôle de file FIFO, de pile LIFO ou de file à double extrémité sans modifier le code. La Javadoc de Stack recommande Deque plutôt que la classe héritée ; la Javadoc de Deque ajoute la recommandation pratique qu'ArrayDeque devrait être votre implémentation par défaut. Il est presque toujours plus rapide que LinkedList, plus économe en mémoire, et c'est la référence de la bibliothèque standard dès lors qu'on n'a plus besoin de l'interface List.

Pourquoi un tableau circulaire

Une « file construite à partir d'un tableau » classique rencontre un problème : après quelques cycles d'ajout en queue et de suppression en tête, le tableau se remplit du côté de la queue tandis que des emplacements vides s'accumulent du côté de la tête. Une solution naïve consisterait à décaler tout vers la gauche à chaque retrait — O(n) par suppression, ce qui ruine les performances.

L'astuce du tableau circulaire résout ce problème. La classe conserve deux indices, head et tail, et les laisse se reboucler :

slots:   [ . . . D E F G H A B C ]
                         ^head     ^... wraps to slot 0 ... ^tail

addFirst décrémente head, addLast incrémente tail, tous deux modulo la longueur du tableau. removeFirst et removeLast font l'inverse. Chaque opération est O(1) ; le seul coût est de doubler le tableau de support quand head entrerait en collision avec tail, ce qui est amorti sur l'ensemble des opérations.

Résultat : pas d'allocation par élément de nœud, pas de chaînage de pointeurs, accès favorable au cache. C'est la raison d'ingénierie pour laquelle ArrayDeque est généralement le choix le plus rapide pour les charges de travail de file et de pile.

Rappel sur l'interface Deque

Un Deque possède deux extrémités. Chaque opération existe en trois variantes :

Opération	Première (tête) — exception	Première (tête) — valeur spéciale	Dernière (queue) — exception	Dernière (queue) — valeur spéciale
Insertion	`addFirst(e)`	`offerFirst(e)`	`addLast(e)`	`offerLast(e)`
Suppression	`removeFirst()`	`pollFirst()`	`removeLast()`	`pollLast()`
Examen	`getFirst()`	`peekFirst()`	`getLast()`	`peekLast()`

De plus, les synonymes de Queue et de pile se mappent sur l'extrémité tête :

Méthode Queue	Équivalent Deque
`add(e)` / `offer(e)`	`addLast(e)` / `offerLast(e)`
`remove()` / `poll()`	`removeFirst()` / `pollFirst()`
`element()` / `peek()`	`getFirst()` / `peekFirst()`

Méthode Stack	Équivalent Deque
`push(e)`	`addFirst(e)`
`pop()`	`removeFirst()`
`peek()`	`peekFirst()`

Ainsi, Deque est une interface unique qui expose à la fois une file et une pile, selon le nom sous lequel vous appelez l'extrémité tête. Nous avons couvert ces correspondances dans les chapitres Queue et Stack ; Deque est l'endroit où ils se rejoignent.

Ce qu'`ArrayDeque` ajoute en plus

En pratique, très peu de choses au niveau de l'API — c'est justement l'objectif. La classe expose honnêtement le contrat Deque : les deux extrémités, les trois styles d'erreur par opération, ainsi que clear(), iterator(), descendingIterator(), contains, size, isEmpty. L'itération avec l'itérateur standard se fait de la tête vers la queue ; descendingIterator est le moyen économique de parcourir de la queue vers la tête sans inverser.

Les constructeurs reflètent ceux d'ArrayList :

Deque<String> a = new ArrayDeque<>();          // initial capacity 16
Deque<String> b = new ArrayDeque<>(1_000);     // pre-sized
Deque<String> c = new ArrayDeque<>(other);     // from any Collection (head = first iter element)

Pré-dimensionnez lorsque vous connaissez la charge de travail. La valeur par défaut de 16 est arrondie à la puissance de deux supérieure, et la croissance double le tableau — ainsi, un million d'appels à offerLast à partir d'un deque de taille par défaut déclenche environ 16 opérations d'agrandissement et de copie.

Les règles : pas de null, non thread-safe, fail-fast

Trois règles à intérioriser :

ArrayDeque n'autorise pas les éléments null. Chaque insertion lève NullPointerException. C'est ainsi que pollFirst() retournant null pour une file vide reste sans ambiguïté.
Non thread-safe. Deux threads modifiant le même ArrayDeque le corromperont. Pour un usage concurrent, consultez ConcurrentLinkedDeque (sans verrou, non borné) ou LinkedBlockingDeque (borné, bloquant).
Itération fail-fast. Modifier le deque en dehors de l'itérateur pendant l'itération lève ConcurrentModificationException. Utilisez Iterator.remove() ou removeIf pour une mutation sécurisée.

Quand choisir `ArrayDeque` plutôt que les alternatives

Arbre de décision :

Besoin d'une Queue ? → ArrayDeque. Par défaut.
Besoin d'une pile ? → ArrayDeque. Par défaut. Utilisez push / pop / peek.
Besoin d'un Deque ? → ArrayDeque. Par défaut.
Besoin à la fois de sémantiques Deque et List sur le même objet ? → LinkedList. Rare.
Besoin d'un ordre de priorité ? → PriorityQueue. Abstraction différente.
Besoin d'un accès concurrent ? → ConcurrentLinkedDeque (non borné) ou LinkedBlockingDeque (borné). Le bon choix dépend de si vous avez besoin de contre-pression.

La Javadoc l'énonce clairement en texte simple : « Cette classe est susceptible d'être plus rapide que Stack lorsqu'elle est utilisée comme pile, et plus rapide que LinkedList lorsqu'elle est utilisée comme file. » C'est écrit directement par les auteurs du JDK ; cela mérite d'être pris à la lettre.

Un exemple concret : file, pile, deque, fenêtre glissante

Le programme ci-dessous utilise une instance d'ArrayDeque comme file FIFO, une autre comme pile LIFO, et une troisième comme support d'un maximum de fenêtre glissante — un problème classique pour lequel ArrayDeque est la réponse de référence car on a besoin d'une mutation peu coûteuse aux deux extrémités.

java— editable, runs on the server

import java.util.*;

public class ArrayDequeShowcase {
  public static void main(String[] args) {
    // --- 1. FIFO queue ---
    Deque<String> queue = new ArrayDeque<>();
    queue.offerLast("a"); queue.offerLast("b"); queue.offerLast("c");
    System.out.println("FIFO order:  poll=" + queue.pollFirst()
        + " poll=" + queue.pollFirst()
        + " poll=" + queue.pollFirst());

// --- 2. LIFO stack ---
    Deque<String> stack = new ArrayDeque<>();
    stack.push("a"); stack.push("b"); stack.push("c");
    System.out.println("LIFO order:  pop=" + stack.pop()
        + " pop=" + stack.pop()
        + " pop=" + stack.pop());

// --- 3. Iteration: head-to-tail vs descending ---
    Deque<Integer> ints = new ArrayDeque<>(List.of(1, 2, 3, 4, 5));
    System.out.print("forward:  "); ints.forEach(x -> System.out.print(x + " "));
    System.out.println();
    System.out.print("reverse:  ");
    Iterator<Integer> r = ints.descendingIterator();
    while (r.hasNext()) System.out.print(r.next() + " ");
    System.out.println();

// --- 4. Null rejection ---
    try { ints.offerLast(null); }
    catch (NullPointerException e) {
      System.out.println("offerLast(null) → " + e.getClass().getSimpleName());
    }

// --- 5. Sliding window maximum — the canonical ArrayDeque algorithm ---
    int[] xs = { 1, 3, -1, -3, 5, 3, 6, 7 };
    int k = 3;
    System.out.println("\nsliding window max, k=" + k + ", input=" + Arrays.toString(xs));
    System.out.println("output=" + Arrays.toString(slidingMax(xs, k)));
  }

// O(n) algorithm: deque holds indices, kept in decreasing order of xs[i].
  // Push at the tail, pop from the head when out of window — both O(1).
  static int[] slidingMax(int[] xs, int k) {
    int[] out = new int[xs.length - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();
    for (int i = 0; i < xs.length; i++) {
      while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
      while (!dq.isEmpty() && xs[dq.peekLast()] < xs[i]) dq.pollLast();
      dq.offerLast(i);
      if (i >= k - 1) out[i - k + 1] = xs[dq.peekFirst()];
    }
    return out;
  }
}

Ce qu'on peut retenir de cette exécution :

Les sections 1 et 2 utilisent la même classe pour deux usages distincts en appelant des méthodes différentes. File FIFO : offerLast / pollFirst. Pile LIFO : push / pop. Il n'y a pas de classe séparée à apprendre.
descendingIterator() est le parcours inverse économique — utile quand vous avez construit un deque comme une pile et souhaitez l'afficher du bas vers le haut.
La fonction de fenêtre glissante utilise les deux extrémités dans la même boucle — pollFirst pour supprimer les indices sortis de la fenêtre, pollLast pour maintenir une pile décroissante monotone, peekFirst pour lire le maximum courant. Cet accès aux deux extrémités est la raison d'être d'ArrayDeque ; tenter de faire cela avec un ArrayList serait quadratique.

Et ensuite

Vous avez vu comment ArrayDeque implémente les deux extrémités de la relation file/pile. L'interface qu'il implémente depuis le début mérite son propre chapitre — Deque est le contrat qui rassemble tout ce que nous avons couvert pour les collections de type file. Nous aborderons cela à la prochaine session.

Pratique

Vous avez besoin d'une pile LIFO rapide de tokens `String` et vous savez que vous devrez itérer le contenu du bas vers le haut pour le débogage. Quelle déclaration correspond à la recommandation moderne ?

`Deque<String> tokens = new ArrayDeque<>();` puis `push`/`pop`/`peek`, et `descendingIterator()` pour parcourir du bas vers le haut en O(n)`Stack<String> tokens = new Stack<>();` — la classe dédiée exprime l'intention et supporte `get(0)` pour accéder au bas`List<String> tokens = new LinkedList<>();` avec `add(0, x)` et `remove(0)` pour push/pop`PriorityQueue<String> tokens = new PriorityQueue<>(Comparator.reverseOrder());` — l'ordre inverse la fait se comporter comme une pile