KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C

FIFO-wachtrij in C: ringbuffer

Implementeer een FIFO-wachtrij met vaste capaciteit en gebruik `head`, `tail` en `size` om arrayposities te hergebruiken zonder elementen te verschuiven.

Versie: 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;

Een FIFO-wachtrij (first in, first out) haalt het oudste element weg dat nog in de wachtrij staat. FIFO bepaalt de volgorde; een ringbuffer is één manier om die te implementeren. Queue, enqueue en dequeue worden in het voorbeeld gedefinieerd en behoren niet tot de standaardbibliotheek van C.

Queue q = {0}; initialiseert een lege wachtrij. head is de index van het oudste element als de wachtrij niet leeg is, en tail is de index voor de volgende schrijfactie als de wachtrij niet vol is. Beide indices lopen van 0 tot CAPACITY - 1. size telt de bezette posities, van 0 tot CAPACITY. Wiskundig geldt tail ≡ head + size (mod CAPACITY). Daarom kun je aan head == tail alleen niet zien of de wachtrij leeg of vol is; aan size wel.

Als er ruimte is, schrijft enqueue op positie tail, schuift tail door en verhoogt size. Als de wachtrij niet leeg is, kopieert dequeue de waarde op positie head naar *out, schuift head door en verlaagt size. Elke stap gebruikt (index + 1) % CAPACITY: % geeft de rest van de deling, dus na de laatste index volgt weer 0. CAPACITY moet positief zijn; een deler van nul bij % veroorzaakt ongedefinieerd gedrag.

Beide functies geven true terug bij succes en false als de actie wordt geweigerd omdat de wachtrij respectievelijk vol of leeg is. Bij weigering blijft de wachtrij ongewijzigd, en bij dequeue ook *out. q moet naar een geïnitialiseerde wachtrij wijzen waarvan de levensduur nog niet voorbij is; out moet naar een afzonderlijk, schrijfbaar int-object wijzen dat nog bestaat. Elke operatie kost O(1) tijd en de array gebruikt O(CAPACITY) geheugen. Deze implementatie alloceert geen dynamisch geheugen en synchroniseert geen threads. Het voorbeeld gaat uit van een hosted omgeving en vereist geen C23-specifieke functies; ondersteuning voor de ISO C23-modus verschilt per implementatie.

Voorbeelden

#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;
}

Resultaat

full
10
20
30
40
empty

Na drie schrijfacties keert `tail` terug naar `0`. De poging om `99` toe te voegen drukt `full` af zonder `10` te overschrijven. Na het verwijderen van `10` hergebruikt `40` positie `0`, maar `40` komt pas na `20` en `30` uit de wachtrij. De mislukte verwijdering uit de lege wachtrij beëindigt de lus; het programma drukt `empty` af.

Gerelateerde lessen

  • C · Les 86 · Gevorderd · Versie: 3

Bronnen