Algorithmen mit Stapeln

Ein Stapel kennt nur sein oberstes Element. Wer alle Elemente ansehen will, muss sie herunternehmen — und irgendwo ablegen.

• Umkehren:alle Elemente nacheinander pushen und danach alle poppen — die Reihenfolge dreht sich um.
• Durchsehen:solange !s.isEmpty(): oberstes Element mit pop() nehmen, bearbeiten, auf einen Hilfsstapel legen.
• Zurückladen:danach alles vom Hilfsstapel zurück — so steht der Originalstapel wieder wie vorher.
• Warum?Ein Stapel hat keine Operation getLength(); selbst die Anzahl bestimmt man so.

public int anzahl(Stack<String> s) {
    Stack<String> hilf = new Stack<String>();
    int n = 0;
    while (!s.isEmpty()) {       // umladen und zählen
        hilf.push(s.pop());
        n++;
    }
    while (!hilf.isEmpty()) {    // zurückladen
        s.push(hilf.pop());
    }
    return n;
}

Compiler und Taschenrechner prüfen vor dem Rechnen, ob Klammern richtig gesetzt sind. Die Idee: Jede öffnende Klammer wartet auf dem Stapel auf ihr Gegenstück.

• Öffnend:( [ { wird mit push auf den Stapel gelegt.
• Schließend:Stapel leer → Fehler. Sonst mit pop() die oberste öffnende Klammer holen — sie muss zur schließenden passen.
• Ende:Liegt noch etwas auf dem Stapel, fehlt eine schließende Klammer.

Sieh dir den Ausdruck an und tippe: korrekt geklammert oder fehlerhaft? Dann zeigt „Prüfen“, wie der Stapel Zeichen für Zeichen arbeitet.

Halte fest: Ein Klammerausdruck ist genau dann korrekt, wenn keine schließende Klammer auf einen leeren Stapel oder eine falsche Klammer trifft und der Stapel am Ende leer ist.