Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Stack

Stack

Im Gegensatz zur Liste ist der Stack eine international standardisierte Datenstruktur.

ADT Stack: ggf. leere Folge von Elementen zusammen mit einem ggf. undefinierten Topelement

Bei einem Stack hat man jeweils nur Zugriff auf das oberste Element. Man kann dieses inspizieren oder entfernen. Ferner kann man ein neues Element auflegen. Womit das bisherige oberste Element erst einmal nicht mehr erreichbar ist. Nimmt man das neu aufgelegte Element jedoch wieder vom Stack herunter, so hat man wieder Zugriff auf das alte oberste Element.

| |
|X|  ←  Oberstes Element: - inspizieren
|X|                       - auflegen
|X|                       - entfernen
|X|
---

Beim Entfernen wird lediglich das Element vom Stack entfernt. Dieses wird jedoch nicht zurückgegeben. Bei Inspizieren wird das oberste Element zurückgegeben, es bleibt jedoch als oberstes Element auf den Stack und wir nicht etwa von diesem entfernt.

Auf einen Stack haben wir folgende Operationen:

newStack() $\rightarrow$ Stack
push(x, s) $\rightarrow$ Stack
pop(s) $\rightarrow$ Stack
top(s) $\rightarrow$ Element
isEmpty(s) $\rightarrow$ boolean

Durch die folgenden vier Axiome ist ein Stack eindeutig definiert. Wir nennen sie daher Stackaxiome:

s:Stack
x:Element
(A1) isEmpty(newStack()) = true
(A2) isEmpty(push(x, s)) = false
(A3) top(push(x, s)) = x
(A4) pop(push(x, s)) = s

Stacks lassen sich sowohl mit Hilfe von Arrays als auch mit Hilfe von Listen implementieren. Bei der Implementierung mit einem Array, muss das Array, sobald es vollständig gefüllt ist und ein weiteres Element eingefügt werden soll, in ein neues größeres Array umkopiert werden. Man wählt typischerweise ein doppelt so großes Array. Beim Einfügen eines Elements inkrementiert man den Arrayindex, beim Löschen dekrementiert man ihn. Man initialisiert ihn mit -1, so dass das erste Element am Index 0 eingefügt wird. Alle Operationen eines Stacks haben eine Laufzeit von ${\mathcal {O}}(1)$

String umkehren

Wir wollen bei einem gegebenen String die Reihenfolge der Buchstaben umkehren. Ein Stack bietet hier eine einfache Lösung. Wir legen geben die Buchstaben in der ursprünglichen Reihenfolge auf den Stack und entnehmen anschließen jeweils das oberste Element des Stacks und fügen es hinten an unseren entstehenden Resultatstring an. Die folgende Abbildung verdeutlicht dieses Vorgehen schematisch. Stacks sind, wie wir hier sehen gut geeignet, um Reihenfolgen umzukehren.

Die Funktion reverse überführt einen String in seine revertierte Version. Wir schreiben den String in einer Schleife zeichenweise auf den Stack. Als Resultat beginnen wir mit dem leeren String. Nun räumen wir den Stack mit einer while not isEmpty(s) Schleife wieder ab. In Körper der Schleife fügen wir das jeweilige oberste Element an unser Resultat an und nehmen anschließend das oberste Element von Stack herunter. Schließlich geben wir das Resultat zurück.

reverse(t : String) : String
  s := newStack()
  for i := 0 to t.length() -1
    push(t.charAt(i), s)
  n := ""
  while not isEmpty(s)
    n := n + top(s)
    pop(s)
  return n

Klammerung prüfen

Stacks haben auch viel mit symmetrischen Dingen zu tun. Beispielsweise sollte die Klammerung bei einem geklammerten Ausdruck symmetrisch sein. Betrachten wir folgenden Ausdruck aus runden und eckigen Klammern und untersuchen wir ob dieser korrekt geklammert ist.

Die Klammerpaare sind in der obigen Abbildung durch Unterstriche verdeutlicht. Man kann einen Stack auch hier geschickt einsetzen, um die Korrektheit der Klammerung zu überprüfen. Man verarbeitet die Eingabe zeichenweise von links nach rechts. Findet man eine öffnende Klammer, so legt man sie auf den Stack. Findet man eine schließende Klammer in der Eingabe und eine passende öffnende Klammer oben auf dem Stack, so nimmt man sie vom Stack herunter und fährt fort. Findet man eine schließende Klammer und ist der Stack leer oder enthält als Topelement keine passende öffnende Klammer, so hat man gezeigt, dass der Ausdruck falsch geklammert ist. Erreicht man das Ende der Eingabe, so ist der Ausdruck genau dann korrekt geklammert, wenn der Stack nun leer ist.

testeKlammerung(c : Char []) : boolean
  s := newStack()
  for i := 0 to c.length -1
    if c[i] = '(' or c[i] = '['
      push(c[i], s)
    else
      if   (
              (
                   ( c[i] = ')' and top(s) = '(' ) 
                or ( c[i] = ']' and top(s) = '[' ) 
              )
              and 
              ( 
                not isEmpty(s) 
              )
           )
        pop(s)
      else
        return false
  return isEmpy(s)

Infix nach Postfix konvertieren

Wir betrachten folgende Eingabe:

a * (b + c) - d / e

In Postfix Schreibweise lautet der Term entsprechend:

a b c + * d e / -

Auch hier hilft ein Stack diese Umwandlungsaufgabe einfach, zu lösen. Man betrachtet hier einen zunächst leeren Stack sowie eine zeichenweise Eingabe und eine zeichenweise Ausgabe, in welcher wir das Ergebnis erstellen. Wir gehen die Eingabe zeichenweise durch. Finden wir einen Operanden, so schreiben wir ihn in die Ausgabe. Finden wir einen Operator oder eine öffnende Klammer, so legen wir ihn bzw. sie auf den Stack. Bei einer schließenden Klammer lesen und entfernen wir solange Operatoren vom Stack und schreiben, sofern es sich um Operatoren handelt, diese in die Ausgabe, bis wir eine schließende Klammer vom Stack entfernt haben, die Klammer selbst verarbeiten wir nicht weiter.

Weiterhin müssen wir noch berücksichtigen, dass die Multiplikation eine höhere Priorität hat als die Addition (Punkt- vor Strichrechnung). Finden wir einen Operator der Strichrechnung in an der aktuellen Stelle der Eingabe vor, so löschen wir alle Punktrechnungsoperatoren vom Stack und schreiben diese unmittelbar in die Ausgabe. Anschließend legen wir den gefundenen Operator der Strichrechnung auf den Stack.