L3_3 Dynamische Datenstrukturen: Warteschlange (Queue)

Die Warteschlange ist eine dynamische Datenstruktur mit beliebiger Größe. Eine Warteschlange ar-beitet nach dem FIFO-Prinzip (=First In First Out) arbeitet, d. h. die Daten die zuerst hineingelegt (first in) wurden, werden als erstes herausgenommen (first out). Die Datenstruktur Warteschlange kann folglich gut mit den Warteschlangen an einer Kasse im Supermarkt verglichen werden.

Daten können mit Hilfe der Operation ENQUEUE() der Warteschlange hinzugefügt und mit der Opera-tion DEQUEUE() wieder entfernt werden. Dabei wird ein hinzugefügtes Element immer hinten an die Warteschlange angefügt. Die Entnahme eines Elements erfolgt dagegen immer von vorne. Das be-deutet, dass immer das Element aus der Warteschlange entnommen wird, das als ersten hinzugefügt wurde.

Beispiel:

Anwendungsbereiche in der Informatik:

• Druckerauftrag:
  Das Programm (z. B. Word) schreibt den Druckauftrag in eine dafür vorgesehen Warteschlange. Der Drucker arbeitet diese Warteschlange mit Druckaufträgen entsprechend der Reihenfolge ab.
• Puffer:
  Eine Datei wird von der Festplatte in den Puffer geschrieben. Das Programm, welches die Datei verarbeiten möchte, liest diese Datei jetzt aus dem Puffer. Daraus ergibt sich der Vorteil einer zeit-lichen Entkoppelung.
• Pipe bei Interprozesskommunikation:
  Eine Pipe ist eine Verbindung zwischen zwei Programmen. Programm 1 leitet die Ausgabe in die Pipe weiter und Programm 2 entnimmt diese Ausgabe als eine Eingabe aus der Pipe.