Java Stack-Klasse und Deque-basierte Stacks

Ein Stack ist eine Last-in-first-out-Collection: Man pusht ein Element hinein, und das nächste pop gibt das zuletzt hinzugefügte zurück. Java bietet zwei Möglichkeiten, einen Stack zu erstellen — die veraltete Klasse java.util.Stack aus dem Jahr 1995 und die moderne Empfehlung, Deque<E> (typischerweise ArrayDeque) zu verwenden. Beide funktionieren und haben dieselben konzeptuellen Operationen, aber die offizielle Javadoc von Stack selbst empfiehlt, Deque zu bevorzugen. Dieses Kapitel zeigt, wie Stack aussieht, warum das JDK heute auf eine andere Lösung verweist und wie man den empfohlenen Ersatz verwendet.

Wofür ein Stack verwendet wird

Stacks tauchen in allen Algorithmen auf, die von Natur aus Last-in-first-out funktionieren:

Rückgängig machen / Wiederherstellen von Historien — jede neue Aktion wird gepusht; Rückgängig macht die letzte pop.
Parser- und Interpreter-Zustand — Ausdrucksauswertung, Prüfung auf ausgewogene Klammern, Aufrufrahmen.
Tiefensuche — Nachfolger pushen, nächsten zu besuchenden Knoten poppen.
Dinge umkehren — jedes Element einer Sequenz pushen, dann wieder poppen.

Die Form ist immer dieselbe: push, pop, peek, isEmpty, size. Fünf Operationen.

Die veraltete Klasse `Stack`

java.util.Stack<E> erweitert Vector<E>, was bedeutet, dass sie alles aus dem vorherigen Kapitel erbt — einschließlich des per-Methode synchronized, der veralteten Methodennamen und der ungewöhnlichen Tatsache, dass es eine List ist. Ein Stack ist durch Vererbung eine indizierbare Liste — man kann stack.get(3) darauf aufrufen, was genau die Art von API-Fehler ist, die die Empfehlung motiviert, stattdessen Deque zu verwenden.

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())

Sechs Methoden spezifisch für Stack:

E push(E item) — fügt oben hinzu. Gibt das Element zurück.
E pop() — entfernt und gibt das oberste Element zurück. Wirft EmptyStackException wenn leer.
E peek() — oberstes Element ohne Entfernen. Gleiche Ausnahme.
boolean empty() — beachte die Kleinschreibung, unterscheidet sich von Collection.isEmpty().
int search(Object o) — 1-basierter Abstand von der Spitze oder -1 wenn nicht vorhanden. Seltsame Wahl — das Ergebnis ist "wie viele pops bis o erreicht ist", was selten nützlich ist.

Alles andere wird von Vector und List geerbt.

Warum die Javadoc auf `Deque` verweist

Öffnet man die tatsächliche Javadoc für Stack in einem modernen JDK, findet man folgende Zeile:

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.

Die Gründe decken sich mit dem vorherigen Kapitel über Vector:

Stack ist bei jeder Methode synchronisiert. Man zahlt die Sperrkosten auch in einThreadigem Code, und die Synchronisierung hat die falsche Granularität für zusammengesetzte Operationen.
Stack ist eine List. Indizierten Zugriff auf einem Stack zu haben ist ein kategorischer Fehler — man kann in die Mitte schauen, was die LIFO-Disziplin verletzt, die die Klasse eigentlich durchsetzen soll.
Die fünf Stack-Operationen, die man tatsächlich braucht, sind bereits in Deque (push, pop, peek, isEmpty, size) vorhanden, und ArrayDeque ist die schnellste Implementierung im JDK.

Kurz gesagt: Stack funktioniert, ist aber ein Design von 1995, das in ein Framework von 1998 gepresst wurde. Neuer Code sollte Deque verwenden.

Der empfohlene Ersatz

Das Idiom ist eine Zeile:

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

Dann ruft man push, pop, peek auf. Das Deque-Interface definiert sie intern als addFirst, removeFirst, peekFirst, sodass die Spitze des Stacks der Kopf der Deque ist.

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]

Drei Details zu beachten:

peek() auf einer Deque gibt null zurück wenn leer; peek() auf Stack wirft eine Ausnahme. peekFirst() hat ebenfalls die null-zurückgebende Form. Wenn man stattdessen eine Ausnahme möchte, ruft man getFirst() (oder element()) auf.
Die gleiche Unterscheidung zwischen pop() / removeFirst() gilt: pop() wirft eine Ausnahme wenn leer.
ArrayDeque lehnt null-Elemente ab. Man sollte es nur für Nicht-null-Werte verwenden — was der übliche Fall bei Stacks ist.

Wann `Stack` in neuem Code akzeptabel ist

Fast nie, und die Hürde ist niedrig:

Pflege von altem Code, der ihn bereits verwendet — nicht nur wegen des Klassen-Austauschs umbauen.
Arbeit mit einer API, die explizit Stack erfordert — äußerst selten. Die Swing-Klassen, die Vector und ähnliche verwendeten, tendieren nicht dazu, Stack zu verlangen.

Für alles andere: Deque<E> deklarieren und ArrayDeque<> instanziieren.

Ein ausgearbeitetes Beispiel: Klammerprüfer auf zwei Arten

Das folgende Programm verwendet sowohl Stack als auch Deque<Character>, um das klassische Problem der ausgewogenen Klammern zu lösen. Gleicher Algorithmus, zwei Implementierungen — nebeneinander lesen, dann die Deque-Form betrachten und entscheiden, welche man in drei Monaten lieber lesen würde.

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)");
  }
}

Was zu beachten ist:

Die beiden Funktionen sind bis auf den Typnamen und empty() vs isEmpty() identisch. Es gibt keinen algorithmischen Grund, Stack zu bevorzugen — der Code liest sich genauso.
Der Block "Stack-specific API" am Ende ist das Argument gegen die veraltete Klasse: empty() ist ein anderer Name als der Rest des Frameworks, search() gibt einen 1-basierten Abstand zurück (im restlichen Java selten), und get(0) erlaubt es, in die Mitte eines Stacks zu greifen — was den gesamten Zweck der Abstraktion untergräbt.

Was kommt als Nächstes

Sie haben nun die drei Hauptimplementierungen von List (ArrayList, LinkedList, Vector) und die LIFO-Spezialisierung gesehen, die auf Vector aufgebaut ist. Die nächsten vier Kapitel behandeln die parallele Geschichte für Dinge-die-man-in-Reihenfolge-hinzufügt-und-entnimmt: das Queue-Interface, PriorityQueue, ArrayDeque und den allgemeineren Deque-Vertrag.

Übungen

Übung

Sie schreiben einen neuen Parser und benötigen einen LIFO-Stack von Tokens für den Klammerprüfungsdurchlauf. Welche Deklaration wird in modernem Java empfohlen?

`Deque<Token> tokens = new ArrayDeque<>();` — verwende `push`, `pop`, `peek`; die Javadoc von Stack selbst empfiehlt Deque`Stack<Token> tokens = new Stack<>();` — die dedizierte Klasse ist das klarste Signal der Absicht`Vector<Token> tokens = new Vector<>();` — unterklasse es inline, um nur `push`/`pop` freizugeben`List<Token> tokens = new ArrayList<>();` mit `add(0, t)` für push und `remove(0)` für pop