CKTIS / C
Fronta FIFO s kruhovým bufferem
Implementujte frontu FIFO s pevnou kapacitou v poli pomocí dvou indexů a počítadla, abyste mohli znovu využít uvolněná místa bez přesouvání prvků.
Verze: ISO C23; implementation support may vary
Syntaxe
#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 se nejdříve odebere prvek, který byl vložen nejdříve z těch, jež jsou ještě ve frontě. Kruhový buffer tuto posloupnost zachovává v poli s pevnou kapacitou: za posledním místem se index vrátí na nulu a prvky se nepřesouvají. Jde o způsob implementace, nikoli o typ ze standardní knihovny C. Příklad nepoužívá žádné novinky zavedené až v C23; podpora C23 závisí na implementaci.
V této konvenci označuje head další prvek ke čtení, pokud fronta není prázdná, tail další místo k zápisu, pokud není plná, a size počet prvků. Pro CAPACITY > 0 leží oba indexy v [0, CAPACITY) a size v [0, CAPACITY]. Matematicky se tail rovná (head + size) mod CAPACITY. Všechna tři pole struktury začínají na nule. head == tail platí v prázdné i plné frontě; tyto stavy rozlišuje size. Využít lze všechna místa.
enqueue při size == CAPACITY odmítne zápis a nic nepřepíše. Jinak zapíše na index tail, posune jej a zvýší size. dequeue při size == 0 odmítne čtení; jinak zkopíruje hodnotu z indexu head do *out, posune head a sníží size. Obě funkce vracejí 1 při úspěchu a 0 při odmítnutí; odmítnutí nemění frontu ani případnou výstupní proměnnou. Odebrání obsah místa nemaže. Výraz (i + 1) % CAPACITY využívá zbytek po celočíselném dělení a vrací platný index z posledního místa na nulu. Kapacita nemusí být mocninou dvou; dělitel nesmí být nula.
Každá operace trvá O(1) a pole zabírá O(CAPACITY) paměti. Předejte ukazatel na inicializovanou frontu, jejíž doba života neskončila; out musí ukazovat na samostatný zapisovatelný objekt typu int. Implementace přístup nesynchronizuje: pokud k frontě přistupuje více vláken a alespoň jedno ji mění, je nutná vnější synchronizace.
Pří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ýsledek
full: rejected 99 dequeued: 10 dequeued: 20 dequeued: 30 dequeued: 40 empty: nothing to dequeue
Po vložení `10`, `20` a `30` fronta odmítne `99`. Odebrání `10` uvolní místo `0` pro `40`. Navzdory své pozici v poli se `40` odebere až po `20` a `30`. Při posledním pokusu o odebrání je fronta prázdná.
Související lekce
- C · Lekce 86 · Pokročilá · Verze: 3