CKTIS / C
FIFO-Warteschlange in C: Ringpuffer
Implementiere eine FIFO-Warteschlange mit fester Kapazität und nutze `head`, `tail` und `size`, um Arrayplätze ohne Verschieben der Elemente wiederzuverwenden.
Version: ISO C23; implementation support may vary
Syntax
Queue q = {0};
bool enqueue(Queue *q, int value);
bool dequeue(Queue *q, int *out);
/* Advance a valid index; CAPACITY must be positive. */
index = (index + 1) % CAPACITY;Eine FIFO-Warteschlange (first in, first out) entnimmt das älteste noch vorhandene Element. FIFO legt die Reihenfolge fest; ein Ringpuffer ist eine mögliche Implementierung. Queue, enqueue und dequeue sind im Beispiel definiert und gehören nicht zur C-Standardbibliothek.
Queue q = {0}; initialisiert eine leere Warteschlange. head ist der Index des ältesten Elements, wenn die Warteschlange nicht leer ist. tail ist der Index für den nächsten Schreibzugriff, wenn sie nicht voll ist. Beide Indizes liegen zwischen 0 und CAPACITY - 1. size zählt die belegten Plätze, von 0 bis CAPACITY. Mathematisch gilt tail ≡ head + size (mod CAPACITY). Deshalb unterscheidet head == tail allein nicht zwischen leer und voll; dafür dient size.
Ist Platz frei, schreibt enqueue an Position tail, setzt tail weiter und erhöht size. Ist die Warteschlange nicht leer, kopiert dequeue den Wert an Position head nach *out, setzt head weiter und verringert size. Zum Weiterschalten dient (index + 1) % CAPACITY: % liefert den Divisionsrest, sodass auf den letzten Index wieder 0 folgt. CAPACITY muss positiv sein; ein Divisor von null bei % führt zu undefiniertem Verhalten.
Beide Funktionen liefern bei Erfolg true und bei Ablehnung wegen voller bzw. leerer Warteschlange false. Dabei bleiben die Warteschlange und bei dequeue auch *out unverändert. q muss auf eine initialisierte Warteschlange innerhalb ihrer Lebensdauer zeigen, out auf ein separates, schreibbares int-Objekt innerhalb seiner Lebensdauer. Jede Operation benötigt O(1) Zeit, das Array O(CAPACITY) Speicher. Die Implementierung verwendet weder dynamische Speicherallokation noch Thread-Synchronisation. Das Beispiel setzt eine gehostete Umgebung voraus und benötigt keine C23-spezifischen Funktionen; die Unterstützung des ISO-C23-Modus hängt von der Implementierung ab.
Beispiele
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
enum { CAPACITY = 3 };
typedef struct {
int data[CAPACITY];
size_t head;
size_t tail;
size_t size;
} Queue;
static size_t next_index(size_t index)
{
return (index + 1) % CAPACITY;
}
static bool enqueue(Queue *q, int value)
{
if (q->size == CAPACITY) {
return false;
}
q->data[q->tail] = value;
q->tail = next_index(q->tail);
++q->size;
return true;
}
static bool dequeue(Queue *q, int *out)
{
if (q->size == 0) {
return false;
}
*out = q->data[q->head];
q->head = next_index(q->head);
--q->size;
return true;
}
int main(void)
{
Queue q = {0};
int value;
if (!enqueue(&q, 10) || !enqueue(&q, 20) || !enqueue(&q, 30)) {
return EXIT_FAILURE;
}
if (enqueue(&q, 99)) {
return EXIT_FAILURE;
}
puts("full");
if (!dequeue(&q, &value)) {
return EXIT_FAILURE;
}
printf("%d\n", value);
if (!enqueue(&q, 40)) {
return EXIT_FAILURE;
}
while (dequeue(&q, &value)) {
printf("%d\n", value);
}
puts("empty");
return EXIT_SUCCESS;
}
Ergebnis
full 10 20 30 40 empty
Nach drei Schreibvorgängen springt `tail` auf `0` zurück. Der Versuch, `99` einzufügen, gibt `full` aus, ohne `10` zu überschreiben. Nach der Entnahme von `10` belegt `40` erneut Platz `0`, wird aber erst nach `20` und `30` entnommen. Die fehlgeschlagene Entnahme aus der leeren Warteschlange beendet die Schleife; das Programm gibt `empty` aus.
Zugehörige Lektionen
- C · Lektion 86 · Fortgeschritten · Version: 3