Java Stack: Klasse, Methoden, Alternativen, Implementierung

Ebenso alt wie Java selbst ist die seit der Version 1.0 vorhandene Klasse java.util.Stack – eine Implementierung des abstrakten Datentyps Stack.

Stack erbt von java.util.Vector und implementiert damit zahlreiche Interfaces des Java Collections Frameworks – seit Java 21 auch SequencedCollection.

Im folgenden Klassendiagramm stehen durchgezogene Pfeile für extends und gestrichelte für implements. Die Interfaces RandomAccess, Cloneable und Serializable, die Vector ebenfalls implementiert, habe ich weggelassen:

In diesem Artikel zeige ich dir, wie du Stack verwendest, warum du stattdessen ein Deque nehmen solltest – und wie du einen eigenen Stack hinter einem Interface implementierst, das nur die Stack-Operationen enthält.

Stack in Java erzeugen

Stack liegt im Package java.util und hat genau einen Konstruktor – ohne Parameter.

Mit ihm erzeugst du einen leeren Stack:

Stack<String> stack = new Stack<>();

Den Typ der Elemente gibst du in spitzen Klammern an – hier String. Anders als bei Vector kannst du dem Konstruktor weder eine Anfangskapazität noch Anfangselemente mitgeben.

Java Stack Methoden

Stack erweitert Vector um die folgenden Methoden:

• push() – legt ein Element auf den Stack und gibt dieses Element zurück
• pop() – entnimmt das oberste Element vom Stack und gibt es zurück; bei einem leeren Stack wirft pop() eine EmptyStackException
• peek() – gibt das oberste Element des Stacks zurück, ohne es vom Stack zu entfernen; bei einem leeren Stack wirft auch peek() eine EmptyStackException
• empty() – prüft, ob der Stack leer ist; da Stack bereits die isEmpty()-Methode von Vector erbt, ist die empty()-Methode überflüssig; warum die JDK-Entwickler:innen sie eingebaut haben, ist mir ein Rätsel
• search() – sucht ein Element auf dem Stack und gibt dessen Entfernung zur Spitze des Stacks zurück: 1 für das oberste Element, -1, wenn das Element nicht auf dem Stack liegt

Genau wie Vector ist auch Stack threadsicher: pop(), peek() und search() sind synchronized, push() und empty() rufen synchronisierte Methoden von Vector auf.

Die Funktionsweise der Methoden zeige ich im folgenden Beispiel.

Java Stack Beispiel

Die folgenden Code-Schnipsel zeigen eine beispielhafte Verwendung von Stack (den kompletten Code findest du in der Klasse JavaStackDemo im GitHub-Repo).

Zuerst legen wir einen Stack an und schieben per push() die Elemente „apple“, „orange“ und „pear“ auf den Stack:

Stack<String> stack = new Stack<>();

stack.push("apple");
stack.push("orange");
stack.push("pear");

Danach geben wir den Inhalt des Stacks auf der Konsole aus – sowie die Ergebnisse von peek() und empty():

System.out.println("stack = " + stack);

System.out.println("stack.peek() = " + stack.peek());
System.out.println("stack.empty() = " + stack.empty());

Die Ausgabe sieht wie folgt aus:

stack = [apple, orange, pear]
stack.peek() = pear
stack.empty() = false

Die toString()-Methode von Stack gibt die Elemente also von unten nach oben aus. Das zuletzt eingefügte Element „pear“ liegt auf der Spitze des Stacks.

Mit search() können wir nach einem Element suchen:

System.out.println("stack.search(\"apple\") = " + stack.search("apple"));

Die Ausgabe lautet:

stack.search("apple") = 3

Das bedeutet, dass „apple“ an dritter Position im Stack steht. Das liegt daran, dass wir nach „apple“ zwei weitere Elemente auf den Stack geschoben haben.

search() zählt von der Spitze aus und beginnt bei 1: Für „pear“ gibt die Methode 1 zurück, für ein Element, das nicht auf dem Stack liegt, -1.

Wir entnehmen die drei Elemente wieder:

System.out.println("stack.pop() = " + stack.pop());
System.out.println("stack.pop() = " + stack.pop());
System.out.println("stack.pop() = " + stack.pop());

Wir sehen, dass die Elemente in umgekehrter Reihenfolge entnommen werden:

