12.2 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, daß
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:
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:
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:
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:
|
Das folgende Beispiel verdeutlicht die Anwendung eines Stacks:
001 /* Listing1202.java */
002
003 import java.util.*;
004
005 public class Listing1202
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 }
|
Listing1202.java |
Listing 12.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