Stack

Ein Stack ist eine Datenstruktur nach dem Last In, First Out (LIFO) Prinzip - wie ein Stapel Teller, wo du immer nur von oben nehmen und hinzufügen kannst.

Was zuletzt draufgelegt wurde, wird zuerst wieder genommen.

Grundprinzip

LIFO - Last In, First Out

     ┌───┐
     │ 3 │  ← Top (oben) - zuletzt hinzugefügt, wird zuerst genommen
     ├───┤
     │ 2 │
     ├───┤
     │ 1 │  ← Bottom (unten) - zuerst hinzugefügt
     └───┘

Wie ein Stapel Teller:

Du kannst nur den obersten Teller nehmen oder einen neuen oben drauflegen - nie in der Mitte oder unten!

Operationen

Grundlegende Operationen:

1. push() - Element hinzufügen

Legt ein neues Element oben auf den Stack.

stack.push(1);  // [1]
stack.push(2);  // [1, 2]
stack.push(3);  // [1, 2, 3] ← 3 ist oben

Komplexität: O(1) - konstante Zeit

2. pop() - Element entfernen

Entfernt das oberste Element und gibt es zurück.

int element = stack.pop();  // 3
// Stack ist jetzt: [1, 2]

Komplexität: O(1)

3. peek() / top() - Oberstes Element anschauen

Gibt oberstes Element zurück ohne es zu entfernen.

int top = stack.peek();  // 2 (bei Stack [1, 2])
// Stack bleibt: [1, 2]

Komplexität: O(1)

4. isEmpty() - Ist Stack leer?

Prüft ob Stack leer ist.

boolean leer = stack.isEmpty();  // true oder false

Komplexität: O(1)

5. size() - Anzahl Elemente

Gibt Anzahl der Elemente zurück.

int anzahl = stack.size();  // z.B. 3

Komplexität: O(1)

Implementierung in Java

Mit Java Stack-Klasse:

import java.util.Stack;

public class StackBeispiel {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // Push - Elemente hinzufügen
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Stack: " + stack);  // [10, 20, 30]

        // Peek - Oberstes anschauen
        System.out.println("Top: " + stack.peek());  // 30

        // Pop - Oberstes entfernen
        int removed = stack.pop();
        System.out.println("Entfernt: " + removed);  // 30
        System.out.println("Stack: " + stack);  // [10, 20]

        // isEmpty
        System.out.println("Leer? " + stack.isEmpty());  // false

        // Size
        System.out.println("Größe: " + stack.size());  // 2
    }
}

Eigene Implementierung mit Array:

public class MyStack {
    private int[] arr;
    private int top;  // Index des obersten Elements
    private int capacity;

    public MyStack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;  // -1 bedeutet leer
    }

    public void push(int element) {
        if (isFull()) {
            throw new RuntimeException("Stack ist voll!");
        }
        arr[++top] = element;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack ist leer!");
        }
        return arr[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack ist leer!");
        }
        return arr[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == capacity - 1;
    }

    public int size() {
        return top + 1;
    }
}

Anwendungsfälle

1. Rückgängig-Funktion (Undo)

Stack<String> history = new Stack<>();

// Änderungen speichern
history.push("Text eingegeben");
history.push("Formatierung geändert");
history.push("Bild eingefügt");

// Rückgängig machen
String letzte = history.pop();  // "Bild eingefügt" rückgängig

Beispiel:

• Texteditor (Strg+Z)
• Photoshop Undo
• Browser Zurück-Button

2. Klammerprüfung

boolean pruefeKlammern(String text) {
    Stack<Character> stack = new Stack<>();

    for (char c : text.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        }
        else if (c == ')' || c == '}' || c == ']') {
            if (stack.isEmpty()) return false;

            char top = stack.pop();
            if (!passt(top, c)) return false;
        }
    }

    return stack.isEmpty();  // Alle Klammern geschlossen?
}

boolean passt(char offen, char zu) {
    return (offen == '(' && zu == ')') ||
           (offen == '{' && zu == '}') ||
           (offen == '[' && zu == ']');
}

Beispiel:

pruefeKlammern("(a + b) * {c - [d]}");  // true
pruefeKlammern("(a + b");               // false
pruefeKlammern("(a + b})");             // false

3. Funktionsaufrufe (Call Stack)

Wenn Programm Funktionen aufruft, speichert CPU Rücksprungadressen auf einem Stack.

void main() {
    funktionA();        // Push Rücksprungadresse
}

void funktionA() {
    funktionB();        // Push Rücksprungadresse
}

void funktionB() {
    System.out.println("Hi");
    // Pop - zurück zu funktionA
}
// Pop - zurück zu main

Call Stack:

main → funktionA → funktionB
     ← (return)  ← (return)

4. Postfix-Notation berechnen

Mathematische Ausdrücke in umgekehrter polnischer Notation.

// "3 4 + 5 *" = (3 + 4) * 5 = 35
int berechnePostfix(String ausdruck) {
    Stack<Integer> stack = new Stack<>();

    for (String token : ausdruck.split(" ")) {
        if (istZahl(token)) {
            stack.push(Integer.parseInt(token));
        } else {
            int b = stack.pop();
            int a = stack.pop();

            if (token.equals("+")) stack.push(a + b);
            if (token.equals("-")) stack.push(a - b);
            if (token.equals("*")) stack.push(a * b);
            if (token.equals("/")) stack.push(a / b);
        }
    }

    return stack.pop();
}

5. Tiefensuche (DFS) in Graphen

Stack wird für Tiefensuche in Bäumen und Graphen verwendet.

void depthFirstSearch(Node start) {
    Stack<Node> stack = new Stack<>();
    Set<Node> besucht = new HashSet<>();

    stack.push(start);

    while (!stack.isEmpty()) {
        Node aktuell = stack.pop();

        if (!besucht.contains(aktuell)) {
            System.out.println("Besuche: " + aktuell);
            besucht.add(aktuell);

            for (Node nachbar : aktuell.getNachbarn()) {
                stack.push(nachbar);
            }
        }
    }
}

Vergleich mit anderen Datenstrukturen

Stack vs Queue

Stack vs Array

Vor- und Nachteile

Komplexität

Stack Overflow

Beispiel:

void unendlicheRekursion() {
    unendlicheRekursion();  // Kein Abbruch!
}
// Führt zu: java.lang.StackOverflowError

Vermeidung:

• Rekursion mit Abbruchbedingung
• Iterative Lösungen statt Rekursion
• Tail-Rekursion optimieren

Prüfungsrelevanz AP2

Typische Prüfungsfrage:

"Erkläre das LIFO-Prinzip eines Stacks und nenne drei praktische Anwendungsfälle."

Verwandte Konzepte

• Queue - FIFO-Datenstruktur
• Linked List - Kann als Stack verwendet werden
• Array - Basis für Array-Stack
• Rekursion - Nutzt implizit Call Stack
• Datenstrukturen - Übergeordnetes Konzept
• Algorithmen - Nutzen oft Stacks

Zusammenfassung

Merksatz:

"Last In, First Out - Was zuletzt drauf kommt, geht zuerst wieder runter!"

Die 3 Kern-Operationen:

1. push() - Oben drauflegen
2. pop() - Von oben nehmen
3. peek() - Oben anschauen ohne nehmen