WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C

FIFO-Warteschlange mit Ringpuffer

Implementiere eine FIFO-Warteschlange fester Kapazität in einem Array mit zwei Indizes und einem Zähler, um freie Plätze ohne Verschieben wiederzuverwenden.

Version: ISO C23; implementation support may vary

Syntax

#include <stddef.h>

enum { CAPACITY = 3 }; /* Positive, fixed capacity for this example. */
typedef struct {
    int data[CAPACITY];
    size_t head, tail, size;
} Queue;

/* Initialize with Queue q = {0}; then pass &q. */
static int enqueue(Queue *q, int value);
static int dequeue(Queue *q, int *out);
/* Both return 1 on success or 0 on full/empty, respectively. */

FIFO bedeutet, dass das zuerst eingefügte Element, das noch in der Warteschlange liegt, zuerst entnommen wird. Ein Ringpuffer setzt diese Reihenfolge in einem Array fester Kapazität um: Nach dem letzten Platz springt ein Index auf null, ohne dass Elemente verschoben werden. Das ist ein Implementierungsmuster, kein Typ der C-Standardbibliothek. Das Beispiel benötigt keine erst mit C23 eingeführten Merkmale; die C23-Unterstützung hängt von der Implementierung ab.

Hier bezeichnet head bei nicht leerer Warteschlange das nächste zu lesende Element, tail bei nicht voller Warteschlange den nächsten Schreibplatz und size die Anzahl der Elemente. Für CAPACITY > 0 liegen beide Indizes in [0, CAPACITY) und size in [0, CAPACITY]. Mathematisch gilt tail = (head + size) mod CAPACITY. Alle drei Felder beginnen bei null. head == tail gilt sowohl im leeren als auch im vollen Zustand; size unterscheidet sie. Alle Plätze sind nutzbar.

enqueue lehnt bei size == CAPACITY das Schreiben ab, ohne etwas zu überschreiben. Sonst schreibt es an Position tail, rückt diesen Index vor und erhöht size. dequeue lehnt bei size == 0 das Lesen ab; sonst kopiert es den Wert an Position head nach *out, rückt head vor und verringert size. Beide liefern 1 bei Erfolg und 0 bei Ablehnung; dabei bleiben Warteschlange und etwaige Ausgabevariable unverändert. Die Entnahme löscht den Speicherplatz nicht. (i + 1) % CAPACITY nutzt den Divisionsrest, um einen gültigen Index vom letzten Platz auf null zurückzuführen. Die Kapazität muss keine Zweierpotenz sein; der Divisor darf nicht null sein.

Jede Operation braucht O(1) Zeit, das Array O(CAPACITY) Speicher. Übergib einen Zeiger auf eine initialisierte Warteschlange innerhalb ihrer Lebensdauer; out muss auf ein separates beschreibbares int-Objekt zeigen. Die Implementierung synchronisiert nicht: Greifen mehrere Threads zu und verändert mindestens einer die Warteschlange, ist externe Synchronisation nötig.

Beispiele

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

enum { CAPACITY = 3 };

typedef struct {
    int data[CAPACITY];
    size_t head, tail, size;
} Queue;

static int enqueue(Queue *q, int value)
{
    if (q->size == CAPACITY)
        return 0;
    q->data[q->tail] = value;
    q->tail = (q->tail + 1) % CAPACITY;
    ++q->size;
    return 1;
}

static int dequeue(Queue *q, int *out)
{
    if (q->size == 0)
        return 0;
    *out = q->data[q->head];
    q->head = (q->head + 1) % CAPACITY;
    --q->size;
    return 1;
}

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: rejected 99");

    if (!dequeue(&q, &value))
        return EXIT_FAILURE;
    printf("dequeued: %d\n", value);
    if (!enqueue(&q, 40))
        return EXIT_FAILURE;

    while (dequeue(&q, &value))
        printf("dequeued: %d\n", value);
    puts("empty: nothing to dequeue");
    return EXIT_SUCCESS;
}

Ergebnis

full: rejected 99
dequeued: 10
dequeued: 20
dequeued: 30
dequeued: 40
empty: nothing to dequeue

Nach dem Einfügen von `10`, `20` und `30` wird `99` abgelehnt. Die Entnahme von `10` gibt Platz `0` für `40` frei. Trotz seiner Position im Array wird `40` nach `20` und `30` entnommen. Beim letzten Entnahmeversuch ist die Warteschlange leer.

Zugehörige Lektionen

  • C · Lektion 86 · Fortgeschritten · Version: 3

Quellen