Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C

Kolejka FIFO w C: bufor cykliczny

Zaimplementuj kolejkę FIFO o stałej pojemności i użyj indeksów `head` i `tail` oraz licznika `size`, aby ponownie wykorzystywać miejsca w tablicy bez przesuwania elementów.

Wersja: ISO C23; implementation support may vary

Składnia

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;

Kolejka FIFO (first in, first out) usuwa najstarszy spośród elementów, które w niej pozostały. FIFO określa kolejność, a bufor cykliczny to jeden ze sposobów jej realizacji. Queue, enqueue i dequeue są zdefiniowane w przykładzie i nie należą do standardowego API języka C.

Inicjalizacja Queue q = {0}; tworzy pustą kolejkę. head wskazuje indeks najstarszego elementu, gdy kolejka nie jest pusta, a tail wskazuje indeks następnego zapisu, gdy kolejka nie jest pełna. Oba indeksy mieszczą się w zakresie od 0 do CAPACITY - 1. size liczy zajęte miejsca, od 0 do CAPACITY. Matematycznie tail ≡ head + size (mod CAPACITY), więc samo head == tail nie rozróżnia kolejki pustej od pełnej; rozróżnia je size.

Jeśli jest miejsce, enqueue zapisuje wartość pod tail, przesuwa tail i zwiększa size. Jeśli kolejka nie jest pusta, dequeue kopiuje wartość spod head do *out, przesuwa head i zmniejsza size. Przesunięcie to (index + 1) % CAPACITY: % daje resztę z dzielenia, więc po ostatnim indeksie następuje 0. CAPACITY musi być dodatnie; reszta z dzielenia przez zero oznacza niezdefiniowane zachowanie.

Obie funkcje zwracają true po sukcesie i false po odmowie z powodu pełnej lub pustej kolejki. Odmowa nie zmienia kolejki ani, w przypadku dequeue, *out. q musi wskazywać zainicjalizowaną kolejkę w trakcie jej życia, a out — osobny obiekt int, który nadal istnieje i do którego można zapisać. Każda operacja zajmuje O(1) czasu, a tablica zajmuje O(CAPACITY) pamięci. Implementacja nie korzysta z dynamicznej alokacji ani nie synchronizuje wątków. Przykład zakłada środowisko hostowane i nie wymaga funkcji charakterystycznych dla C23; obsługa trybu ISO C23 zależy od implementacji.

Przykłady

#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;
}

Wynik

full
10
20
30
40
empty

Po trzech zapisach `tail` wraca do `0`. Próba dodania `99` wypisuje `full`, nie nadpisując `10`. Po usunięciu `10` wartość `40` trafia na zwolnione miejsce o indeksie `0`, ale zostaje odczytana po `20` i `30`. Nieudana próba pobrania z pustej kolejki kończy pętlę; program wypisuje `empty`.

Powiązane lekcje

  • C · Lekcja 86 · Zaawansowany · Wersja: 3

Źródła