Stapel und Schlange
Über diese App
Dieselbe Folge von push und pop auf einem Stapel und in einer Schlange: Was kommt heraus? Die Innenansicht zeigt den Preis der Bauweise: Als Python-Liste rücken beim pop(0) alle Zellen einzeln nach, der Zähler läuft bis n(n−1)/2; die Liste mit Index behält alles; die verkettete Liste hängt nur first, last und next um. Zehn Beispiele der Folien mit echtem Python-Ablauf, darunter Rückgängig, Klammerprüfung, vertauschte Zeilen mit Selbstschleife und Duck-Typing.
LIFO und FIFO
Ein Stapel (Stack) gibt das zuletzt hineingelegte Element zuerst wieder heraus: last in, first out. Eine Schlange (Queue) gibt das älteste Element zuerst heraus: first in, first out. Beide haben dieselbe Schnittstelle aus push und pop, verhalten sich aber verschieden. Wie teuer pop ist, hängt von der Bauweise ab. Eine Python-Liste entfernt am Ende in konstanter Zeit, bei pop(0) müssen dagegen alle übrigen Elemente nachrücken. Eine verkettete Liste mit Zeigern auf Anfang und Ende kommt an beiden Stellen mit wenigen Zeigeränderungen aus.
Was die App zeigt
Oben die Folge der Operationen, links der Stapel, rechts die Schlange, darunter jeweils, was pop geliefert hat. Vier Ansichten zeigen das Innere der Schlange: von außen, als Python-Liste mit pop(0), bei der ein Zähler die Verschiebungen bis n(n−1)/2 mitzählt, als Liste mit wanderndem Index, die alles behält, und als verkettete Liste mit first, last und next, die nur Pfeile umhängt. Neun weitere Beispiele zeigen Code-Tafel, Konsole und Speicherbild.
Selbst ausprobieren
Gib eine eigene Folge aus push und pop ein oder wähle eines der zehn Beispiele, darunter Rückgängig, Klammerprüfung, vertauschte Zeilen mit Selbstschleife und Duck-Typing. Vor jedem pop fragt die App auf Wunsch, was herauskommt. Vergleiche die Innenansichten für längere Folgen und beobachte, wie der Verschiebe-Zähler der Liste wächst, während die verkettete Liste bei jedem Schritt nur wenige Pfeile umhängt.
Häufige Fragen
- Was ist der Unterschied zwischen Stack und Queue?
- Ein Stack (Stapel) arbeitet nach LIFO: Das zuletzt eingefügte Element kommt zuerst heraus, wie bei einem Tellerstapel. Eine Queue (Warteschlange) arbeitet nach FIFO: Das zuerst eingefügte Element kommt zuerst heraus, wie an einer Kasse.
- Warum ist list.pop(0) in Python langsam?
- Eine Python-Liste speichert ihre Elemente lückenlos hintereinander. Entfernt man das erste, müssen alle übrigen eine Position nach vorne rücken; das kostet O(n). Für Warteschlangen eignet sich collections.deque, das an beiden Enden in O(1) einfügt und entfernt.
- Wofür braucht man einen Stapel?
- Überall, wo das Jüngste zuerst erledigt wird: Rückgängig-Funktionen, das Prüfen passender Klammern, der Aufrufstapel von Funktionen oder die Tiefensuche in Graphen.
- Was zeigt die App „Stapel und Schlange“?
- Stapel und Schlange nebeneinander mit derselben Folge von push und pop, dazu vier Innenansichten der Schlange mit Zählern für Verschiebungen und umgehängte Pfeile sowie zehn Python-Beispiele mit Speicherbild.
Fach: Informatik
Mehr aus Informatik
- Ackermann-Funktion
- Aufzug-Simulator
- Binär-Werkstatt
- Binäre vs. lineare Suche
- Collatz-Problem (3n+1)
- CPU-Innenleben
- Das Innere austauschen
- Ein Frame in 16 Millisekunden — wie eine Game-Engine ein Bild rechnet (3D)
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps