Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C

Kolejka FIFO w buforze cyklicznym

Zaimplementuj kolejkę FIFO o stałej pojemności w tablicy, używając dwóch indeksów i licznika, aby ponownie wykorzystywać zwolnione miejsca bez przesuwania elementów.

Wersja: ISO C23; implementation support may vary

Składnia

#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 oznacza, że najwcześniej dodany element, który nadal jest w kolejce, zostaje pobrany jako pierwszy. Bufor cykliczny realizuje tę kolejność w tablicy o stałej pojemności: po ostatniej komórce indeks wraca do zera, a elementy nie są przesuwane. To wzorzec implementacji, nie typ z biblioteki standardowej C. Przykład nie wymaga elementów wprowadzonych w C23; zakres obsługi C23 zależy od implementacji.

W tej konwencji head wskazuje następny element do odczytu, gdy kolejka nie jest pusta, tail wskazuje następne miejsce zapisu, gdy kolejka nie jest pełna, a size liczy elementy. Dla CAPACITY > 0 oba indeksy należą do [0, CAPACITY), a size do [0, CAPACITY]. Matematycznie tail jest równe (head + size) mod CAPACITY. Początkowo wszystkie trzy pola mają wartość zero. head == tail zachodzi zarówno w pustej, jak i w pełnej kolejce; rozróżnia je size. Można wykorzystać wszystkie komórki.

enqueue odrzuca zapis przy size == CAPACITY, niczego nie nadpisując. W przeciwnym razie zapisuje pod indeksem tail, przesuwa go i zwiększa size. dequeue odrzuca odczyt przy size == 0; w przeciwnym razie kopiuje wartość spod head do *out, przesuwa head i zmniejsza size. Obie operacje zwracają 1 po sukcesie i 0 po odmowie; odmowa nie zmienia kolejki ani zmiennej wyjściowej. Pobranie nie zeruje komórki. Aktualizacja (i + 1) % CAPACITY używa reszty z dzielenia i dla poprawnego indeksu zawija go z ostatniej pozycji do zera. Nie wymaga pojemności będącej potęgą dwóch; dzielnik nie może być zerem.

Każda operacja trwa O(1), a tablica zajmuje O(CAPACITY) pamięci. Przekazuj wskaźnik do istniejącej, zainicjalizowanej kolejki; out ma wskazywać osobny, zapisywalny obiekt int. Implementacja nie synchronizuje dostępu: jeśli kilka wątków korzysta z kolejki i co najmniej jeden ją modyfikuje, potrzebna jest synchronizacja zewnętrzna.

Przykłady

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

Wynik

full: rejected 99
dequeued: 10
dequeued: 20
dequeued: 30
dequeued: 40
empty: nothing to dequeue

Po dodaniu `10`, `20` i `30` kolejka odrzuca `99`. Pobranie `10` zwalnia komórkę `0` dla `40`. Mimo tej pozycji w tablicy `40` wychodzi po `20` i `30`. Ostatnia próba pobrania zastaje pustą kolejkę.

Powiązane lekcje

  • C · Lekcja 86 · Zaawansowany · Wersja: 3

Źródła