Stapel und Warteschlange
- Wie lässt sich „Stapel und Warteschlange“ mit einem Modell erklären?
- Ist die Anweisung für jede Person eindeutig und endet der Ablauf sicher?
- Wie kann ich meine Lösung testen und verständlich dokumentieren?
Datenstruktur Stack
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.
Erklärung von Serlo Education e. V., lizenziert unter CC BY-SA 4.0 – Original bei Serlo, CC BY-SA 4.0, übernommen am 2026-09-03.
Schlau Fassung
Stapel und Warteschlange Ein Stapel arbeitet nach dem Prinzip zuletzt hinein, zuerst heraus. Eine Warteschlange nach zuerst hinein, zuerst heraus.
Stapel und Warteschlange ist in der Informatik kein isolierter Merksatz. Entscheidend ist, welche Daten oder Zustände am Anfang vorliegen, nach welcher Regel sie verarbeitet werden und wie sich das Ergebnis überprüfen lässt. Die Rückgängig-Funktion nutzt einen Stapel, der Druckerauftrag eine Warteschlange.
Beim Bearbeiten trennst du deshalb Beobachtung und Vermutung: Zuerst beschreibst du, was tatsächlich eingegeben, gespeichert, übertragen oder ausgegeben wird. Danach begründest du mit Fachbegriffen, warum der Ablauf so funktioniert.
Drei Bausteine, die du sicher können musst
Jeder Schritt ist ohne Raten ausführbar.
Der Ablauf erreicht nach endlich vielen Schritten ein Ende.
Eingabe und erwartetes Ergebnis prüfen einen bestimmten Weg.
Ausgearbeitetes Beispiel
Ausgangslage: Die Rückgängig-Funktion nutzt einen Stapel, der Druckerauftrag eine Warteschlange.
- Modell festlegen: Benenne Eingaben, gespeicherte Werte und die gewünschte Ausgabe.
- Regel anwenden: Formuliere die Verarbeitung so genau, dass eine andere Person jeden Schritt wiederholen kann.
- Ergebnis prüfen: Vergleiche die beobachtete Wirkung mit einer vorher notierten Erwartung und untersuche mindestens einen Randfall.
Begründung: Ein Stapel arbeitet nach dem Prinzip zuletzt hinein, zuerst heraus. Eine Warteschlange nach zuerst hinein, zuerst heraus. Dadurch wird nicht nur das Ergebnis, sondern auch sein Zustandekommen nachvollziehbar.
So gehst du informatisch vor
Fachbegriffe in eigenen Worten
- Eindeutigkeit
- Jeder Schritt ist ohne Raten ausführbar.
- Endlichkeit
- Der Ablauf erreicht nach endlich vielen Schritten ein Ende.
- Testfall
- Eingabe und erwartetes Ergebnis prüfen einen bestimmten Weg.
Aufgaben
- StartBegriffe sichern: Erkläre „Stapel und Warteschlange“ in mindestens vier Sätzen und verwende zwei Begriffe aus dem Glossar.
Musterlösung
Ein Stapel arbeitet nach dem Prinzip zuletzt hinein, zuerst heraus. Eine Warteschlange nach zuerst hinein, zuerst heraus. Die Rückgängig-Funktion nutzt einen Stapel, der Druckerauftrag eine Warteschlange. Eine vollständige Antwort benennt zusätzlich Eingabe oder Ausgangszustand, Verarbeitung und überprüfbares Ergebnis. - OrdnenModell bilden: Zerlege das Beispiel der Seite in Ausgangslage, Regel, Ergebnis und Test.
Musterlösung
Ausgangslage: die im Beispiel genannten Daten oder Geräte. Regel: der beschriebene Verarbeitungsschritt. Ergebnis: die sichtbare Wirkung. Test: ein normaler Fall und ein bewusst veränderter Randfall. - AnwendenSelbst lösen: Schreibe einen Algorithmus, der eine Figur vom Start durch ein 4-mal-4-Feld zum Ziel führt, ohne ein Hindernis zu berühren.
Musterlösung
Eine korrekte Lösung nennt Startposition und Blickrichtung und gibt jeden Schritt oder jede geprüfte Bedingung eindeutig an. - FehlersucheDiagnose: Verändere im Beispiel genau eine Voraussetzung. Sage vorher, welche Wirkung du erwartest, und begründe sie.
Lösungshinweis
Eine gute Lösung benennt die veränderte Voraussetzung, den betroffenen Verarbeitungsschritt und eine beobachtbare Ausgabe. Mehrere Dinge gleichzeitig zu ändern erlaubt keine eindeutige Ursache. - TransferNeuer Zusammenhang: Finde ein zweites Beispiel aus Schule oder Alltag und erkläre Gemeinsamkeit sowie Unterschied.
Lösungshinweis
Nutze dieselben Fachbegriffe, aber übertrage sie auf andere Daten, Geräte oder Regeln. Der Unterschied muss fachlich relevant sein und darf nicht nur den Namen betreffen. - ProfiVertiefung: Kürze eine lange Befehlsfolge durch eine Schleife und erkläre, warum beide Fassungen dasselbe leisten.
Lösungshinweis
Suche zuerst den kleinsten Abschnitt, der unverändert mehrfach vorkommt, und bestimme danach die Wiederholungszahl.
Weiterführende Aufgaben
Abgabe in fünf Teilen
- Ziel: Ein Satz, der messbar sagt, was funktionieren soll.
- Plan: Skizze, Ablaufplan, Tabelle oder Pseudocode.
- Produkt: Programm, Modell, Untersuchung oder dokumentierter Versuch.
- Tests: Normalfall, Randfall und mindestens ein absichtlich provozierter Fehler.
- Reflexion: Gefundener Fehler, vorgenommene Verbesserung und nächster sinnvoller Schritt.
Bewertungsraster für Partnerfeedback
- Fachlich richtig und mit passenden Begriffen erklärt
- Plan und Ergebnis stimmen sichtbar überein
- Tests sind reproduzierbar dokumentiert
- Quellen, Bilder und fremde Hilfen sind angegeben