Stapel (Stack)

4.1. Stapel (Stack)#

4.1.1. Motivation: Undo-Funktion#

Du willst eine App programmieren, die eine “Rückgängig”-Funktion bietet, wie du sie von Textverarbeitungsprogrammen oder Zeichen-Apps kennst. Diese Funktion soll alle letzten Aktionen in umgekehrter Reihenfolge rückgängig machen können.

Ein Stack (Stapel) ist eine perfekte Datenstruktur für diese Aufgabe, da er nach dem Prinzip “Last In, First Out” (LIFO) funktioniert – die letzte Aktion, die du gemacht hast, ist die erste, die rückgängig gemacht wird.

Beispiel: “Rückgängig” in einer Mal-App

Angenommen, du programmierst eine Zeichen-App. Jedes neue Element der Zeichnung, das der Nutzer einfügt, wird auf den Stack gelegt.

  1. Der Nutzer zeichnet zuerst eine Linie – die Aktion wird auf den Stapel gelegt.

  2. Dann fügt er einen Kreis hinzu – auch diese Aktion wird auf den Stapel gelegt.

  3. Schließlich zeichnet er ein Quadrat – auch diese Aktion wird oben auf den Stapel gelegt.

Der Stack sieht jetzt so aus:

  • Quadrat (oben)

  • Kreis

  • Linie (unten)

Jetzt will der Nutzer eine Aktion rückgängig machen. Wenn er auf “Rückgängig” klickt, nimmst du das oberste Element (das Quadrat) vom Stapel. Das Quadrat verschwindet als erstes.
Der Nutzer klickt ein weiteres Mal auf “Rückgängig”. Jetzt wird der Kreis vom Stapel genommen und verschwindet.

4.1.2. Übungen: Stacks sinnvoll einsetzen#

Wichtig

Die wichtigste Operationen für Stacks sind:

  • push: Ein Element auf den Stapel legen.

  • pop: Das oberste Element vom Stapel entfernen.

  • top: Das oberste Element ansehen, ohne es zu entfernen.

Aufgabe 1: Grundlegende Stack-Operationen#

Gegeben sei ein leerer Stack st. Führe die folgenden Operationen durch und gib den Zustand des Stacks nach jeder Operation an.

  1. st.push(5)

  2. st.push(10)

  3. st.pop()

  4. st.push(20)

  5. st.push(15)

  6. st.pop()

  7. st.push(25)

Notiere den Zustand von st nach jedem Schritt.

Lösung

  1. st.push(5): (5)

  2. st.push(10): (5, 10) (von unten nach oben, d.h. 5 liegt unten, 10 oben)

  3. st.pop(): (5)

  4. st.push(20): (5, 20)

  5. st.push(15): (5, 20, 15)

  6. st.pop(): (5, 20)

  7. st.push(25): (5, 20, 25)

Im Endzustand liegt also die 25 ganz oben, die 5 unten.

Aufgabe 2: Zeichenkette umdrehen#

Du hast die Zeichenkette bzw. den String “KITAMROFNI”. Beschreibe, wie du mit einem Stack st die Zeichenkette in ihre korrekte Form umkehren kannst. Schreibe die Schritte auf, die du ausführen würdest.

Lösung

  1. Lege nacheinander alle Buchstaben von “KITAMROFNI” auf den Stack (beginnend beim ersten Buchstaben „K „).

  2. Nimm nun nacheinander alle Buchstaben vom Stack und füge sie zu einer neuen Zeichenkette zusammen.

Aufgabe 3: Bücher stapeln#

Angenommen, du hast einen Stapel Bücher. Jedes Buch kann auf ein anderes gelegt oder von oben abgenommen werden. Wie kannst du vorgehen, um einen bestimmten Buchtitel aus der Mitte des Stapels zu entfernen? Beschreibe die Vorgehensweise und welche Einschränkungen es dabei gibt.

Lösung

Um ein bestimmtes Buch aus der Mitte des Stapels zu entfernen, wäre es hilfreich, einen zweiten Stapel zu verwenden:

  1. Nimm nacheinander die Bücher vom ursprünglichen Stapel st1 und lege sie auf einen zweiten Stapel st2. Das machst du so lange, bis du das gesuchte Buch erreicht hast.

  2. Entferne das gesuchte Buch aus st1.

  3. Danach nimmst du die Bücher vom zweiten Stapel st2 wieder herunter und legst sie zurück auf den ursprünglichen Stapel st1. So stellst du den Stapel fast wieder in seinen ursprünglichen Zustand her – nur das gewünschte Buch fehlt jetzt.

