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

CKTIS / C

Fronta FIFO v C: kruhový buffer

Implementuj frontu FIFO s pevnou kapacitou a pomocí `head`, `tail` a `size` znovu využívej pozice v poli bez přesouvání prvků.

Verze: ISO C23; implementation support may vary

Syntaxe

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;

Fronta FIFO (first in, first out, první dovnitř, první ven) odebírá nejstarší prvek, který v ní ještě je. FIFO určuje pořadí; kruhový buffer je jeden ze způsobů implementace. Queue, enqueue a dequeue jsou definovány v příkladu a nejsou součástí standardní knihovny jazyka C.

Queue q = {0}; inicializuje prázdnou frontu. head je index nejstaršího prvku, pokud fronta není prázdná, a tail je index příštího zápisu, pokud není plná. Oba indexy jsou v rozsahu 0 až CAPACITY - 1. size počítá obsazené pozice, od 0 do CAPACITY. Matematicky platí tail ≡ head + size (mod CAPACITY), takže samotné head == tail nerozliší prázdnou a plnou frontu; rozliší je size.

Pokud je místo, enqueue zapíše hodnotu na pozici tail, posune tail a zvýší size. Pokud fronta není prázdná, dequeue zkopíruje hodnotu z pozice head do *out, posune head a sníží size. K posunu slouží (index + 1) % CAPACITY: % vrací zbytek po dělení, takže po posledním indexu následuje 0. CAPACITY musí být kladná; nulový dělitel u % způsobuje nedefinované chování.

Obě funkce vracejí true při úspěchu a false při odmítnutí operace kvůli plné, respektive prázdné frontě. Odmítnutí nemění frontu a v případě dequeue ani *out. q musí ukazovat na inicializovanou frontu, jejíž doba života ještě neskončila; out musí ukazovat na samostatný, stále existující objekt int, do kterého lze zapisovat. Každá operace trvá O(1) a pole zabírá O(CAPACITY) paměti. Implementace nepoužívá dynamickou alokaci ani nesynchronizuje vlákna. Příklad předpokládá hostované prostředí a nevyžaduje vlastnosti specifické pro C23; podpora režimu ISO C23 závisí na implementaci.

Pří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ýsledek

full
10
20
30
40
empty

Po třech zápisech se `tail` vrátí na `0`. Pokus vložit `99` vypíše `full`, aniž by přepsal `10`. Po odebrání `10` využije `40` znovu pozici `0`, ale z fronty vyjde až po `20` a `30`. Neúspěšný pokus o odebrání z prázdné fronty ukončí smyčku; program vypíše `empty`.

Související lekce

  • C · Lekce 86 · Pokročilá · Verze: 3

Zdroje