stack.pop() = pear
stack.pop() = orange
stack.pop() = apple

Was passiert, wenn wir ein weiteres Mal pop() aufrufen?

System.out.println("stack.pop() = " + stack.pop());

Da der Stack jetzt leer ist, wird eine EmptyStackException geworfen:

Exception in thread "main" java.util.EmptyStackException
    at java.base/java.util.Stack.peek(Stack.java:103)
    at java.base/java.util.Stack.pop(Stack.java:85)
    at eu.happycoders.demos.stack.JavaStackDemo.main(JavaStackDemo.java:28)

Genau wie pop() wirft auch peek() bei einem leeren Stack eine EmptyStackException.

Warum man Stack nicht (mehr) verwenden sollte

Die JDK-Entwickler:innen empfehlen, java.util.Stack nicht mehr zu verwenden. Das Javadoc besagt:

„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.“

Was genau bedeutet das? Meiner Meinung nach sollte Stack aus den folgenden Gründen nicht verwendet werden:

1. Durch die Erweiterung von Vector stellt Stack Operationen zur Verfügung, die in einem Stack nichts zu suchen haben, so wie der Zugriff auf Elemente über deren Index oder das Einfügen und Löschen von Elementen an beliebigen Positionen. Seit Java 21 kommen über das Interface SequencedCollection Methoden wie addFirst() und removeFirst() hinzu, die am Boden des Stacks arbeiten.
2. Für Stack gibt es kein eigenes Interface. Wer Stack als Typ verwendet, legt sich auf diese eine Implementierung fest.
3. Greift nur ein Thread auf den Stack zu, ist die Synchronisation überflüssig. Im Javadoc von ArrayDeque heißt es: „This class is likely to be faster than Stack when used as a stack“. Greifen hingegen mehrere Threads auf den Stack zu, ist synchronized bei jedem Methodenaufruf kein besonders performantes Mittel, um eine Datenstruktur threadsicher zu machen. Besser ist in der Regel optimistisches Locking durch CAS-Operationen („Compare-and-swap“), wie ConcurrentLinkedDeque sie einsetzt.

Stack-Alternativen

Die JDK-Entwickler:innen empfehlen, statt Stack eine der Deque-Implementierungen zu verwenden, z. B. ArrayDeque.

Das Interface java.util.Deque gibt es seit Java 6. Seine Methoden ähneln denen von Stack:

• Es gibt die Methoden push(), pop() und peek().
• Statt empty() musst du isEmpty() aufrufen.
• Eine search()-Methode gibt es nicht.

Der folgende Code (ArrayDequeDemo im GitHub-Repo) zeigt die beispielhafte Anwendung von ArrayDeque als Stack:

public class ArrayDequeDemo {
  static void main() {
    Deque<String> stack = new ArrayDeque<>();

    stack.push("apple");
    stack.push("orange");
    stack.push("pear");

    System.out.println("stack = " + stack);

    System.out.println("stack.peek() = " + stack.peek());
    System.out.println("stack.isEmpty() = " + stack.isEmpty());

    System.out.println("stack.pop() = " + stack.pop());
    System.out.println("stack.pop() = " + stack.pop());
    System.out.println("stack.pop() = " + stack.pop());

    System.out.println("stack.pop() = " + stack.pop());
  }
}

Wie du siehst, ist der Code nahezu identisch zum vorherigen Beispiel.

Die Ausgabe ist es nicht:

stack = [pear, orange, apple]
stack.peek() = pear
stack.isEmpty() = false
stack.pop() = pear
stack.pop() = orange
stack.pop() = apple
Exception in thread "main" java.util.NoSuchElementException
    at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:360)
    at java.base/java.util.ArrayDeque.pop(ArrayDeque.java:591)
    at eu.happycoders.demos.stack.ArrayDequeDemo.main(ArrayDequeDemo.java:28)

In der Ausgabe siehst du zwei Unterschiede zum Beispiel mit Stack:

• toString() gibt die Elemente von oben nach unten aus – das zuletzt eingefügte Element „pear“ steht vorn.
• pop() wirft bei einem leeren Stack eine NoSuchElementException statt einer EmptyStackException.

