CKTIS / C
Čakalna vrsta FIFO s krožnim medpomnilnikom
Čakalno vrsto FIFO s stalno kapaciteto izvedite v tabeli z dvema indeksoma in števcem, tako da sproščena mesta znova uporabite brez premikanja elementov.
Različica: ISO C23; implementation support may vary
Sintaksa
#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 pomeni, da najprej odstranimo najprej vstavljeni element med tistimi, ki so še v vrsti. Krožni medpomnilnik ohrani ta vrstni red v tabeli s stalno kapaciteto: po zadnjem mestu se indeks vrne na nič, elementi pa se ne premikajo. To je način izvedbe, ne tip iz standardne knjižnice jezika C. Primer ne uporablja novosti, uvedenih šele v C23; podpora za C23 je odvisna od implementacije.
Po tem dogovoru head označuje naslednji element za branje, kadar vrsta ni prazna, tail naslednje mesto za pisanje, kadar ni polna, size pa število elementov. Pri CAPACITY > 0 sta oba indeksa v [0, CAPACITY), size pa v [0, CAPACITY]. Matematično je tail enak (head + size) mod CAPACITY. Vsa tri polja strukture imajo na začetku vrednost nič. head == tail velja tako za prazno kot za polno vrsto; stanji loči size. Uporabna so vsa mesta.
enqueue pri size == CAPACITY zavrne pisanje in ničesar ne prepiše. Sicer zapiše na indeks tail, ga premakne naprej in poveča size. dequeue pri size == 0 zavrne branje; sicer kopira vrednost z indeksa head v *out, premakne head naprej in zmanjša size. Obe funkciji ob uspehu vrneta 1, ob zavrnitvi pa 0; ob zavrnitvi se ne spremenita ne vrsta ne morebitna izhodna spremenljivka. Odstranitev ne izbriše vsebine mesta. Izraz (i + 1) % CAPACITY uporabi ostanek celoštevilskega deljenja, da veljaven indeks z zadnjega mesta vrne na nič. Kapaciteta ni nujno potenca števila dve; delitelj ne sme biti nič.
Vsaka operacija traja O(1), tabela pa zavzame O(CAPACITY) prostora. Podajte kazalec na inicializirano vrsto, katere življenjska doba se še ni iztekla; out mora kazati na ločen zapisljiv objekt tipa int. Izvedba dostopov ne sinhronizira: če do vrste dostopa več niti in jo vsaj ena spreminja, je potrebna zunanja sinhronizacija.
Primeri
#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;
}
Rezultat
full: rejected 99 dequeued: 10 dequeued: 20 dequeued: 30 dequeued: 40 empty: nothing to dequeue
Po vstavitvi `10`, `20` in `30` vrsta zavrne `99`. Odstranitev `10` sprosti mesto `0` za `40`. Kljub svojemu mestu v tabeli pride `40` iz vrste za `20` in `30`. Ob zadnjem poskusu odstranitve je vrsta prazna.
Povezane lekcije
- C · Lekcija 86 · Napredna · Različica: 3