Queue: FIFO und Kapazität

Eine Queue speichert Elemente nach FIFO: das zuerst eingefügte Element verlässt die Struktur zuerst. enqueue (oder offer) fügt hinten an, dequeue (oder poll) entfernt vorne.

Beispielspur: enqueue(A), enqueue(B), dequeue liefert A, dequeue liefert B.

Bei begrenzter Kapazität (Ringpuffer) kann enqueue bei vollem Puffer scheitern. Leeres dequeue ist der symmetrische Fehlerfall.

Warteschlangen modellieren Druckaufträge, Netzpakete und Breitensuche in Graphen.

Queue aus zwei Stacks: Implement Queue using Stacks [1].

$$i \equiv (h+k) \pmod{C}$$

Wo gebraucht

Job-Queues, Message Broker (Kafka/RabbitMQ-Idee), Request-Puffer vor Workern, Druckspools, BFS. Begrenzte Kapazität modelliert Backpressure: volle Queue bedeutet Last abweisen oder blockieren, nicht still Speicher füllen.

Vertiefung

Ein FIFO-Speicher erhält die Ankunftsreihenfolge. Ein Ringpuffer nutzt ein festes Array zyklisch, sodass Entnahmen am Anfang keine restlichen Elemente verschieben. Zwei Indizes markieren typischerweise Schreib- und Leseposition.

Sind beide Indizes gleich, kann der Puffer leer oder voll sein. Diese Mehrdeutigkeit wird durch einen separaten Zähler, ein zusätzliches Zustandsbit oder einen absichtlich ungenutzten Platz aufgelöst. Die gewählte Variante bestimmt die tatsächlich nutzbare Kapazität.

Bei begrenztem Speicher muss die Überlaufstrategie Teil des Vertrags sein. Blockieren, Verwerfen des neuen Elements und Überschreiben des ältesten Elements haben in Nachrichtensystemen sehr unterschiedliche Folgen.

Schwierigkeitsstufen

1. Lese- und Schreibindex eines Ringpuffers verfolgen.
2. Leer- und Vollzustand ohne Mehrdeutigkeit codieren.
3. Eine Überlaufstrategie für ein konkretes System begründen.

Fallstricke

Modulo-Arithmetik beseitigt das Verschieben, aber nicht die Zustandsmehrdeutigkeit. Ausserdem ist eine Arraylänge von k bei der Freiplatzmethode nur für k - 1 Elemente nutzbar.