Ein Stack (Stapelspeicher, Kellerspeicher) ist eine dynamische Datenstruktur. Elemente können nur oben auf dem Stapel abgelegt oder von oben entnommen werden. Das heißt, das letzte Element, das abgelegt wurde, wird als erstes entnommen. Daher bezeichnet man diese Datenstruktur auch als LIFO (Last-In-First-Out) Struktur.
Verwendet wird diese Datenstruktur von vielen Compilern, um Argumente, lokale Variablen, den Rückgabewert und die Rücksprungadresse bei einem Methodenaufruf abzulegen.
Die wichtigsten Zugriffsmethoden eines Stacks sind:
- push(x) – legt das Element x auf den Stack
- pop() – entnimmt das oberste Element und gibt es zurück
- peek() – gibt das Element zurück ohne den Stack zu verändern
Im folgenden Beispiel sieht man die Umsetzung eines generischen Stacks. Der Stack wurde mit Hilfe eines Arrays implementiert.
import java.util.Arrays;
public class Stack<T> {
private Object[] data;
private int sp;
public Stack() {
data = new Object[10];
sp = 0;
}
public void push(T elem) {
if (sp == data.length) {
data = Arrays.copyOf(data, 2 * data.length);
}
data[sp++] = elem;
}
@SuppressWarnings("unchecked")
public T pop() {
return (T) data[--sp];
}
public int size() {
return sp;
}
}
Eine interessante Anwendung des Stacks ist die umgekehrte polnische Notation, mit der Taschenrechner realisiert wurden. Diese Notation erlaubt die Formulierung beliebig komplizierter mathematischer Ausdrücke ohne Klammern.
Im Folgenden wird die Anwendung eines Stacks anhand eines Beispiels der umgekehrten polnischen Notation erläutert.
2 + (3 * 4) =========== | | | | | | | | | | | | | | | 4 | | | | | | | | 3 | | 3 | | 12 | | | | 2 | | 2 | | 2 | | 2 | | 14 | ----- ----- ----- ----- ----- push(2) push(3) push(4) * +
Mit Hilfe unserer Stack-Implementierung kann diese Berechnung folgendermaßen ausgeführt werden:
Stack<Integer> st = new Stack<>();
st.push(2);
st.push(3);
st.push(4);
System.out.println(st); // Ausgabe: 2, 3, 4,
st.push(st.pop() * st.pop());
System.out.println(st); // Ausgabe: 2, 12,
st.push(st.pop() + st.pop());
System.out.println(st); // Ausgabe: 14,