15.3 Die Klasse Stack

• 15.3 Die Klasse Stack

Ein Stack ist eine Datenstruktur, die nach dem LIFO-Prinzip (last-in-first-out) arbeitet. Die Elemente werden am vorderen Ende der Liste eingefügt und von dort auch wieder entnommen. Das heißt, die zuletzt eingefügten Elemente werden zuerst entnommen und die zuerst eingefügten zuletzt.

In Java ist ein Stack eine Ableitung eines Vektors, der um neue Zugriffsfunktionen erweitert wurde, um das typische Verhalten eines Stacks zu implementieren. Obwohl dies eine ökonomische Vorgehensweise ist, bedeutet es, dass ein Stack alle Methoden eines Vektors erbt und damit auch wie ein Vektor verwendet werden kann. Wir wollen diese Tatsache hier ignorieren und uns mit den spezifischen Eigenschaften eines Stacks beschäftigen.

Der Konstruktor der Klasse Stack ist parameterlos:

public Stack()

java.util.Stack

Das Anfügen neuer Elemente wird durch einen Aufruf der Methode push erledigt und erfolgt wie üblich am oberen Ende des Stacks. Die Methode liefert als Rückgabewert das eingefügte Objekt:

public Object push(Object item)

java.util.Stack

Der Zugriff auf das oberste Element kann mit einer der Methoden pop oder peek erfolgen. Beide liefern das oberste Element des Stacks, pop entfernt es anschließend vom Stack:

public Object pop() public Object peek()

java.util.Stack

Des Weiteren gibt es eine Methode empty, um festzustellen, ob der Stack leer ist, und eine Methode search, die nach einem beliebigen Element sucht und als Rückgabewert die Distanz zwischen gefundenem Element und oberstem Stack-Element angibt:

public boolean empty() public int search(Object o)

java.util.Stack

Das folgende Beispiel verdeutlicht die Anwendung eines Stacks:

001 /* Listing1502.java */ 002 003 import java.util.*; 004 005 public class Listing1502 006 { 007 public static void main(String[] args) 008 { 009 Stack s = new Stack(); 010 011 s.push("Erstes Element"); 012 s.push("Zweites Element"); 013 s.push("Drittes Element"); 014 while (true) { 015 try { 016 System.out.println(s.pop()); 017 } catch (EmptyStackException e) { 018 break; 019 } 020 } 021 } 022 }

Listing1502.java

Listing 15.2: Anwendung eines Stacks

Das Programm erzeugt einen Stack und fügt die Werte »Erstes Element«, »Zweites Element« und »Drittes Element« ein. Anschließend entfernt es so lange Elemente aus dem Stack, bis die Ausgabeschleife durch eine Ausnahme des Typs EmptyStackException beendet wird. Durch die Arbeitsweise des Stack werden die Elemente in der umgekehrten Eingabereihenfolge auf dem Bildschirm ausgegeben:

Drittes Element
Zweites Element
Erstes Element

Mit dem JDK 6 wurde das Interface java.util.Deque eingeführt, welches beispielsweise von der Klasse LinkedList implementiert wird und die gleichen Operationen wie ein Stack anbietet. Dieses Interface wird in Abschnitt 16.2 erläutert.