mibeon
/ Datenstrukturen

Queue Kapazität

Speicherbedarf einer Queue (Ringpuffer) bei fester Kapazität: Speicher = Kapazitaet · Elementgroesse. FIFO-Datenstruktur mit konstantem Pro-Element-Aufwand.

Queue Kapazität
01 · Eingabe

Queue Kapazität berechnen

Speicherbedarf einer Queue (Ringpuffer) bei fester Kapazität: Speicher = Kapazitaet · Elementgroesse. FIFO-Datenstruktur mit konstantem Pro-Element-Aufwand.

Lösen für
Speicher = Kapazitaet · Elementgroesse
Byte

Worum geht es?

Eine Queue (First In First Out) wird in eingebetteten Systemen typischerweise als Ringpuffer fester Größe mit Head- und Tail-Index implementiert. Der Speicherbedarf ist Kapazität mal Elementgröße — Enqueue und Dequeue laufen in O(1) ohne dynamische Allokation.

Praktische Einsatzgebiete sind UART-Empfangspuffer, Druckwarteschlangen, Job-Queues in Schedulern, BFS-Implementierungen in Graphen-Algorithmen und Message-Queues in Embedded-Betriebssystemen.

Die Formel

Formel Queue-Speicher 
Speicher = Kapazität · Elementgröße

Umstellungen:
    Kapazität     = Speicher / Elementgröße
    Elementgröße  = Speicher / Kapazität

Die Variablen

SymbolBedeutungEinheitErklärung
KapazitätKapazität—Maximale Anzahl Elemente.
ElementgrößeElementgrößeByteGröße eines Elements.
SpeicherSpeicherbedarfByteGesamter belegter Speicher.

Minimal-Beispiel

UART-RX-Puffer für 128 Byte-große Frames:

Rechnung UART-Puffer 
Speicher = 128 · 1
         = 128 Byte

Praxis-Beispiele

Beispiel 1 — Message-Queue im RTOS

Eine FreeRTOS-Queue für 16 Messages à 32 Byte:

Rechnung RTOS-Queue 
Speicher = 16 · 32
         = 512 Byte

Beispiel 2 — BFS-Frontier

Eine BFS auf einem Graphen mit 10⁶ Knoten benötigt im Worst Case eine Queue für alle Knoten (8 Byte Pointer):

Rechnung BFS-Worst-Case 
Speicher = 10⁶ · 8
         = 8 MB

Beispiel 3 — Audio-Streaming

Ein Audio-Ringpuffer für 1 Sekunde Stereo-PCM (44,1 kHz, 16-Bit):

Rechnung Audio-Ringpuffer 
Kapazität    = 44 100 · 2 = 88 200 Samples
Elementgröße = 2 Byte
Speicher     = 176 400 Byte
             ≈ 172 KiB