Das Gegenstück zur Queue ist der Stack. Ein Stack ist ein Datenspeicher, der wie ein Stapel organisiert ist: Neue Daten werden oben auf den Stapel abgelegt. Und dort, am oberen Ende des Stapels, werden die Daten auch wieder gelesen und vom Stapel entnommen.
Anders als bei der Queue geht es also nicht der Reihe nach, sondern nach dem Prinzip last-in-first-out (LIFO). Stell dir einen Sachbearbeiter vor, der neu hereinkommende Vorgänge immer oben auf den Stapel legt und von dort wieder abarbeitet. Oder einen Kindergarten, der einen frei gewordenen Platz immer an diejenige Familie vergibt, die zuletzt angerufen hat. Nicht gerade fair!
Für diese Anwendungen ist der Stack nicht geeignet. Aber es gibt zahlreiche Anwendungen, für die der Stack genau der richtige Datenspeicher ist.
In der Abbildung (a) sind die Zahlen 1, 2, 3 bereits auf dem Stack abgelegt worden; die 4 kommt gerade hinzu. Das Ergebnis ist die Situation (b). In (c) wird die oberste Zahl wieder vom Stack entnommen, dieses ist die 4.
Es ist nicht möglich, auf irgendwelche beliebigen Datenelemente des Stacks zuzugreifen. Nur auf das am oberen Ende befindliche Datenelement ist ein Zugriff möglich. Dieses Datenelement kann gelesen und entnommen werden. Und genau dort, am oberen Ende, werden neue Datenelemente eingefügt.
In der deutschen Literatur wird auch der Begriff Keller für den Stack verwendet – gerade so, als würdest du Sachen einfach die Kellertreppe hinunterstoßen und von dort auch wieder zurückholen.
Der Stack im Alltag
Im täglichen Leben benutzt du deinen eingebauten Stack etwa in folgender Situation: Du stehst am Herd und kochst. Da klingelt das Telefon. Du speicherst auf deinem Stack, was du zuletzt an Zutaten in den Topf getan hast und gehst zum Telefon. Während du telefonierst, klingelt es an der Tür. Du speicherst auf deinem Stack, worüber du gerade am Telefon gesprochen hast und gehst an die Tür. Du nimmst die Paketsendung entgegen. Während du die Tür wieder zumachst, überlegst du: "Wo war ich stehen geblieben?" Dein oberster Stackeintrag sagt dir, dass du telefoniert hast und zuletzt über die Wochenendplanung gesprochen hast. Du entfernst diesen Eintrag vom Stack und gehst zurück zum Telefon und nimmst das Telefongespräch wieder auf. Nachdem du zu Ende telefoniert hast, überlegst du: "Wo war ich stehen geblieben?" Dein oberster Stackeintrag sagt dir, dass du beim Kochen warst und dass du zuletzt Bohnen in den Topf getan hast. Du entfernst diesen Eintrag vom Stack und gehst zurück zum Herd und kochst weiter.
Funktionsaufrufe in Programmiersprachen
Genau dieser Ablauf ist typisch für den Aufruf von Funktionen in Programmiersprachen. Wenn eine Funktion aufgerufen wird, springt das Programm in den Funktionskörper und arbeitet die dort befindlichen Anweisungen ab. Aber wie geht es dann weiter? Das Programm muss an die Stelle zurückkehren, von der aus es in den Funktionskörper gesprungen ist. Dies ist die sogenannte Rücksprungadresse, und diese wird zuvor beim Aufruf der Funktion im Aufrufstack des Computers gespeichert.
Es ist wichtig, dass ein solcher Aufrufstack vorhanden ist, denn eine aufgerufene Funktion kann ihrerseits eine weitere Funktion aufrufen, diese kann ihrerseits noch eine Funktion aufrufen usw. Alle jeweiligen Rücksprungadressen werden im Aufrufstack gespeichert. Und zusätzlich werden noch alle lokalen Daten der Funktionen dazu gespeichert, damit bei der Rückkehr in den Funktionskörper genau mit diesen Daten weitergearbeitet werden kann.
Dies entspricht genau deinem Vorgehen im täglichen Leben. Du speicherst die Rücksprungadressen "Herd" und "Telefon" und zusätzlich dazu die Daten "Bohnen kochen" und "Wochenende planen". So weißt du, wohin du zurückkehren musst und wo du anknüpfen musst.
Der Aufrufstack ist die wichtigste Anwendung des Stacks in der Informatik. Ohne ihn ist die Nutzung von Funktionen nicht möglich, insbesondere nicht von rekursiven Funktionen.
Anwendung
Es gibt eine ganze Reihe von weiteren wichtigen Anwendungen des Stacks. In der theoretischen Informatik verwendet der Stackautomat einen Stack. Bei der Tiefensuche in einem Graphen wird ein Stack verwendet. Bei der Auswertung von arithmetischen Ausdrücken ist ein Stack erforderlich, um Zwischenergebnisse zu speichern.
Vielfach nutzt du implizit den Aufrufstack, wenn du rekursiv programmierst. Ein Recursive-Descent-Parser etwa simuliert einen Stackautomaten und verwendet dabei den Aufrufstack quasi als dessen Stack. Auch die Tiefensuche in einem Graphen kannst du rekursiv implementieren, ebenso die Auswertung von arithmetischen Ausdrücken.
Du hast noch nicht genug vom Thema?
Hier findest du noch weitere passende Inhalte zum Thema:
