4.5Stack (Kellerspeicher, Stapel) 

Einen Stapelspeicher, auch Keller genannt, ist eine LIFO-(Last-in-First-out-)Datenstruktur. Die lässt sich mit einem Stapel Teller veranschaulichen. Beim Hinzufügen von Elementen wächst die Datenstruktur dynamisch, wobei das zuletzt abgelegte Element als erstes auch wieder entnommen wird – ein wahlfreier Zugriff ist nicht vorgesehen.

In Java gibt es drei unterschiedliche Herangehensweisen, falls ein LIFO-Verhalten erwünscht ist:

• Stack: Die Klasse Stack repräsentiert einen Stapelspeicher seit Java 1.0. Die Methode push(…) setzt Elemente auf den Stack, pop() holt sie herunter. Die Klasse erweitert Vector (wir diskutieren diese prickelnde Designentscheidung weiter unten), womit die Klasse zusätzliche Funktionalität besitzt, beispielsweise die Fähigkeit zur Aufzählung und zum wahlfreien Zugriff auf Kellerelemente. Stack ist nicht mehr angebracht.

• Deque ist ein Typ, dessen implementierende Klassen sich je nach Methoden FIFO (für engl. first in, first out) oder LIFO verhalten. Das bestimmen die Methoden. Soll sich eine Deque-Datenstruktur als LIFO-Stack verhalten, sind die Methoden addFirst(…) (entspricht push(…) bei Stack) und removeFirst() (entspricht pop() bei Stack) zu nutzen. Eine LinkedList implementiert Deque, kann also als Stack verwendet werden.

• Collections.asLifoQueue(Deque): Deque zeigt das LIFO-Verhalten nur bei den entsprechenden Methoden addFirst(…) und removeFirst(…), doch ist der Typ anfällig für Programmierfehler, denn schnell ist statt addFirst(…) nur add(…) geschrieben, und schon landet das Element an der falschen Stelle. Interessant ist daher die Methode Collections.asLifoQueue(Deque). Sie liefert eine Queue zurück, also eine Datenstruktur mit weniger Methoden, als eine Deque, wobei das traditionelle FIFO-Prinzip einer Queue umgedreht wurde in ein LIFO-Verhalten. Mit anderen Worten: Die Queue einer Collections.asLifoQueue(Deque) zeigt das typische Verhalten eines Stacks. Und weil die Schnittstelle Queue nur wenige Methoden hat, minimiert sich die Fehlerquelle, aus Versehen die falsche Methode aufgerufen zu haben.

 

4.5.1Die Methoden von java.util.Stack 

Stack besitzt nur wenige zusätzliche Methoden.

• Stack()
  Der Konstruktor erzeugt einen neuen Stack.

• boolean empty()
  Testet, ob Elemente auf dem Stapel vorhanden sind.

• E push(E item)
  Das Element item wird auf den Stapel gebracht.

• E pop()
  Holt das letzte Element vom Stapel. EmptyStackException signalisiert einen leeren Stapel.

• E peek()
  Das oberste Element wird nur vom Stapel gelesen, aber nicht wie bei pop() entfernt. Bei leerem Stapel wird eine EmptyStackException ausgelöst.

• int search(Object o)
  Sucht im Stapel nach dem obersten Eintrag, der mit dem Objekt o übereinstimmt. Gibt die Distanz von der Spitze zurück oder –1, falls das Objekt nicht im Stapel ist. 1 bedeutet, dass der gesuchte Eintrag ganz oben auf dem Stapelspeicher liegt, 2 bezeichnet die zweitoberste Position usw. Die Zählweise ist ungewöhnlich, da sie nicht nullbasiert ist wie alle anderen Methoden, die mit Positionen arbeiten. Doch hier handelt es sich ausdrücklich um die Distanz und nicht um die Position!

Ein Stack ist ein Vector – aha!

Eine genaue Betrachtung der Klasse Stack zeigt den unsinnigen und falschen Einsatz der Vererbung, und es stellt sich die Frage, warum sich der Autor Jonathan Payne für jene Variante entschieden hat. Stack erbt alle Methoden von Vector (einer List) und damit viele Methoden, die im krassen Gegensatz zu den charakteristischen Eigenschaften eines Stapels stehen. Dazu zählen unter anderem die Methoden elementAt(…), indexOf(…), insertElementAt(…), removeElementAt(…), setElementAt(…) und weitere. Wenn eine Unterklasse nicht bedingungslos alle Eigenschaften der Oberklasse unterstützt, ist die Vererbung falsch angewendet.