Zum Inhalt
Alle Apps

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

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps