Classe Java Stack et piles basées sur Deque

Une pile est une collection dernier entré, premier sorti : vous push un élément, et le prochain pop retourne ce que vous avez placé le plus récemment. Java propose deux façons d'en construire une — la classe historique java.util.Stack de 1995, et la recommandation moderne d'utiliser Deque<E> (typiquement ArrayDeque). Les deux fonctionnent, les deux proposent les mêmes opérations conceptuelles, mais la Javadoc officielle de Stack elle-même vous conseille de préférer Deque. Ce chapitre vous montre à quoi ressemble Stack, pourquoi le JDK pointe désormais ailleurs, et comment utiliser le remplacement recommandé.

À quoi sert une pile

Les piles apparaissent dans tout algorithme naturellement dernier entré, premier sorti :

Historiques d'annulation / rétablissement — chaque nouvelle action est poussée ; annuler dépile la dernière.
État d'analyseur et d'interpréteur — évaluation d'expressions, vérification de crochets équilibrés, trames d'appel.
Parcours en profondeur — on empile les successeurs, on dépile le prochain nœud à visiter.
Inverser des éléments — on empile chaque élément d'une séquence, puis on les dépile.

La forme est toujours la même : push, pop, peek, isEmpty, size. Cinq opérations.

La classe `Stack` héritée

java.util.Stack<E> étend Vector<E>, ce qui signifie qu'elle hérite de tout ce qui se trouve dans le chapitre précédent — y compris le synchronized par méthode, les noms de méthodes hérités, et le fait gênant qu'il s'agit d'une List. Un Stack est, par héritage, une liste indexable — vous pouvez appeler stack.get(3) dessus, ce qui est exactement le genre d'erreur d'API qui motive la recommandation d'utiliser Deque.

Stack<String> s = new Stack<>();
s.push("a");
s.push("b");
s.push("c");
System.out.println(s.peek());   // c
System.out.println(s.pop());    // c
System.out.println(s.size());   // 2
System.out.println(s.empty());  // false  (note: empty(), not isEmpty())

Six méthodes spécifiques à Stack :

E push(E item) — ajouter au sommet. Retourne l'élément.
E pop() — supprimer et retourner le sommet. Lève EmptyStackException si vide.
E peek() — sommet sans suppression. Même exception.
boolean empty() — notez l'orthographe en minuscules, distincte de Collection.isEmpty().
int search(Object o) — distance en base 1 depuis le sommet, ou -1 si absent. Choix étrange — le résultat indique « combien de pop pour atteindre o », ce qui est rarement utile.

Tout le reste est hérité de Vector et List.

Pourquoi la Javadoc vous renvoie vers `Deque`

Ouvrez la Javadoc réelle de Stack dans n'importe quel JDK moderne et vous trouverez la ligne :

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

Les raisons s'alignent avec le chapitre précédent sur Vector :

Stack est synchronisé sur chaque méthode. Vous payez le coût du verrou même en code mono-thread, et la synchronisation est au mauvais niveau de granularité pour toute opération composée.
Stack est une List. L'accès indexé sur une pile est une erreur de catégorie — cela vous permet de regarder au milieu, ce qui viole la discipline LIFO que la classe est censée imposer.
Les cinq opérations de pile dont vous avez réellement besoin sont déjà sur Deque (push, pop, peek, isEmpty, size), et ArrayDeque est l'implémentation la plus rapide du JDK.

En résumé : Stack fonctionne, mais c'est une conception de 1995 intégrée dans un framework de 1998. Le nouveau code devrait utiliser Deque.

Le remplacement recommandé

L'idiome tient en une ligne :

Deque<String> stack = new ArrayDeque<>();

Ensuite appelez push, pop, peek. L'interface Deque les définit comme addFirst, removeFirst, peekFirst sous le capot, donc le sommet de la pile est la tête du deque.

Deque<String> calls = new ArrayDeque<>();
calls.push("main");
calls.push("parseArgs");
calls.push("split");
System.out.println(calls.peek());      // split
System.out.println(calls.pop());       // split
System.out.println(calls);              // [parseArgs, main]

Trois détails à connaître :

peek() sur un Deque retourne null quand vide ; peek() sur Stack lève une exception. peekFirst() est la même forme retournant null. Si vous préférez l'exception, appelez getFirst() (ou element()).
La même distinction pop() / removeFirst() s'applique : pop() lève une exception quand vide.
ArrayDeque rejette les éléments null. Utilisez-le uniquement pour des valeurs non nulles — ce qui est le cas habituel pour les piles.

Quand `Stack` est acceptable dans du nouveau code

Presque jamais, et le seuil est bas :

Maintenir du vieux code qui l'utilise déjà — ne changez pas juste pour permuter la classe.
Travailler avec une API qui requiert spécifiquement Stack — extrêmement rare. Les classes Swing qui utilisaient Vector et ses semblables n'ont pas tendance à requérir Stack.

Pour tout le reste, déclarez Deque<E> et instanciez ArrayDeque<>.

Un exemple complet : vérificateur de parenthèses, de deux façons

Le programme ci-dessous utilise à la fois Stack et Deque<Character> pour résoudre le classique problème des parenthèses équilibrées. Même algorithme, deux implémentations — lisez-le côte à côte, puis regardez la forme Deque et décidez laquelle vous préféreriez relire dans trois mois.

java— editable, runs on the server

import java.util.*;

public class BalancedBrackets {
  // 1. The legacy Stack form.
  static boolean balancedStack(String s) {
    Stack<Character> opens = new Stack<>();
    for (char c : s.toCharArray()) {
      switch (c) {
        case '(', '[', '{' -> opens.push(c);
        case ')', ']', '}' -> {
          if (opens.empty() || !matches(opens.pop(), c)) return false;
        }
        default -> {}
      }
    }
    return opens.empty();
  }

// 2. The modern Deque form.
  static boolean balancedDeque(String s) {
    Deque<Character> opens = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
      switch (c) {
        case '(', '[', '{' -> opens.push(c);
        case ')', ']', '}' -> {
          if (opens.isEmpty() || !matches(opens.pop(), c)) return false;
        }
        default -> {}
      }
    }
    return opens.isEmpty();
  }

static boolean matches(char open, char close) {
    return (open == '(' && close == ')')
        || (open == '[' && close == ']')
        || (open == '{' && close == '}');
  }

public static void main(String[] args) {
    String[] tests = {
      "(a+b)*[c-d]",
      "{ if (a[i] > 0) { do(); } }",
      "(unclosed",
      ")a(",
      ""
    };
    for (String t : tests) {
      System.out.printf("%-32s  stack=%-5s  deque=%-5s%n",
          "'" + t + "'",
          balancedStack(t),
          balancedDeque(t));
    }

// Tiny demo of the legacy Stack-specific oddities.
    Stack<Integer> demo = new Stack<>();
    demo.push(10); demo.push(20); demo.push(30);
    System.out.println("\nStack-specific API:");
    System.out.println("  empty()  = " + demo.empty()    + "  (not isEmpty)");
    System.out.println("  search(10) = " + demo.search(10)  + "  (1-based from top)");
    System.out.println("  search(99) = " + demo.search(99)  + "  (-1 if absent)");
    System.out.println("  get(0)   = " + demo.get(0)
        + "  (it's also a List — direct index access; category leak)");
  }
}

Ce qu'il vaut la peine de noter :

Les deux fonctions sont identiques hormis le nom du type et empty() vs isEmpty(). Il n'y a aucune raison algorithmique de préférer Stack — le code se lit de la même façon.
Le bloc « Stack-specific API » en bas illustre le cas contre la classe héritée : empty() a un nom différent du reste du framework, search() retourne une distance en base 1 (rare dans le reste de Java), et get(0) vous permet d'accéder au milieu d'une pile — ce qui va à l'encontre de tout l'intérêt de l'abstraction.

La suite

Vous avez maintenant vu les trois implémentations de List principales (ArrayList, LinkedList, Vector) et la spécialisation LIFO construite par-dessus Vector. Les quatre prochains chapitres couvrent le pendant pour les éléments qu'on ajoute et retire dans l'ordre : l'interface Queue, PriorityQueue, ArrayDeque, et le contrat plus général de Deque.

Pratique

Vous écrivez un nouvel analyseur et avez besoin d'une pile LIFO de tokens pour la passe de correspondance des crochets. Quelle est la déclaration recommandée en Java moderne ?

`Deque<Token> tokens = new ArrayDeque<>();` — utiliser `push`, `pop`, `peek` ; la Javadoc de Stack elle-même recommande Deque`Stack<Token> tokens = new Stack<>();` — la classe dédiée est le signal d'intention le plus clair`Vector<Token> tokens = new Vector<>();` — en sous-classer inline pour n'exposer que `push`/`pop``List<Token> tokens = new ArrayList<>();` avec `add(0, t)` pour push et `remove(0)` pour pop