Zwei weitere Unterschiede zeigt das Beispiel nicht: peek() gibt bei einem leeren ArrayDeque null zurück, statt eine Exception zu werfen. Und ArrayDeque nimmt keine null-Elemente an – denn null ist bei einem Deque der Rückgabewert für „leer“.

Die folgende Tabelle fasst diese vier Unterschiede zusammen. Dazu kommen der Zugriff über den Index und die Thread-Sicherheit aus dem vorigen Abschnitt:

	Stack	ArrayDeque
peek() bei leerem Stack	wirft EmptyStackException	gibt null zurück
pop() bei leerem Stack	wirft EmptyStackException	wirft NoSuchElementException
push(null)	erlaubt	wirft NullPointerException
Reihenfolge von toString() und Iterator	von unten nach oben	von oben nach unten
Zugriff über den Index	ja	nein
Thread-Sicherheit	ja	nein

ArrayDeque ist also nicht threadsicher. Greifen mehrere Threads auf den Stack zu, verwende stattdessen ein threadsicheres Deque wie ConcurrentLinkedDeque.

Wie sich Iteration und Thread-Sicherheit im Detail unterscheiden, zeige ich im Artikel Java Deque vs. Stack.

Stack in Java implementieren

Weder Stack noch Deque ist ein sauberer Stack: Beide bieten Operationen an, die ein Stack nicht zur Verfügung stellen sollte – Stack die indexbasierten Methoden von Vector, Deque Methoden wie addLast() und removeLast(), die Elemente am Boden des Stacks einfügen und entfernen.

Diese unnötigen Operationen stehen im Widerspruch zum Interface-Segregation-Prinzip (ISP), demzufolge eine Schnittstelle nur diejenigen Methoden enthalten sollte, die die Nutzer:innen dieser Schnittstelle benötigen.

Daher zeige ich in diesem Abschnitt und den folgenden Teilen dieses Tutorials, wie man in Java einen Stack selbst implementiert – und zwar auf vier verschiedene Arten, die Array-Variante in zwei Ausführungen:

Variante	Klasse	Größe	push()	pop()
Adapter um ein ArrayDeque (in diesem Abschnitt)	ArrayDequeStack	wächst	amortisiert O(1)	O(1)
Array fester Größe	BoundedArrayStack	fest	O(1)	O(1)
Array variabler Größe	ArrayStack	wächst	amortisiert O(1)	O(1)
Verkettete Liste	LinkedListStack	wächst und schrumpft	O(1)	O(1)
Eine (bzw. zwei) Queues	QueueStack	wächst	O(n)	O(1)

„Amortisiert“ heißt: Ist das interne Array voll, kostet ein push() einmalig O(n) für das Umkopieren; auf alle Aufrufe verteilt bleibt der Aufwand konstant (siehe amortisierter Aufwand im Artikel über die O-Notation).

Los geht’s mit einem Interface…

Stack-Interface

Als Erstes legen wir ein Stack-Interface an. Dieses enthält nur diejenigen Methoden, die ein Stack anbieten sollte, nämlich:

• push() – zum Hinzufügen von Elementen auf den Stack
• pop() – zum Entnehmen von Elementen von der Oberseite des Stacks
• peek() – zum Betrachten des obersten Stack-Elements, ohne es zu entnehmen
• isEmpty() – um zu prüfen, ob der Stack leer ist (diese Methode ist optional)

Der folgende Code zeigt das Interface (Interface Stack im GitHub-Repo):

public interface Stack<E> {
  void push(E element);
  E pop();
  E peek();
  boolean isEmpty();
}

Unser Interface heißt genauso wie java.util.Stack, liegt aber im Package eu.happycoders.collections.stack. Ab hier ist mit Stack dieses Interface gemeint, nicht die Klasse aus dem JDK.

Ich habe mich an dieser Stelle entschieden, dass pop() und peek() bei einem leeren Stack eine NoSuchElementException werfen, so wie es removeFirst() und getFirst() von Deque tun. Anders als Deque.peek() liefert unser peek() also nicht null.

Alternativ könnte man auch Optional<E> zurückliefern. Die Entscheidung hängt davon ab, inwieweit der Aufruf von pop() und peek() auf einem leeren Stack eine Ausnahme darstellt (dann sollte man Exceptions werfen) oder einen regulären Control Flow (dann sollte man ein Optional zurückgeben).

