Queue (englisch für „Reihe“ oder „Schlange“) bezeichnet in der Informatik und EDV eine häufig eingesetzte, lineare Datenstruktur zur Zwischenspeicherung von Objekten in einer bestimmten Reihenfolge zur Weiterverarbeitung.
Das FIFO-Prinzip
Das grundlegende Merkmal einer Queue ist das FIFO-Prinzip (First In – First Out; „Wer zuerst kommt, mahlt zuerst“). Elemente werden immer am Ende der Schlange eingefügt und am Anfang der Schlange entnommen. Das Element, das am längsten in der Queue wartet, wird somit als nächstes verarbeitet.
Die beiden Hauptoperationen einer Queue sind:
- Enqueue: Ein neues Element wird hinten an die Warteschlange angehängt.
- Dequeue: Das vorderste Element wird aus der Warteschlange entnommen und verarbeitet.
Typische Anwendungsbeispiele
Queues kommen überall dort zum Einsatz, wo Ressourcen geteilt werden oder Prozesse asynchron (zeitlich versetzt) ablaufen:
- Drucker-Warteschlange (Print Queue): Wenn mehrere Benutzer gleichzeitig Dokumente an einen Drucker senden, werden die Druckaufträge in einer Queue gesammelt und nacheinander abgearbeitet.
- Datenpuffer (Buffering): Beim Streaming von Videos oder Musik werden Daten vorab in einer Queue gespeichert, um Netzwerkschwankungen auszugleichen und eine flüssige Wiedergabe zu garantieren.
- Prozess-Scheduling: Betriebssysteme nutzen Warteschlangen, um zu regeln, welche Programme oder Aufgaben (Tasks) wann Rechenzeit auf dem Prozessor (CPU) erhalten.
- Nachrichtensysteme (Message Queues): In großen Software-Architekturen tauschen unabhängige Programme Nachrichten über Queues aus, um sich gegenseitig nicht zu blockieren.
Abgrenzung
Das Gegenstück zur Queue ist der Stack (Stapel- oder Kellertextspeicher). Dieser arbeitet nach dem LIFO-Prinzip (Last In – First Out), bei dem das zuletzt hinzugefügte Element als erstes wieder entnommen wird (vergleichbar mit einem Stapel Teller).
