Datenstrukturen: Stack und Queue

Ein abstrakter Datentyp (ADT) beschreibt eine Datenstruktur über ihre Operationen und deren Verhalten, ohne die konkrete Implementierung festzulegen. Stack und Queue sind zwei der wichtigsten ADTs in der Informatik.

Ein Stack arbeitet nach dem LIFO-Prinzip (Last In, First Out): Das zuletzt hinzugefügte Element wird als erstes wieder entnommen – wie ein Stapel Teller.

Grundoperationen:

• push(element): Legt ein Element oben auf den Stack.
• pop(): Entfernt und gibt das oberste Element zurück.
• peek() / top(): Gibt das oberste Element zurück, ohne es zu entfernen.
• isEmpty(): Prüft, ob der Stack leer ist.

Alle Operationen haben die Laufzeit O(1).

public class Stack<T> {
    private Object[] daten;
    private int top = -1;

    public Stack(int kapazität) {
        daten = new Object[kapazität];
    }

    public void push(T element) {
        if (top == daten.length - 1)
            throw new RuntimeException("Stack voll");
        daten[++top] = element;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty())
            throw new RuntimeException("Stack leer");
        T element = (T) daten[top];
        daten[top--] = null;
        return element;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty())
            throw new RuntimeException("Stack leer");
        return (T) daten[top];
    }

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

Eine klassische Stack-Anwendung ist die Überprüfung korrekter Klammerung in Ausdrücken:

algorithmus klammerPrüfung(ausdruck):
    stack = neuer Stack
    für jedes Zeichen z in ausdruck:
        wenn z ist öffnende Klammer:
            stack.push(z)
        wenn z ist schließende Klammer:
            wenn stack.isEmpty():
                gib FALSCH zurück
            offen = stack.pop()
            wenn offen und z nicht zusammenpassen:
                gib FALSCH zurück
    gib stack.isEmpty() zurück

Beispiel: ((a+b)*c) → korrekt. ((a+b)*c → falsch (Klammer fehlt).

Eine Queue arbeitet nach dem FIFO-Prinzip (First In, First Out): Das zuerst hinzugefügte Element wird als erstes wieder entnommen – wie eine Warteschlange an der Kasse.

Grundoperationen:

• enqueue(element): Fügt ein Element am Ende der Queue ein.
• dequeue(): Entfernt und gibt das erste Element zurück.
• front() / peek(): Gibt das erste Element zurück, ohne es zu entfernen.
• isEmpty(): Prüft, ob die Queue leer ist.

Alle Operationen haben die Laufzeit O(1).

Eine effiziente Array-basierte Queue verwendet einen Ringpuffer (zirkuläres Array):

public class Queue<T> {
    private Object[] daten;
    private int head = 0, tail = 0, size = 0;

    public Queue(int kapazität) {
        daten = new Object[kapazität];
    }

    public void enqueue(T element) {
        if (size == daten.length)
            throw new RuntimeException("Queue voll");
        daten[tail] = element;
        tail = (tail + 1) % daten.length;
        size++;
    }

    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty())
            throw new RuntimeException("Queue leer");
        T element = (T) daten[head];
        daten[head] = null;
        head = (head + 1) % daten.length;
        size--;
        return element;
    }

    public boolean isEmpty() { return size == 0; }
}

Die Breitensuche (Breadth-First Search) in Graphen verwendet eine Queue, um Knoten ebenenweise zu besuchen:

algorithmus BFS(startknoten):
    queue = neue Queue
    besucht = neue Menge
    queue.enqueue(startknoten)
    besucht.add(startknoten)

    solange nicht queue.isEmpty():
        knoten = queue.dequeue()
        verarbeite(knoten)
        für jeden Nachbar n von knoten:
            wenn n nicht in besucht:
                besucht.add(n)
                queue.enqueue(n)

BFS findet stets den kürzesten Weg (in Kantenanzahl) in einem ungewichteten Graphen.

• Zugriffsprinzip: Stack = LIFO, Queue = FIFO
• Typische Anwendungen Stack: Funktionsaufrufe (Call Stack), Klammerprüfung, Undo-Funktionalität, Tiefensuche (DFS), Auswertung von Postfix-Ausdrücken
• Typische Anwendungen Queue: Breitensuche (BFS), Druckerwarteschlange, Prozess-Scheduling, Pufferung von Datenströmen
• Laufzeit aller Operationen: Beide O(1)

Abitur-Tipp: Im Abitur wird oft verlangt, den Zustand eines Stacks oder einer Queue Schritt für Schritt nach einer Folge von Operationen darzustellen. Übe dies mit konkreten Beispielen. Merke: Stack = LIFO (wie Tellerstapel), Queue = FIFO (wie Warteschlange). Typische Aufgabe: Implementiere eine Klammerprüfung oder erkläre, warum BFS eine Queue statt einen Stack verwendet.