Was man nicht tun sollte, ist bei einem leeren Stack null zurückzugeben – denn dann ließe sich ein leerer Stack nicht von einem null-Element unterscheiden. Der ArrayDequeStack, der gleich folgt, nimmt ohnehin keine null-Elemente an: Bei push(null) wirft ArrayDeque.addFirst() eine NullPointerException.

Stack implementieren mit ArrayDeque

Unsere erste Implementierung besteht aus einem Adapter um die (nicht threadsichere) Deque-Implementierung ArrayDeque. Der Adapter leitet die Stack-Methoden wie folgt weiter:

• Stack.push() → ArrayDeque.addFirst()
• Stack.pop() → ArrayDeque.removeFirst()
• Stack.peek() → ArrayDeque.getFirst()
• Stack.isEmpty() → ArrayDeque.isEmpty()

Hier zunächst ein Klassendiagramm, das das Adapter-Pattern darstellt:

Und hier die Implementierung des Adapters (Klasse ArrayDequeStack im GitHub-Repo):

public class ArrayDequeStack<E> implements Stack<E> {
  private final Deque<E> deque = new ArrayDeque<>();

  @Override
  public void push(E item) {
    deque.addFirst(item);
  }

  @Override
  public E pop() {
    return deque.removeFirst();
  }

  @Override
  public E peek() {
    return deque.getFirst();
  }

  @Override
  public boolean isEmpty() {
    return deque.isEmpty();
  }
}

Das folgende Demo-Programm (Klasse StackDemo im GitHub-Repo) zeigt, wie man die ArrayDequeStack-Klasse benutzt.

Es ist so konzipiert, dass wir ohne großen Aufwand zusätzliche Stack-Implementierungen ausprobieren können (indem wir runDemo() für Instanzen anderer Stack-Klassen aufrufen).

public class StackDemo {
  static void main() {
    runDemo(new ArrayDequeStack<>());
  }

  private static void runDemo(Stack<Integer> stack) {
    System.out.println(
        "---------- " + stack.getClass().getSimpleName() + " ----------");

    stack.push(1);
    stack.push(2);
    stack.push(3);

    System.out.println("stack.peek() = " + stack.peek());

    System.out.println("stack.pop() = " + stack.pop());
    System.out.println("stack.pop() = " + stack.pop());
    System.out.println("stack.pop() = " + stack.pop());

    try {
      System.out.println("stack.pop() = " + stack.pop());
    } catch (Exception ex) {
      ex.printStackTrace(System.out);
    }
  }
}

Das Programm gibt Folgendes aus:

---------- ArrayDequeStack ----------
stack.peek() = 3
stack.pop() = 3
stack.pop() = 2
stack.pop() = 1
java.util.NoSuchElementException
    at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:360)
    at eu.happycoders.collections.stack.ArrayDequeStack.pop(ArrayDequeStack.java:26)
    at eu.happycoders.demos.stack.StackDemo.runDemo(StackDemo.java:38)
    at eu.happycoders.demos.stack.StackDemo.main(StackDemo.java:17)

Die Elemente kommen in umgekehrter Reihenfolge wieder heraus, und der vierte pop()-Aufruf auf den leeren Stack wirft die NoSuchElementException aus ArrayDeque.removeFirst().

Wir haben mit wenigen Zeilen Code eine eigene (nicht threadsichere) Stack-Klasse implementiert.

Um einen threadsicheren Stack zu implementieren, können wir analog einen Adapter um ein threadsicheres Deque – wie ConcurrentLinkedDeque (nicht blockierend) oder LinkedBlockingDeque (blockierend) – legen. Einen blockierenden Stack ergibt das allerdings erst, wenn der Adapter an putFirst() und takeFirst() weiterleitet; diese Methoden werfen eine InterruptedException, die das Interface dann deklarieren müsste.

Zusammenfassung und Ausblick

In diesem Artikel hast du gelernt, wie du Javas Stack-Klasse verwendest, warum die JDK-Entwickler:innen stattdessen ein Deque wie ArrayDeque empfehlen und wie du einen eigenen Stack hinter einem Interface implementierst, das nur die Stack-Operationen enthält.

Im nächsten Teil des Tutorials zeige ich dir, wie du einen Stack mit einem Array implementierst.