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

CKTIS / C

Front FIFO v C: kruhový buffer

Implementuj front FIFO s pevnou kapacitou a pomocou `head`, `tail` a `size` opakovane využívaj miesta v poli bez presúvania prvkov.

Verzia: ISO C23; implementation support may vary

Syntax

Queue q = {0};
bool enqueue(Queue *q, int value);
bool dequeue(Queue *q, int *out);

/* Advance a valid index; CAPACITY must be positive. */
index = (index + 1) % CAPACITY;

Front FIFO (first in, first out, prvý dnu, prvý von) odoberá najstarší prvok, ktorý v ňom ešte je. FIFO určuje poradie; kruhový buffer je jeden zo spôsobov implementácie. Queue, enqueue a dequeue sú definované v príklade a nepatria do štandardnej knižnice jazyka C.

Queue q = {0}; inicializuje prázdny front. head je index najstaršieho prvku, ak front nie je prázdny, a tail je index nasledujúceho zápisu, ak front nie je plný. Oba indexy majú rozsah od 0 do CAPACITY - 1. size počíta obsadené miesta, od 0 do CAPACITY. Matematicky platí tail ≡ head + size (mod CAPACITY), takže samotné head == tail nerozlíši prázdny a plný front; rozlíši ich size.

Ak je voľné miesto, enqueue zapíše hodnotu na pozíciu tail, posunie tail a zvýši size. Ak front nie je prázdny, dequeue skopíruje hodnotu z pozície head do *out, posunie head a zníži size. Na posun sa používa (index + 1) % CAPACITY: % vráti zvyšok po delení, takže po poslednom indexe nasleduje 0. CAPACITY musí byť kladná; nulový deliteľ pri % spôsobuje nedefinované správanie.

Obe funkcie vrátia true pri úspechu a false pri odmietnutí operácie pre plný, respektíve prázdny front. Odmietnutie nezmení front a pri dequeue ani *out. q musí ukazovať na inicializovaný front, ktorého životnosť sa ešte neskončila; out musí ukazovať na samostatný, stále existujúci objekt int, do ktorého sa dá zapisovať. Každá operácia trvá O(1) a pole zaberá O(CAPACITY) pamäte. Implementácia nepoužíva dynamickú alokáciu ani nesynchronizuje vlákna. Príklad predpokladá hostované prostredie a nevyžaduje vlastnosti špecifické pre C23; podpora režimu ISO C23 závisí od implementácie.

Príklady

#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

enum { CAPACITY = 3 };

typedef struct {
    int data[CAPACITY];
    size_t head;
    size_t tail;
    size_t size;
} Queue;

static size_t next_index(size_t index)
{
    return (index + 1) % CAPACITY;
}

static bool enqueue(Queue *q, int value)
{
    if (q->size == CAPACITY) {
        return false;
    }
    q->data[q->tail] = value;
    q->tail = next_index(q->tail);
    ++q->size;
    return true;
}

static bool dequeue(Queue *q, int *out)
{
    if (q->size == 0) {
        return false;
    }
    *out = q->data[q->head];
    q->head = next_index(q->head);
    --q->size;
    return true;
}

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");

    if (!dequeue(&q, &value)) {
        return EXIT_FAILURE;
    }
    printf("%d\n", value);
    if (!enqueue(&q, 40)) {
        return EXIT_FAILURE;
    }

    while (dequeue(&q, &value)) {
        printf("%d\n", value);
    }
    puts("empty");
    return EXIT_SUCCESS;
}

Výsledok

full
10
20
30
40
empty

Po troch zápisoch sa `tail` vráti na `0`. Pokus vložiť `99` vypíše `full` bez prepísania `10`. Po odobratí `10` hodnota `40` znova využije pozíciu `0`, ale z frontu vyjde až po `20` a `30`. Neúspešný pokus o odobratie z prázdneho frontu ukončí cyklus; program vypíše `empty`.

Súvisiace lekcie

  • C · Lekcia 86 · Pokročilá · Verzia: 3

Zdroje