Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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

Zdroje