Datenstrukturen: Queue / Warteschlange

Die Warteschlange

Eine Queue (deutsch: Warteschlange) ist ebenfalls eine Datenstruktur, die einige Gemeinsamkeiten mit einer einfach verketteten Liste hat.
Sie stellt die Umkehrung eines Stacks dar und folgt nach dem FIFO-Prinzip (First-In-First-Out). Das bedeutet, das Objekt was zuerst in die Datenstruktur eingefügt wurde, ist zugleich das erste Objekt was entnommen wird.

Genauso wie bei einem Stack gibt es keine Möglichkeit Objekte zwischen weiteren Objekten einzufügen. Objekte können sich also nicht vordrängeln.
Soll ein Objekt eingefügt werden, so wird es immer an das Listenende eingefügt (enqueue). Es sei denn, die Liste ist leer. Möchte man ein Objekt aus einer Queue entnehmen, so wird immer das erste Listenelement entnommen (dequeue).
Oftmals wird auch hier eine Funktionalität für das Kopieren und das Durchlaufen einer Queue angeboten, um so nach bestimmten Objekten zu suchen.

Abbildung: Eine Queue

Anwendungsbeispiel

Ein Anwendungsbeispiel für eine Queue ist die Verwaltung von mehreren Threads (Multithreading). Jeder erzeugte Thread wird in eine Queue eingefügt. Nun müssen die Threads ausgeführt werden. Das FIFO-Prinzip hilft hier weiter, denn es sollen idealerweise alle Threads in der Reihenfolge ausgeführt werden, wie sich auch eingefügt worden sind. Dafür greifen mehrere Prozesse auf dieselbe Datenstruktur zu.

Abbildung: Ringpuffer

Eine weitere Implementierung sind die Ringpuffer. Ein Ringpuffer hat im Gegensatz zu einer Queue eine feste Größe, also wie ein Array. Es gibt einen Pointer, der auf den ersten Index zeigt, sowie einen Pointer der auf den letzten Index zeigt. Hier kann allerdings ein Pufferüberlauf entstehen, wenn bspw. die einzufügenden Objekte größer als der Puffer sind.

Quelle
https://courses.cs.washington.edu/courses/cse373/06sp/handouts/lecture04.pdf, pp. 13 ff.
www.studytonight.com/data-structures/images/introduction-to-queue.png
www.megunolink.com/wp-content/uploads/2016/08/CircularBuffer.png