Stack und Queue
Wie funktionieren Stacks und Queues?
Der Stack: Der Stapelspeicher (LIFO)
Ein Stack (deutsch: Stapel) ist eine Datenstruktur, die nach dem LIFO-Prinzip (Last-In, First-Out) arbeitet. Das bedeutet: Das Element, das als letztes hinzugefügt wurde, wird als erstes wieder entfernt. Ein Alltagsbeispiel ist ein Stapel Teller in der Mensa. Wenn gespült wird, werden saubere Teller oben auf den Stapel gelegt (push). Wenn du einen Teller benötigst, nimmst du den obersten herunter (pop). Du würdest niemals versuchen, den untersten Teller herauszuziehen, da sonst der ganze Stapel umkippen könnte.
In der Softwareentwicklung sind die drei Hauptoperationen eines Stacks:
- push(element): Legt ein neues Element oben auf den Stapel.
- pop(): Nimmt das oberste Element vom Stapel und gibt es zurück.
- peek(): Liest das oberste Element, ohne es zu entfernen (wie ein prüfender Blick auf den obersten Teller).
Ein klassisches Anwendungsbeispiel ist die "Rückgängig"-Funktion (Undo) in Textverarbeitungsprogrammen. Jeder getippte Buchstabe oder Befehl wird auf einen Stack gelegt. Wird STRG+Z gedrückt, nimmt das Programm die letzte Aktion (die oberste auf dem Stack) herunter und macht sie rückgängig.
Die Queue: Die Warteschlange (FIFO)
Eine Queue (deutsch: Warteschlange) arbeitet nach dem FIFO-Prinzip (First-In, First-Out). Hier gilt die faire Regel: Wer zuerst kommt, wird zuerst bedient. Stell dir eine Schlange an der Supermarktkasse vor. Die Person, die sich zuerst angestellt hat, wird als erste abkassiert und verlässt die Schlange (dequeue). Neu ankommende Personen stellen sich immer hinten an (enqueue).
Die Hauptoperationen einer Queue sind:
- enqueue(element): Fügt ein Element am Ende (Tail) der Schlange hinzu.
- dequeue(): Entfernt das vorderste Element (Head) und liefert es zurück.
- peek(): Zeigt das vorderste Element an, ohne es zu entfernen.
Ein technisches Beispiel ist der Drucker-Spooler. Wenn mehrere Mitarbeitende gleichzeitig Druckaufträge senden, werden diese in einer Queue gespeichert. Das Dokument, das zuerst beim Drucker ankam, wird auch zuerst gedruckt, unabhängig davon, wie groß oder klein es ist.
Wann nutze ich welche Struktur?
Die Wahl zwischen Stack und Queue hängt davon ab, in welcher Reihenfolge Daten verarbeitet werden müssen:
- Stack (LIFO): Wird genutzt, wenn der Weg "zurückverfolgt" werden muss oder das aktuellste Ereignis die höchste Priorität hat.
- Beispiel Call Stack: Wenn in einem Programm Funktion A die Funktion B aufruft, und B ruft C auf, muss erst C fertig werden, damit B weitermachen kann. Der Computer "stapelt" diese Aufrufe übereinander.
- Queue (FIFO): Wird genutzt, wenn Aufgaben fair nacheinander abgearbeitet werden sollen oder Daten gepuffert werden müssen.
- Beispiel Webserver: Anfragen an einen Webserver werden oft in einer Queue gesammelt und nacheinander abgearbeitet, um Überlastungen zu vermeiden und Fairness zu garantieren.
Wie werden Stacks und Queues technisch umgesetzt?
Effiziente Stack-Implementierung mit Arrays
Da du bereits Arrays als Speicherstruktur kennst, können wir diese nutzen, um einen Stack zu bauen. Wir benötigen lediglich ein Array fester Größe und eine Variable, den sogenannten Stack-Pointer (oft top genannt). Dieser zeigt immer auf das oberste Element.
Stell dir das Array als ein Regal mit nummerierten Fächern vor:
- Initialisierung: Der Stack-Pointer steht auf
-1. Das bedeutet: "Der Stapel ist leer". - Push (Drauflegen):
- Zuerst erhöhen wir den Stack-Pointer um 1.
- Dann schreiben wir das neue Datum in das Fach, auf das der Pointer jetzt zeigt.
- Achtung: Wenn der Pointer das Ende des Arrays erreicht, ist der Stack voll (Stack Overflow).
- Pop (Herunternehmen):
- Wir lesen das Datum aus dem Fach, auf das der Pointer gerade zeigt.
- Dann verringern wir den Pointer um 1.
- Achtung: Wenn der Pointer auf -1 steht, ist der Stack leer, und wir können nichts entnehmen (Stack Underflow).
Pseudocode:
Array daten[100]
Integer top = -1
Funktion push(wert):
IF top == 99 THEN Fehler "Stack Overflow"
top = top + 1
daten[top] = wert
Funktion pop():
IF top == -1 THEN Fehler "Stack Underflow"
wert = daten[top]
top = top - 1
return wertRingpuffer (Circular Buffer) für Queues
Bei einer Queue ist die Umsetzung mit einem einfachen Array schwieriger. Wenn wir vorne Elemente entfernen (dequeue), entstehen leere Plätze am Anfang. Würden wir alle restlichen Elemente nach vorne schieben ("aufrücken"), wäre das sehr rechenintensiv. Lassen wir die Lücken aber bestehen und füllen nur hinten auf (enqueue), "wandert" die Schlange irgendwann aus dem Speicherbereich des Arrays hinaus.
Die Lösung ist der Ringpuffer. Wir nutzen zwei Zeiger:
- Head (Lese-Zeiger): Zeigt auf das älteste Element (vorne), das als nächstes entnommen wird.
- Tail (Schreib-Zeiger): Zeigt auf den nächsten freien Platz (hinten).
Der Trick ist das "Im-Kreis-Denken": Wenn der Tail-Zeiger am Ende des Arrays angekommen ist, springt er wieder an den Anfang (Index 0), sofern dort Platz frei geworden ist. Mathematisch lösen wir das elegant mit dem Modulo-Operator (%).
Pseudocode:
Array daten[5]
Integer head = 0
Integer tail = 0
Integer anzahl = 0
Funktion enqueue(wert):
IF anzahl == 5 THEN Fehler "Queue voll"
daten[tail] = wert
// Tail rückt weiter, springt bei 5 aber auf 0 zurück (Modulo)
tail = (tail + 1) % 5
anzahl = anzahl + 1
Funktion dequeue():
IF anzahl == 0 THEN Fehler "Queue leer"
wert = daten[head]
// Head rückt weiter, springt bei 5 aber auf 0 zurück (Modulo)
head = (head + 1) % 5
anzahl = anzahl - 1
return wertLernziele
- das Konzept eines Stacks (Stapelspeicher) erklären, indem das LIFO-Prinzip (Last-In, First-Out) und die grundlegenden Operationen (push, pop, peek) anhand von Alltagsbeispielen (z.B. Tellerstapel) und Codebeispielen erläutert werden.
- das Konzept einer Queue (Warteschlange) erklären, indem das FIFO-Prinzip (First-In, First-Out) und die grundlegenden Operationen (enqueue, dequeue, peek) anhand von Alltagsbeispielen (z.B. Warteschlange an der Kasse) und Codebeispielen erläutert werden.
- die Unterschiede zwischen Stack und Queue vergleichen, indem ihre Zugriffsprinzipien (LIFO vs. FIFO) und typische Anwendungsfälle (z.B. Funktionsaufrufstapel vs. Druckauftragswarteschlange) gegenübergestellt werden.
- die Funktionsweise von Stacks und Queues auf Basis von Arrays oder Listen auszuführen, indem der strukturelle Aufbau von grundlegenden Operationen (z. B. via Pseudocode) skizziert und die Vor- und Nachteile der gewählten Datenstruktur gegenübergestellt werden.
Vertiefe dein Wissen!
Du hast die Grundlagen verstanden? Perfekt! In unserer App findest du interaktive Übungen, praktische Projekte und erweiterte Inhalte zu Stack und Queue.
.DOEG5Pbs_Za9Mg1.svg)
.0zaumQ2g_Za9Mg1.svg)
Ab 5€/Monat • Kostenloser Test verfügbar