Interface Java Deque | W3Docs Learn Java

Deque<E> — prononcé « deck », abréviation de double-ended queue (file à double extrémité) — est une Queue<E> avec une seconde extrémité. Là où une Queue ne permet de retirer que depuis la tête, une Deque permet d'insérer, de retirer et d'examiner les éléments aux deux extrémités, tête et queue. Cette unique capacité supplémentaire suffit à faire de Deque le contrat qui sous-tend deux abstractions totalement différentes : c'est une file, c'est une pile, et le JDK la recommande comme choix par défaut pour les deux.

Deux extrémités × trois opérations × deux styles d'erreur

L'interface peut sembler intimidante au premier abord, car chaque opération apparaît en douze variantes — tête ou queue, insertion ou suppression ou examen, exception ou valeur spéciale. Mais ce n'est que la grille 3×2 de Queue étendue sur deux extrémités :

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

La colonne « exception » est celle à utiliser quand une file vide ou pleine à ce stade serait un bogue. La colonne « valeur spéciale » est celle à utiliser quand un état vide est attendu et que vous souhaitez tester cette condition dans une boucle.

La correspondance avec Queue

Deque étend Queue, donc une Deque est une Queue. Les méthodes héritées sont des alias pour les variantes tête-vers-queue :

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

Insérer à la queue, retirer depuis la tête — c'est la discipline FIFO qu'une Queue vous offre déjà, simplement formulée avec les noms explicites des extrémités.

La correspondance avec la pile

Deque définit également trois méthodes « pile » qui agissent toutes sur la tête :

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

Empiler, dépiler — discipline LIFO, même tête, extrémité opposée à celle de l'insertion/suppression par rapport à la correspondance avec la file. C'est pourquoi le chapitre sur Stack vous renvoie ici : la façon moderne d'écrire une pile en Java est Deque<E> stack = new ArrayDeque<>(); puis d'appeler push / pop / peek.

La règle : null n'est pas autorisé

Comme Queue, le contrat Deque réserve null comme sentinelle « vide » pour pollFirst, pollLast, peekFirst, peekLast. Ainsi, toutes les implémentations Deque à usage général du JDK rejettent les éléments null avec NullPointerException à l'insertion. La seule exception est LinkedList, qui autorise null pour des raisons historiques — et hérite de toute l'ambiguïté qui en découle. Ne faites pas ça.

Itération et itération inverse

Une Deque possède deux itérateurs par convention :

iterator() parcourt de la tête vers la queue — l'ordre dans lequel vous appelleriez pollFirst répétitivement.
descendingIterator() parcourt de la queue vers la tête — l'ordre dans lequel vous appelleriez pollLast répétitivement.

Les deux sont généralement fail-fast : modifier la deque depuis l'extérieur de l'itérateur pendant l'itération lève une ConcurrentModificationException. Utilisez Iterator.remove() ou removeIf si vous devez muter pendant un parcours.

Choisir une implémentation

En code monothread, il y a essentiellement deux choix :

ArrayDeque — le choix par défaut. Tableau circulaire, O(1) aux deux extrémités, pas d'allocation de nœud par élément, cache-friendly. Rejette null. Implémente Deque et Queue.
LinkedList — nœuds doublement chaînés. Implémente aussi List, donc chaque élément obtient un nœud avec des pointeurs prev/next. Plus lente aux deux extrémités que ArrayDeque et utilise davantage de mémoire. À choisir uniquement si vous avez réellement besoin de la sémantique Deque et List sur le même objet.

Pour le code concurrent (traité plus loin dans la partie concurrence du livre) :

ConcurrentLinkedDeque — sans verrou, non borné.
LinkedBlockingDeque — optionnellement borné, bloquant — la version à utiliser pour construire une file de work-stealing ou un producteur/consommateur avec contre-pression à l'une ou l'autre extrémité.

Un exemple concret : file, pile et vérification de palindrome dans une seule deque

Le programme ci-dessous utilise une ArrayDeque comme file FIFO, une autre comme pile LIFO, et une troisième pour vérifier si une phrase est un palindrome en alimentant les deux extrémités et en comparant. L'idée est que la même interface, voire la même classe, joue les trois rôles.

java— editable, runs on the server

import java.util.*;

public class DequeShowcase {
  public static void main(String[] args) {
    // --- FIFO via Deque ---
    Deque<String> queue = new ArrayDeque<>();
    queue.offerLast("task-1");
    queue.offerLast("task-2");
    queue.offerLast("task-3");
    System.out.println("FIFO drain: " + queue.pollFirst() + ", "
        + queue.pollFirst() + ", " + queue.pollFirst());

// --- LIFO via Deque ---
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(1); stack.push(2); stack.push(3);
    System.out.println("LIFO drain: " + stack.pop() + ", "
        + stack.pop() + ", " + stack.pop());

// --- Empty: returns special value vs throws ---
    Deque<String> empty = new ArrayDeque<>();
    System.out.println("pollFirst on empty: " + empty.pollFirst());
    System.out.println("peekLast  on empty: " + empty.peekLast());
    try { empty.removeFirst(); }
    catch (NoSuchElementException e) {
      System.out.println("removeFirst threw " + e.getClass().getSimpleName());
    }

// --- Iteration: forward and reverse ---
    Deque<Integer> d = new ArrayDeque<>(List.of(10, 20, 30, 40));
    System.out.print("forward: ");
    d.iterator().forEachRemaining(x -> System.out.print(x + " "));
    System.out.println();
    System.out.print("reverse: ");
    d.descendingIterator().forEachRemaining(x -> System.out.print(x + " "));
    System.out.println();

// --- Palindrome check: pollFirst vs pollLast until they meet ---
    System.out.println("\npalindrome? 'racecar' -> " + isPalindrome("racecar"));
    System.out.println("palindrome? 'hello'   -> " + isPalindrome("hello"));
  }

static boolean isPalindrome(String s) {
    Deque<Character> dq = new ArrayDeque<>();
    for (char c : s.toCharArray()) dq.offerLast(c);
    while (dq.size() > 1) {
      if (!dq.pollFirst().equals(dq.pollLast())) return false;
    }
    return true;
  }
}

Ce que cette exécution montre :

La même classe remplit à la fois les rôles de file et de pile sans renommer une seule méthode au-delà de l'extrémité à laquelle vous vous adressez.
Les méthodes « valeur spéciale » produisent silencieusement null quand la file est vide ; les méthodes « exception » lèvent NoSuchElementException. Choisissez selon que le vide est attendu ou constitue un bogue.
La vérification de palindrome utilise les deux extrémités dans la même boucle — pollFirst et pollLast ensemble. C'est le schéma d'accès que seule une Deque vous offre efficacement.

Prochaine étape

Le chapitre sur Deque clôt le versant file du framework. L'autre grande abstraction dans Collection est celle qui rejette les doublons : un Set est une Collection avec le contrat d'unicité intégré. Nous abordons cela ensuite.

Pratique

Vous souhaitez une pile LIFO en Java moderne. Quelle ligne correspond à la recommandation du JDK ?

`Deque<String> stack = new ArrayDeque<>();` puis appeler `push` / `pop` / `peek``Stack<String> stack = new Stack<>();` — la classe dédiée est la façon la plus claire d'exprimer l'intention`Queue<String> stack = new LinkedList<>();` et appeler `add(0, ...)` pour empiler`List<String> stack = new ArrayList<>();` et utiliser `add` / `remove(size()-1)` — O(1) en fin de liste