

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:
- Als Wrapper um ein
ArrayDeque
(in diesem Artikel) - Mit einem Array
- Mit einer verketteten Liste
- Mit einer (bzw. zwei) Queues
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 Stackpop()
– zum Entnehmen von Elementen von der Oberseite des Stackspeek()
– zum Betrachten des obersten Stack-Elements, ohne es zu entnehmenisEmpty()
– 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:

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.