Aufgabe 4: Ist der Term korrekt geklammert?#

Gegeben sei der Ausdruck 5 + (3 * (2 + 1))) - (4 / (6 + 2) + 7. Bestimme, ob die Klammern korrekt geöffnet und geschlossen wurden. Beschreibe, wie ein Stack st verwendet werden kann, um dies zu überprüfen.

Lösung

Der Ausdruck im Beispiel ist nicht korrekt geklammert. Nach dem Teil “2 + 1” werden drei Klammern geschlossen, obwohl bis dahin erst zwei geöffnet wurden.

Grundidee für die allgemeine Lösung:

  • Gehe den Ausdruck von links nach rechts durch. Ignoriere dabei alle Zahlen und betrachte nur die Klammern.

  • Öffnende Klammern werden auf den Stack gelegt.

  • Wenn du auf eine schließende Klammer triffst, nimmst du die oberste (öffnende) Klammer vom Stack.

  • Wenn am Schluss der Stack wieder leer ist, ist der Ausdruck korrekt geklammert.

Wenn der Ausdruck nicht korrekt geklammert ist, kann dabei an verschiedenen Stellen etwas schiefgehen. Überlege wo!

Wenn du das Verfahren noch genauer verstehen willst, klappe die detaillierte Lösung auf:

Lösung 2

Allgemein kann man eine solche Überprüfung wie folgt durchführen:

  1. Gehe den Ausdruck von links nach rechts durch.

  2. Jedes Mal, wenn eine öffnende Klammer ( gefunden wird, lege sie auf den Stack st. So wird jeder Klammer eine passende schließende Klammer zugeordnet.

  3. Wenn eine schließende Klammer ) gefunden wird, prüfe zuerst, ob der Stack leer ist:

    • Falls der Stack leer ist, bedeutet dies, dass eine schließende Klammer ohne passende öffnende Klammer vorhanden ist. An dieser Stelle wird erkannt, dass der Ausdruck nicht korrekt geklammert ist.

  4. Ist der Stack nicht leer, nimm die oberste Klammer vom Stack herunter (pop()). Das entspricht dem Schließen einer der offenen Klammern.

  5. Setze diesen Vorgang fort, bis du alle Zeichen des Ausdrucks durchgegangen bist.

  6. Am Ende: Prüfe, ob der Stack leer ist:

    • Falls der Stack nicht leer ist, gibt es mehr öffnende Klammern als schließende, und der Ausdruck ist nicht korrekt geklammert.

    • Ist der Stack leer, sind alle Klammern korrekt geöffnet und geschlossen. Der Ausdruck ist somit korrekt geklammert.

Wenn dir das Prinzip klar ist, kannst du jetzt bestimmt auch das Parsons-Problem in der folgenden Aufgabe lösen!

Korrekte Klammerung in Python (Parsons Problem)#

Betrachte noch einmal die vorige Aufgabe. Wie könnte man in einem Programm prüfen, ob ein mathematischer Ausdruck term korrekt geklammert ist?

Bringe im folgenden Parsons-Problem den Code für die Methode def ist_korrekt_geklammert(term: str) in die richtige Reihenfolge:

4.1.3. Stapel als UML-Klassendiagramm modellieren#

Das Klassendiagramm Abb. 4.1 zeigt die Modellierung des Datentyps Stapel aus der Formelsammlung. Wie beim UML-Diagram der verketteten Liste nutzt man die Hilfsklasse Knoten um die Elemente auf dem Stack in der richtige Reihenfolge zu speichern.

../_images/kd_stack_fosa.svg

Abb. 4.1 Klassendiagramm für den Datentyp Stapel/Stack (FoSa 5.2)#

In gewissem Sinn ist diese Umsetzung des Stacks einfach eine “abgespeckte” Liste, denn die beiden Operationen push und pop entsprechen bei der Liste genau den folgenden Operationen:

Was entspricht den Stack-Operationen push und pop bei Listen?

  • einfuegenVorne entspricht push

  • entfernenVorne entspricht pop

Warum? Stell dir die Liste einfach um 90 Grad gedreht vor, mit dem Listenkopf ganz oben. Schon hast du einen Stapel! Und da “pusht” und “popt” man eben immer am Listenkopf…

4.1.4. Stapel implementieren#

Diskussion: Möglichkeiten einen Stack zu implementieren#

Im vorigen Absatz hast du gesehen, dass Stapel verketteten Listen recht ähnlich sind. Für die Implementierung haben wir darum nun auch mehrere Möglichkeiten:

  1. Wir implementieren die Klasse Stapel ganz neu, orientieren uns dabei aber natürlich an VerketteteListe.

  2. Wir nutzen Vererbung: Entweder

    1. Stapel wird eine Unterklasse von VerketteteListe oder

    2. VerketteteListe wird eine Unterklasse von Stapel.

  3. Wir nutzen Assoziation (hier genauer gesagt sogar Komposition), indem wir intern in der Klasse Stapelein Attribut vom Typ VerketteteListe nutzen und manche Aufgabe an dieses “abtreten”.

Diskutiert: Welche Vor- und Nachteile haben diese Möglichkeiten?

Hier einige Punkte, die das Ergebnis eurer Diskussion sein könnten.

  1. Neue Implementierung (keine Vererbung, keine Komposition)

    • Vorteile:

      • Sehr flexibel, da die Implementierung des Stapel unabhängig ist und an die spezifischen Anforderungen von Stapeln angepasst werden kann.

      • Kein direkter Zusammenhang zur VerketteteListe, wodurch eine zu enge Kopplung der beiden Klassen vermieden wird, die ja eigentlich doch sehr unterschiedliche Bedeutungen haben.

    • Nachteile:

      • Doppelte Arbeit, da Funktionen der VerketteteListe (wie etwa das Hinzufügen oder Entfernen von Elementen) erneut implementiert werden müssen.

      • Mehr Fehlerpotenzial und weniger Wartbarkeit, da die gleiche Logik an zwei Stellen existiert.

  2. Vererbung

    • 2.1 Stapel als Unterklasse von VerketteteListe:

      • Vorteile:

        • Stapel erbt alle Methoden der VerketteteListe, wodurch keine doppelte Implementierung notwendig ist.

        • Einfach zu erweitern, wenn VerketteteListe bereits gut getestet und robust ist.

      • Nachteile:

        • Stapel erbt auch die Methoden von VerketteteListe, die er gar nicht braucht. Man müsste dann irgendwie verhindern, dass diese benutzt werden können.

        • Ein Stapel ist nicht “eine Art von” VerketteteListe, sondern ein abstrakter Datentyp (ADT), den man auch durchaus anders implemtieren könnte als durch eine VerketteteListe. Durch die Verwendung von Vererbung wird fälschlicherweise suggeriert als gäbe es hier eine “ist ein”-Beziehung.

        • Erzeugt eine enge Kopplung zwischen den beiden Klassen, was zukünftige Änderungen erschweren könnte.

    • 2.2 VerketteteListe als Unterklasse von Stapel:

      • Vorteile:

        • Der Stapel bringt quasi schon zwei Methoden mit, die die VerketteteListe auch braucht. Sie könnte diese also einfach erben und wir hätten uns damit Arbeit gespart.

      • Nachteile:

        • Verletzung des “Ist-eine”-Prinzips der Vererbung, da eine VerketteteListe kein Stapel ist.

        • Noch unlogischer als Variante 2.1 und führt zu einem sehr verwirrenden Klassendesign.

  3. Komposition (Assoziation):

    • Vorteile:

      • Trennung der Verantwortlichkeiten: Die Klasse Stapel nutzt die VerketteteListe intern, wodurch die Datenstruktur leicht durch eine andere (z. B. ein Array) ausgetauscht werden kann.

      • Flexibilität: Änderungen an der VerketteteListe-Implementierung müssen nicht zwingend die Stapel-Klasse beeinflussen.

      • Entspricht dem Prinzip “Komposition über Vererbung”, da ein Stapel eine spezielle Datenstruktur ist, die auf einer verketteten Liste basiert.

    • Nachteile:

      • Erfordert ein gutes Verständnis von Assoziation und Komposition - das üben wir aber!

      • Wahrscheinlich könnten wir mit einer komplett neuen Implementation (minimal!) Speicherplatz und Rechenzeit sparen, weil wir kein zusätzliches Listenobjekt benötigen würden.

Fazit: Die Nutzung von Komposition (also die interne Verwendung der VerketteteListe in der Stapel-Klasse) ist in diesem Fall am sinnvollsten. Sie ermöglicht die klarste Trennung der Verantwortlichkeiten und bietet die größte Flexibilität.

Die Vererbung mag auf den ersten Blick praktisch sein, passt aber nicht wirklich zur Idee der Vererbung. Denn ein Stapel ist keine Art von VerketteteListe, sondern ein Datentyp, den man unter anderem mit verketteten Listen umsetzen kann, aber nicht zwingend. Auf keinen Fall herrscht zwischen den beiden Klassen eine “ist ein”-Beziehung.

Eine komplett neue Implementierung mag dir zwar maximale Freiheit bieten, hat aber den Nachteil, dass sie zusätzlichen Entwicklungsaufwand erfordert und fehleranfällig sein kann, weil du viele Funktionen der VerketteteListe doppelt programmieren müsstest.

Variante 1: Stapel neu implementieren#

class Knoten:
    def __init__(self, inhalt, naechster=None):  # Wenn für naechster kein Wert angegeben wird, ist er None (Standardwert)
        self.inhalt = inhalt
        self.naechster = naechster

class Stapel:
    def __init__(self):
        self.anfang: Knoten|None = None

    def push(self, daten):
        """legt ein neues Element auf den Stapel"""
        neuer_knoten = Knoten(daten, self.anfang)  # Der neue Knoten zeigt auf den bisherigen Anfang
        self.anfang = neuer_knoten  # Der neue Knoten ist jetzt der Anfang

    def pop(self):
        """entfernt das oberste Element vom Stapel und gibt es zurück"""
        if self.anfang is None:
            raise IndexError("Pop-Operation auf leerem Stapel nicht möglich")
        inhalt = self.anfang.inhalt  # Inhalt des ersten Knotens merken
        self.anfang = self.anfang.naechster  # Anfang auf den nächsten Knoten setzen
        return inhalt

    def top(self):
        """gibt das oberste Element zurück, ohne es zu entfernen"""
        if self.anfang is None:
            raise IndexError("Top-Operation auf leerem Stapel nicht möglich")
        return self.anfang.inhalt

    def ist_leer(self):
        """gibt True zurück, wenn der Stapel leer ist, sonst False"""
        return self.anfang is None  # Kurzform für if self.anfang is None: return True else: return False
    
    def anzahl_elemente(self):
        """gibt die Anzahl der Elemente auf dem Stapel zurück"""
        # ACHTUNG: Diese Methode ist ineffizient, da sie die gesamte interne Liste durchlaufen muss!
        anzahl = 0
        knoten = self.anfang
        while knoten is not None:
            anzahl += 1
            knoten = knoten.naechster
        return anzahl


# Beispielverwendung
st = Stapel()
st.push(5)
st.push(10)
print(st.pop())  # Ausgabe: 10
st.push(20)
st.push(15)
print(st.pop())  # Ausgabe: 15
st.push(25)
print(st.top())  # Ausgabe: 25
print(st.ist_leer())  # Ausgabe: False

10
15
25
False

Variante 2: Vererbung (schlechte Idee!)#

Warnung

Die Variante, dass Stapel von VerketteteListe erbt (oder gar umgekehrt), ist eine schlechte Idee(s. Diskussion: Möglichkeiten einen Stack zu implementieren). Deswegen zeigen wir sie hier auch erst gar nicht!

Variante 3: Stapel nutzt intern eine verkettete Liste (Komposition)#

Hide code cell content 
# Diese Zelle kannst du ausblenden, sie enthält nur unseren alten Code für Verkettete Listen

from __future__ import annotations  
from typing import Any

class Knoten:
    def __init__(self, inhalt):
        """ Konstruktor für die Klasse Knoten: speichert den Inhalt und legt
        eine Referenz auf den nächsten Knoten an. """
        self.inhalt: Any = inhalt   # Any = inhalt kann beliebiger Datentyp sein
        self.naechster: Knoten|None = None    # Typ-Annotation: naechster ist ein Knoten oder None

    def __str__(self):
        return str(self.inhalt)
    
class VerketteteListe:
    def __init__(self):
        self.erster: Knoten|None = None   # Der erste Knoten in der Liste (Listenkopf)    

    def __str__(self) -> str:
        """ Gibt die Liste als Zeichenkette, getrennt durch Pfeile, zurück. """
        inhalte = []
        knoten = self.erster
        while knoten is not None:
            inhalte.append(knoten.inhalt)
            knoten = knoten.naechster
        return " -> ".join(inhalte)

    def einfuegen_vorne(self, pInhalt):
        """Fügt einen neuen Knoten mit pInhalt am Anfang der Liste ein."""
        neu = Knoten(pInhalt)   # "Verpacke" den Inhalt in einen Knoten
        neu.naechster = self.erster  # Nachfolger des neuen Knotens ist der bisherige Listenkopf
        self.erster = neu  # Der neue Knoten ist ab jetzt der Listenkopf
    
    def ist_leer(self) -> bool:
        """gibt True zurück, wenn die Liste leer ist, sonst False"""
        if self.erster is None:
            return True
        else:
            return False

    def anzahl_elemente(self) -> int:
        """gibt die Anzahl der Elemente in der Liste zurück"""
        anzahl = 0
        aktuell = self.erster
        while aktuell is not None:
            anzahl += 1
            aktuell = aktuell.naechster
        return anzahl
    
    def gib_inhalt(self, index: int) -> Any:
        """gibt den Inhalt des Knotens an der Stelle index zurück"""
        if self.erster is None:
            return None
        aktuell = self.erster
        for i in range(index):
            if aktuell.naechster is None:
                return None
            aktuell = aktuell.naechster
        return aktuell.inhalt
    
    def ersetzen(self, index: int, neuer_inhalt: Any) -> None:
        """ersetzt den Inhalt des Knotens an der Stelle index durch neuer_inhalt"""
        if self.erster is None:
            return None
        aktuell: Knoten = self.erster 
        for i in range(index):
            if aktuell.naechster is None:
                return
            aktuell = aktuell.naechster
        aktuell.inhalt = neuer_inhalt

    def enthaelt(self, inhalt: Any) -> bool:
        """gibt True zurück, wenn inhalt in der Liste enthalten ist, sonst False"""
        aktuell = self.erster
        while aktuell is not None:
            if aktuell.inhalt == inhalt:
                return True
            aktuell = aktuell.naechster
        return False
    
    def anhaengen(self, inhalt: Any) -> None:
        """hängt einen neuen Knoten mit dem Inhalt inhalt ans Ende der Liste an"""
        neu = Knoten(inhalt)
        aktuell = self.erster
        if aktuell is None:
            self.erster = neu
            return
        while aktuell.naechster is not None:
            aktuell = aktuell.naechster
        aktuell.naechster = neu
           
    def entfernen_vorne(self) -> Any:
        """entfernt den ersten Knoten und gibt dessen Inhalt zurück"""
        if self.erster is None:
            return None
        inhalt = self.erster.inhalt
        self.erster = self.erster.naechster
        return inhalt

class Stapel:
    def __init__(self):
        # Wir verwenden eine VerketteteListe als interne Datenstruktur und
        # lassen diese die eigentliche Arbeit machen.
        # Komposition: Die Klasse Stapel besteht aus einer VerkettetenListe bzw.
        # steht mit VerketteteListe in einer "Has-A"-Beziehung.

        self._hilfsliste = VerketteteListe()

    def push(self, inhalt: Any) -> None:
        """legt ein neues Element inhalt auf den Stapel"""
        self._hilfsliste.einfuegen_vorne(inhalt)  # Arbeit wird an die Hilfsliste delegiert

    def pop(self) -> Any:
        """entfernt das oberste Element vom Stapel und gibt es zurück"""
        if self.ist_leer():
            raise IndexError("Pop-Operation auf leerem Stapel nicht möglich")
        return self._hilfsliste.entfernen_vorne()  # Arbeit wird an die Hilfsliste delegiert

    def top(self) -> Any:
        """gibt das oberste Element des Stapels zurück, ohne es zu entfernen"""
        if self.ist_leer():
            raise IndexError("Top-Operation auf leerem Stapel nicht möglich")
        return self._hilfsliste.gib_inhalt(0)  # Arbeit wird an die Hilfsliste delegiert

    def ist_leer(self) -> bool:
        """gibt True zurück, wenn der Stapel leer ist, sonst False"""
        return self._hilfsliste.ist_leer()  # Arbeit wird an die Hilfsliste delegiert

    def anzahl_elemente(self):
        """gibt die Anzahl der Elemente auf dem Stapel zurück"""
        # ACHTUNG: Diese Methode ist ineffizient, da sie die gesamte interne Liste durchlaufen muss!
        return self._hilfsliste.anzahl_elemente()


# Beispielverwendung
st = Stapel()
st.push(5)
st.push(10)
print(st.pop())  # Ausgabe: 10
st.push(20)
st.push(15)
print(st.pop())  # Ausgabe: 15
st.push(25)
print(st.top())  # Ausgabe: 25
print(st.ist_leer())  # Ausgabe: False

10
15
25
False
Inhalt