Stack-Klasse in Java (mit Beispiel)

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. Das folgende Diagramm zeigt die Klassenhierarchie:

Java Stack Methoden

Stack erweitert Vector um die folgenden Methoden:

• push() – legt ein Element auf den Stack
• pop() – entnimmt das oberste Element vom Stack
• peek() – gibt das oberste Element des Stacks zurück, ohne es vom Stack zu entfernen
• 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 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

Die Funktionsweise der Methoden zeige ich im folgenden Beispiel.

Genau wie Vector ist auch Stack threadsicher: Alle Methoden sind synchronized.

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 Element auf den Stack geschoben haben.

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:101)
    at java.base/java.util.Stack.pop(Stack.java:83)
    at eu.happycoders.demos.stack.JavaStackDemo.main(JavaStackDemo.java:28)

Genau wie pop() würde auch peek() bei einem leerem Stack eine EmptyStackException werfen.

Warum man Stack nicht (mehr) verwenden sollte

Die Java-Entwickler 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.
2. Stack implementiert kein Interface. Mit der Verwendung von Stack legt man sich also auf eine bestimmte Implementierung fest.
3. Die Verwendung von synchronized bei jedem Methodenaufruf ist kein besonders performantes Mittel, um eine Datenstruktur threadsicher zu machen. Besser ist in der Regel optimistisches Locking durch CAS („Compare-and-swap“)-Operationen, wie sie in den threadsicheren Queue- und Deque-Implementierungen zu finden sind.

Stack-Alternativen

Stattdessen empfehlen die Java-Entwickler eine der Deque-Implementierungen wie bspw. ArrayDeque zu verwenden.

Die java.util.Deque-Schnittstelle ist ähnlich wie die 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 {
  public static void main(String[] args) {
    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.

Allerdings ist zu bedenken, dass auch Deques Operationen anbieten, die ein Stack eigentlich nicht zur Verfügung stellen sollte, wie z. B. das Einfügen und Entfernen von Elementen am Boden des Stacks.

Alternativ kann man eine eigene Stack-Klasse implementieren.

In den nächsten Teile dieses Tutorials stelle ich verschiedene Stack-Implementierungen vor:

• mit einem ArrayDeque
• mit einem Array
• mit einer LinkedList
• mit einer (bzw. zwei) Queues