Stack
-
Kellerspeicher (Stack):
-
realisiert einen LIFO-Speicher (Last In First
Out)
- Elemente eines beliebigen (aber jeweils
festen) Typs werden abgespeichert
-
neue Elemente werden oben abgelegt
-
ein Element kann nur von oben entnommen werden
- im Prinzip unendlich groß
-
Operationen eines Stacks:
-
push(e)
- legt das Element e
auf dem Stack ab
-
e = pop()
- holt das oberste Element vom Stack
-
status = empty()
- prüft, ob der Stack leer ist
- status ist boolean
-
optional: e = peek()
- gibt das oberste Element des Stacks zurück,
ohne es zu entfernen
- identisch mit e = pop;
push(e)
-
Stack in Java:
- vorhanden als java.util.Stack
- pop und peek werfen ggf. EmptyStackException
-
Typ der Elemente immer Object
- → beliebige Typen (auch durcheinander) in
einem Stack
- einfache Typen über Wrapper-Klassen (Double statt double
etc.)
-
eigentlich gewünscht
- Stack mit einem vorgebbaren Datentyp
- z.B. Stack<int>, Stack<String> (generische
Datentypen)
- geplant für Java 1.5
-
Verwaltung von Unterfunktionsaufrufen:
- alle lokalen Variablen und Parameter einer
Funktion bilden ein Element
(Stackframe)
-
aktueller Stackframe
- gehört zur aktuell ablaufenden
Unterfunktion
- enthält alle gerade zugreifbaren
Variablen
-
Aufruf einer Unterfunktion
- Stackframe des Aufrufers wird auf einem Stack
abgelegt (push)
- Unterfunktion erzeugt neuen aktuellen
Stackframe
-
Rückkehr aus einer Unterfunktion
- oberster Stackframe ersetzt aktuellen (pop)
- Variablen des Aufrufers wieder da
- Variablen des Unterprogramms unwiderruflich
verloren
-
Berechnung von arithmetischen Ausdrücken:
-
betrachten Ausdrücke aus
- Zahlen (der Einfachheit halber positive ganze
Zahlen)
- Klammern ( )
- Grundoperationen + - *
/
-
Ausdrücke müssen vollständig geklammert sein
- Operationen haben genau zwei Operanden
- Operanden sind Zahlen oder
Klammer-Ausdrücke
- keine Punkt- vor Strichrechnung
-
Beispiele
- ok: (((3 + 5) * 2)/(7 -
4))
- falsch: (12 + 5 + 7),
sondern ((12 + 5) + 7)
- falsch: (2 + 4 * 6),
sondern (2 + (4*6))
-
Berechnungsverfahren mit Stack
- Klammern, Operatoren und Zahlen gelten jeweils als
ein Element (Token)
-
Eingabeelemente der Reihe nach verarbeiten:
- alles außer ) auf
den Stack
bei ):
operand2 =
pop()
operator =
pop()
operand1 =
pop()
dummy = pop()
// gibt (
ergebnis =
operator(operand1, operand2)
push(ergebnis)
am Ende: ergebnis = pop()
-
Beispielrechnung:
-
am Anfang
-
nach 5 Schritten
-
6. Schritt
- ) gefunden → 4
Elemente holen 4, +, 2, (
- berechne 2 + 4 →
6 auf Stack
![Beispielrechnung Schritt 1](../images/bild8.png)
- nach 11. Schritt
![Beispielrechnung Schritt 11](../images/bild9.png)
-
12. Schritt
- ) gefunden → 4
Elemente holen 3, -, 1, (
- berechne 1 - 3 →
-2 auf Stack
![Beispielrechnung Schritt 12](../images/bild10.png)
-
13. Schritt
- ) gefunden → 4
Elemente holen -2, *, 6, (
- berechne 6 * -2
→ -12 auf Stack
![Beispielrechnung Schritt 13](../images/bild11.png)
- Eingabe leer → Stack hat das Ergebnis
-
Beispiel-Implementierung von Stack:
-
benötigte Datenfelder
- Array als Speicher
- Zeiger auf oberstes Element
-
Hauptproblem
- Array hat feste Größe → Stack kann voll
werden
- schnelle Lösung: Ausnahme bei
Stack-Überlauf
- alternativ Liste
statt Array verwenden
-
Methoden leicht geschrieben
- IntStack.java
- Ausnahmen bei Zugriff auf leeren Stack oder
Stack-Überlauf fehlen
-
Wachsender Stack mit Array:
-
Problem
- Arraygröße am Anfang festgelegt
- Array kann später nicht vergrößert werden
-
Lösung
- bei Überlauf größeres Array anlegen
- Werte vom alten ins neue kopieren
-
um wieviel vergrößern?
- um einen → zu viel Kopieraufwand bei
häufigem Wachstum
- jedesmal um einen festen Wert (z.B. 100 neue
Werte)
- jedesmal auf doppelte Größe
-
Warteschlange (Queue):
- FIFO-Speicher (First In First
Out)
-
Grundoperationen analog zum Stack
- enter(e) // hinten
anstellen
- e = leave() // vorne
herausnehmen
- empty() // ist die
Warteschlange leer?
-
Grundstruktur bei der Verteilung von Ressourcen, z.B.
- Prozessverwaltung im Betriebssystem
- Druckaufträge
- Puffer bei nachrichtenübertragung
- Implementierung etwas schwieriger als Stack, da es
zwei Zugriffsenden gibt
-
Aufgaben: