Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

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

Zdroje