Stapel (Stack)

Der Stapel (engl. Stack) ist eine der wichtigsten Grundstrukturen der Informatik. Er funktioniert nach dem Prinzip, dass man bildlich gesprochen Elemente stapelt und immer nur auf das oberste Element des Stapels zugreifen kann um es zu lesen oder zu entfernen. Stapel werden daher im Englischen auch mit LIFO abgekürzt:

LIFO: Last In First Out

Hierdurch ergeben sich die typischen Operationen die für einen Stapel (in englisch) definiert sind:

Operation Erklärung Aufwand
peek Lesen der obersten Datenstruktur ohne sie zu entfernen O(1)
pop Lesen der obersten Datenstruktur und gleichzeitiges Entfernen O(1)
push Einfügen einer neuen Datenstruktur als oberste Datenstruktur O(1)
search Suche nach einer Datenstruktur im Stapel und Rückgabe der Position (naive Implementierung) O(n)

Java verfügt bereits über eine Implementierung von Stapeln in der Klasse java.util.Stack in der die oben genannten Operationen als Methoden für beliebige Instanzen der Klasse Object zur Verfügung stehen.

Stapel sind im realen Leben nicht ganz so häufig anzutreffen wie in der Informatik. Ein sehr gutes Beispiel aus dem realen Leben sind

  • Teller die typischerweise aufeinander gestapelt werden. Der letzte Teller den man auf einen Stapel von Tellern legt ist auch typischerweise der erste Teller den man wieder von einem Stapel nimmt.
  • Passagiere die eine Flugzeug besteigen und es dann in umgekehrter Reihenfolge verlassen. (Die strenge Implementierung eines Stapel/Stacks ohne Ausnahmen ist hier weder für die Fluggesellsschaft noch für die Passagiere akzeptabel) 
  • Eine Einzelgarage mit einem Fahrzeugabstellplatz vor der Garage. Dies ist ein Stapel/Stack der Tiefe zwei
  • Ein Abstellgleis mit Prellbock.

In der Informatik sind Stapel sehr nützlich, wann immer man einen Zustand speichern muss um sich etwas Anderem zu widmen, und dann wieder auf den alten Zustand zurückzugreifen. Beispiele hierfür sind

  • Verwalten von Variablen bei Methodenaufrufen in Java: Beim jedem Aufruf einer Methode werden die Variablen der aktuellen Methode auf von den Variablen der aufgerufenen Methode verdeckt(Push). Die Variablen der aufgerufenen Methode sind eine Datenstruktur die neu auf den Stapel gelegt wurden und die Variablen der alten Methode verdecken. Nach dem Abarbeiten der neuen Methode werden deren Variablen wieder gelöscht(Pop) und die Variablen der vorhergehenden Methode stehen wieder zur Verfügung
  • Parsen (Analysieren) von Programiersprachen, Ausdrücken und Termen wie zum Beispiel ein mathematischer Term: 5 + 4*3. Hier wird bei der Analyse  von 5 und "+" festgestellt, dass der zweite Operand (4*3) selbst wieder ein Term ist. Das Parsen der Addition wird angehalten. Die nötigen Datenstrukturen zum Parsen der Multiplikation werden angelegt und verdecken die Addition(Pop). Der Wert von 4*3 wird berechnet. Alle Datenstrukturen die zur Berechnung der Multiplikation benötigt wurden können jetzt wieder gelöscht werden (POP) um mit der ursprünglichen Multiplikation fortzufahren. 

Beispiel: Die Auswertung des Terms 5+4*3