CKTIS / C
Front FIFO s kruhovým bufferom
Implementujte front FIFO s pevnou kapacitou v poli pomocou dvoch indexov a počítadla, aby ste znova využili uvoľnené miesta bez presúvania prvkov.
Verzia: 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 znamená, že sa najprv odoberie prvok, ktorý bol vložený ako prvý spomedzi tých, ktoré ešte zostali vo fronte. Kruhový buffer zachováva toto poradie v poli s pevnou kapacitou: za posledným miestom sa index vráti na nulu bez presunu prvkov. Ide o spôsob implementácie, nie o typ zo štandardnej knižnice jazyka C. Príklad nepoužíva prvky zavedené až v C23; podpora C23 závisí od implementácie.
V tejto konvencii head označuje nasledujúci prvok na čítanie, ak front nie je prázdny, tail nasledujúce miesto na zápis, ak nie je plný, a size počet prvkov. Pri CAPACITY > 0 patria oba indexy do [0, CAPACITY) a size do [0, CAPACITY]. Matematicky sa tail rovná (head + size) mod CAPACITY. Všetky tri členy štruktúry začínajú na nule. head == tail platí pre prázdny aj plný front; size ich rozlišuje. Využiť možno všetky miesta.
enqueue pri size == CAPACITY odmietne zápis a nič neprepíše. Inak zapíše na index tail, posunie ho a zvýši size. dequeue pri size == 0 odmietne čítanie; inak skopíruje hodnotu z indexu head do *out, posunie head a zníži size. Obe funkcie vracajú 1 pri úspechu a 0 pri odmietnutí; odmietnutie nemení front ani prípadnú výstupnú premennú. Odobratie obsah miesta nevymaže. Výraz (i + 1) % CAPACITY používa zvyšok po celočíselnom delení, aby sa platný index z posledného miesta vrátil na nulu. Kapacita nemusí byť mocninou dvoch; deliteľ nesmie byť nula.
Každá operácia trvá O(1) a pole zaberá O(CAPACITY) pamäte. Odovzdajte ukazovateľ na inicializovaný front, ktorého životnosť ešte neskončila; out musí ukazovať na samostatný zapisovateľný objekt typu int. Implementácia prístup nesynchronizuje: ak k frontu pristupuje viac vlákien a aspoň jedno ho mení, treba vonkajšiu synchronizáciu.
Príklady
#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;
}
Výsledok
full: rejected 99 dequeued: 10 dequeued: 20 dequeued: 30 dequeued: 40 empty: nothing to dequeue
Po vložení `10`, `20` a `30` front odmietne `99`. Odobratie `10` uvoľní miesto `0` pre `40`. Napriek svojej pozícii v poli sa `40` odoberie až po `20` a `30`. Pri poslednom pokuse o odobratie je front prázdny.
Súvisiace lekcie
- C · Lekcia 86 · Pokročilá · Verzia: 3