Stack und Queue

Was unterscheidet Stacks von Queues und wie funktionieren sie?

Der Stack: Der Stapelspeicher (LIFO)

Stell dir einen Stapel Teller in der Kantine vor: Wenn saubere Teller aus der Küche kommen, werden sie oben auf den Stapel gelegt. Wenn du einen Teller brauchst, nimmst du den obersten herunter. Du würdest nie den untersten Teller mühsam herausziehen. Genau so funktioniert die Datenstruktur Stack (deutsch: Stapelspeicher).

Wie auch in der zugehörigen Grafik veranschaulicht, arbeitet ein Stack nach dem LIFO-Prinzip (Last-In, First-Out): Das Element, das als letztes hinzugefügt wurde, wird als erstes wieder entfernt. Die drei grundlegenden Operationen sind:

Push: Legt ein neues Element oben auf den Stapel.
Pop: Nimmt das oberste Element vom Stapel herunter und gibt es zurück.
Peek: Liest das oberste Element, ohne es zu entfernen.

Ein klassisches Anwendungsbeispiel in der Softwareentwicklung ist die "Rückgängig"-Funktion (Undo) in Textverarbeitungsprogrammen. Jede deiner Aktionen wird auf einen Stack gelegt. Drückst du STRG+Z, wird per Pop die letzte Aktion vom Stapel geholt und rückgängig gemacht.

Die Queue: Die Warteschlange (FIFO)

Stell dir nun die Schlange an einer Supermarktkasse vor: Wer sich zuerst anstellt, wird auch zuerst abkassiert. Wer neu hinzukommt, stellt sich hinten an. Dieses Prinzip nutzt die Datenstruktur Queue (deutsch: Warteschlange).

Sie arbeitet nach dem FIFO-Prinzip (First-In, First-Out). Die grundlegenden Operationen heißen hier anders und greifen auf unterschiedliche Enden der Struktur zu:

Enqueue: Fügt ein neues Element am Ende (Tail) der Schlange hinzu.
Dequeue: Entfernt das vorderste Element (Head) und gibt es zurück.
Peek: Zeigt das vorderste Element an, ohne es zu entfernen.

Ein typisches technisches Beispiel ist die Druckauftragswarteschlange (Print Spooler). Senden mehrere Personen gleichzeitig Dokumente an einen Netzwerkdrucker, werden diese in einer Queue gespeichert. Das Dokument, das zuerst ankam, wird zuerst gedruckt – fair und in der exakten Reihenfolge des Eintreffens.

Stack vs. Queue: Der direkte Vergleich

Die Wahl zwischen Stack und Queue hängt ausschließlich von der benötigten Verarbeitungsreihenfolge ab:

Nutze einen Stack (LIFO), wenn du Wege "rückverfolgen" musst oder das aktuellste Ereignis Vorrang hat. Ein technisches Beispiel ist der Funktionsaufrufstapel (Call Stack): Ruft Funktion A die Funktion B auf, wird A pausiert und auf den Stack gelegt. B muss erst beendet (Pop) werden, bevor A weiterlaufen kann.

Nutze eine Queue (FIFO), wenn Aufgaben fair und chronologisch abgearbeitet werden sollen. Neben dem Drucker ist die Verarbeitung von Webserver-Anfragen ein klassischer Fall: Greifen tausende User gleichzeitig auf eine Website zu, werden die Anfragen in einer Queue gepuffert und nacheinander bedient, um den Server nicht zu überlasten.

Stack und Queue — dec-software-engineering-data-structures-and-algorithms-fundamental-data-structures-stack-and-queue_page1.svg

Wie implementierst du Stacks und Queues im Code?

Stack-Implementierung: Array vs. Verkettete Liste

Da du Arrays und verkettete Listen bereits kennst, kannst du beide als Basis für einen Stack nutzen. Bei einem Array benötigst du lediglich eine Variable als Stack-Pointer (oft top genannt), die den Index des obersten Elements speichert.

Bewertung: Ein Array ist extrem schnell und speichereffizient, hat aber eine feste Größe. Ist das Array voll, droht ein Programmabsturz (Stack Overflow). Eine Implementierung mit einer verketteten Liste wächst dynamisch mit, benötigt aber durch die Zeiger (Pointers) etwas mehr Speicherplatz.

Hier ist die Logik für einen Array-basierten Stack in Pseudocode:

Array daten[100]
Integer top = -1  // -1 bedeutet: Stack ist leer

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 wert

Queue-Implementierung: Das Problem des Aufrückens

Bei einer Queue ist ein einfaches Array problematisch. Wenn du vorne Elemente entfernst (Dequeue), entstehen leere Plätze. Würdest du alle restlichen Elemente nach vorne schieben, würde das enorm viel Rechenleistung kosten. Lässt du die Lücken bestehen und füllst nur hinten auf (Enqueue), "wandert" die Queue irgendwann über das Ende des Arrays hinaus, obwohl vorne eigentlich Platz wäre.

Bewertung: Eine verkettete Liste löst dieses Problem elegant, da du beim Hinzufügen oder Entfernen nur den Head- und Tail-Zeiger umbiegen musst, ohne Daten zu verschieben. Willst du dennoch ein Array nutzen (z. B. für maximale Performance in hardwarenaher Programmierung), verwendest du einen Ringpuffer.

Der Ringpuffer (Circular Buffer)

Beim Ringpuffer (Circular Buffer) nutzt du ein Array mit zwei Zeigern: Head (Lese-Zeiger) und Tail (Schreib-Zeiger). Der Trick: Wenn der Tail-Zeiger das Ende des Arrays erreicht, springt er wieder auf den Index 0 zurück, sofern dort durch vorherige Dequeue-Aufrufe Platz frei geworden ist. Dies erreichst du mathematisch mit dem Modulo-Operator (%).

Array daten[5]
Integer head = 0
Integer tail = 0
Integer anzahl = 0  // Verfolgt die aktuelle Auslastung

Funktion enqueue(wert):
  IF anzahl == 5 THEN Fehler "Queue voll"
  daten[tail] = wert
  tail = (tail + 1) % 5  // Springt nach Index 4 wieder auf 0
  anzahl = anzahl + 1

Funktion dequeue():
  IF anzahl == 0 THEN Fehler "Queue leer"
  wert = daten[head]
  head = (head + 1) % 5  // Springt nach Index 4 wieder auf 0
  anzahl = anzahl - 1
  return wert

Teste dein Wissen

Du programmierst die "Rückgängig"-Funktion für einen Texteditor. Welche Datenstruktur und welches Prinzip nutzt du, damit STRG+Z die letzte Aktion zuerst widerruft?