Stack feature imageStack feature image
HappyCoders Glasses

Stack in Java implementieren

Sven Woltmann
Sven Woltmann
16. März 2022

Im vorherigen Teil des Tutorials, "Stack-Klasse in Java", hast du erfahren, warum man Javas Stack-Klasse nicht verwenden sollte (unnötige Operationen wie insertElementAt() und setElementAt(), fehlendes Interface, over-synchronized).

Die von den JDK-Entwicklern empfohlene Alternative, Deque, bietet ebenfalls Methoden an, die eigentlich nicht in einen Stack gehören, z. B. addLast() und removeLast().

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

Daher zeige ich in diesem und den folgenden Teilen dieses Tutorials, wie man in Java einen Stack selbst implementiert – und zwar auf vier verschiedene Arten:

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 (Klasse Stack im im GitHub-Repo):

public interface Stack<E> { void push(E item); E pop(); E peek(); boolean isEmpty(); }
Code-Sprache: Java (java)

Ich habe mich an dieser Stelle entschieden, dass pop() und peek() bei einem leeren Stack eine NoSuchElementException werfen, so wie es die add/remove/get-Methoden von Deque tun.

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.

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:

ArrayDequeStack als Adapter um ein ArrayDeque
ArrayDequeStack als Adapter um ein ArrayDeque

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(); } }
Code-Sprache: Java (java)

Das folgende Beispielprogramm (Klasse StackDemo in GitHub) zeigt eine beispielhafte Benutzung der ArrayDequeStack-Klasse.

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

public class StackDemo { public static void main(String[] args) { 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); } } }
Code-Sprache: Java (java)

Fazit

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.

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

Wenn du noch Fragen hast, stelle sie gerne über die Kommentar-Funktion. Möchtest du über neue Tutorials und Artikel informiert werden? Dann klicke hier, um dich für den HappyCoders.eu-Newsletter anzumelden.