CKTIS / C
FIFO-wachtrij met een ringbuffer
Implementeer een FIFO-wachtrij met vaste capaciteit in een array met twee indices en een teller, zodat je vrijgekomen plaatsen hergebruikt zonder elementen te verschuiven.
Versie: 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 betekent dat het eerst ingevoegde element dat nog in de wachtrij staat, er als eerste uit gaat. Een ringbuffer houdt deze volgorde bij in een array met vaste capaciteit: na de laatste plaats gaat een index terug naar nul zonder elementen te verschuiven. Dit is een implementatiepatroon, geen type uit de standaardbibliotheek van C. Het voorbeeld gebruikt niets wat pas in C23 is ingevoerd; ondersteuning voor C23 hangt af van de implementatie.
In deze conventie wijst head het volgende te lezen element aan als de wachtrij niet leeg is, tail de volgende schrijfplaats als de rij niet vol is, en telt size de elementen. Bij CAPACITY > 0 liggen beide indices in [0, CAPACITY) en ligt size in [0, CAPACITY]. Wiskundig is tail gelijk aan (head + size) mod CAPACITY. Alle drie velden beginnen op nul. head == tail geldt bij zowel een lege als een volle rij; size maakt het onderscheid. Alle plaatsen zijn bruikbaar.
enqueue weigert te schrijven bij size == CAPACITY, zonder iets te overschrijven. Anders schrijft de functie op index tail, schuift die index op en verhoogt size. dequeue weigert te lezen bij size == 0; anders kopieert de functie de waarde op index head naar *out, schuift head op en verlaagt size. Beide geven 1 terug bij succes en 0 bij weigering; bij weigering veranderen de wachtrij en een eventuele uitvoervariabele niet. Verwijderen wist de plaats niet. (i + 1) % CAPACITY gebruikt de rest van de gehele deling om een geldige index van de laatste plaats naar nul te laten terugkeren. De capaciteit hoeft geen macht van twee te zijn; de deler mag niet nul zijn.
Elke bewerking kost O(1) tijd en de array gebruikt O(CAPACITY) ruimte. Geef een pointer door naar een geïnitialiseerde wachtrij waarvan de levensduur nog niet is verstreken; out moet naar een afzonderlijk, beschrijfbaar int-object wijzen. De implementatie synchroniseert niet: als meerdere threads de wachtrij gebruiken en minstens één die wijzigt, is externe synchronisatie nodig.
Voorbeelden
#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;
}
Resultaat
full: rejected 99 dequeued: 10 dequeued: 20 dequeued: 30 dequeued: 40 empty: nothing to dequeue
Na het invoegen van `10`, `20` en `30` weigert de wachtrij `99`. Door `10` te verwijderen komt plaats `0` vrij voor `40`. Ondanks zijn positie in de array komt `40` pas na `20` en `30` aan de beurt. Bij de laatste verwijderpoging is de wachtrij leeg.
Gerelateerde lessen
- C · Les 86 · Gevorderd · Versie: 3