Informatik
Stapel & Schlangen
Zwei einfache Ordnungen für Daten: Was zuletzt kam, geht zuerst, oder wer zuerst kam, ist zuerst dran.
Das brauchst du vorher
Wenn du an der Kasse anstehst, weißt du genau, wer als Nächstes dran ist: die Person, die am längsten wartet. Wenn du Teller stapelst, nimmst du immer den obersten, also den, der zuletzt kam. Genau diese zwei Ordnungen nutzen Programme ständig, und sie haben Namen: Schlange und Stapel.
Der Stapel: zuletzt rein, zuerst raus
Ein Stapel funktioniert wie ein Tellerstapel: Neue Elemente legst du oben drauf, das nennt man push. Wegnehmen kannst du nur das oberste Element, das nennt man pop. Was zuletzt reinkam, kommt also zuerst wieder raus. Der Zurück-Button im Browser arbeitet genau so: Beim Weiterklicken wird die verlassene Seite oben auf den Stapel gelegt, und Zurück holt die oberste, also die zuvor besuchte Seite.
Die Zählung beginnt bei 0.
Die Schlange: zuerst rein, zuerst raus
Eine Schlange ist das genaue Gegenteil: Neue Elemente stellen sich hinten an, herausgenommen wird immer vorne. Wer zuerst kam, ist zuerst dran, wie an der Supermarktkasse. Für dich heißt das: Stehst du an Position 5, sind die Positionen 1 bis 4 vor dir dran, also vier Leute, und erst danach kommst du. Ein Drucker nutzt eine Schlange: Schicken drei Leute nacheinander etwas zum Drucken, druckt er die Aufträge genau in dieser Reihenfolge, keiner drängelt sich vor.
Wo Programme das brauchen
Stapel stecken überall dort, wo man Schritte rückgängig machen will: Rückgängig im Texteditor, der Zurück-Button, und sogar Funktionsaufrufe bei der landen auf einem Stapel. Schlangen stecken überall dort, wo Fairness zählt: Druckaufträge, Downloads, Nachrichten, die ein Server der Reihe nach abarbeitet. Die Frage ist immer dieselbe: Soll das Neueste zuerst dran sein oder das Älteste?
Aufgaben
0 von 6 gelöstZeit zum Ausprobieren. Du kannst nichts kaputt machen, jeder Versuch zählt.
Du legst nacheinander A, B und C auf einen Stapel. Welches Element bekommst du beim ersten pop?
Drei Druckaufträge kommen nacheinander an: zuerst von Emma, dann von Ben, dann von Lea. Wessen Auftrag druckt der Drucker zuerst?
Du legst 5 Elemente auf einen Stapel und nimmst danach 2 mit pop wieder herunter. Wie viele Elemente liegen noch auf dem Stapel?
Ordne jeden Begriff seiner Bedeutung zu.
In einer Warteschlange stehen 6 Personen. 2 werden bedient und gehen. Wie viele warten noch?
Ein Drucker arbeitet die Aufträge wie eine … ab: Wer zuerst kam, ist zuerst dran.
Damit geht es weiter