Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C

FIFO red u C-u: kružni međuspremnik

Implementiraj FIFO red fiksnog kapaciteta i upotrijebi `head`, `tail` i `size` za ponovnu uporabu mjesta u polju bez pomicanja elemenata.

Verzija: ISO C23; implementation support may vary

Sintaksa

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;

FIFO red (first in, first out, prvi ulazi, prvi izlazi) uklanja najstariji element koji je još u redu. FIFO određuje redoslijed; kružni međuspremnik jedan je način izvedbe. Queue, enqueue i dequeue definirani su u primjeru i nisu dio standardne biblioteke jezika C.

Queue q = {0}; inicijalizira prazan red. head je indeks najstarijeg elementa kad red nije prazan, a tail je indeks sljedećeg upisa kad red nije pun. Oba su indeksa u rasponu od 0 do CAPACITY - 1. size broji zauzeta mjesta, od 0 do CAPACITY. Matematički vrijedi tail ≡ head + size (mod CAPACITY), pa sam uvjet head == tail ne razlikuje prazan red od punog; razlikuje ih size.

Ako ima mjesta, enqueue upisuje vrijednost na mjesto tail, pomiče tail i povećava size. Ako red nije prazan, dequeue kopira vrijednost s mjesta head u *out, pomiče head i smanjuje size. Za pomak se koristi (index + 1) % CAPACITY: % daje ostatak pri dijeljenju, pa nakon posljednjeg indeksa slijedi 0. CAPACITY mora biti pozitivan; djelitelj nula uz % uzrokuje nedefinirano ponašanje.

Obje funkcije vraćaju true pri uspjehu i false kad je operacija odbijena jer je red pun, odnosno prazan. Odbijanje ne mijenja red, a kod dequeue ni *out. q mora pokazivati na inicijaliziran red čiji životni vijek još traje; out mora pokazivati na zaseban objekt tipa int koji još postoji i u koji se može pisati. Svaka operacija traje O(1), a polje zauzima O(CAPACITY) memorije. Implementacija ne koristi dinamičku dodjelu memorije ni sinkronizaciju dretvi. Primjer pretpostavlja udomljeno okruženje (hosted) i ne zahtijeva značajke specifične za C23; podrška za način rada ISO C23 ovisi o implementaciji.

Primjeri

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

Rezultat

full
10
20
30
40
empty

Nakon triju upisa `tail` se vraća na `0`. Pokušaj umetanja `99` ispisuje `full` bez prepisivanja vrijednosti `10`. Nakon uklanjanja `10`, vrijednost `40` ponovno koristi mjesto `0`, ali izlazi nakon `20` i `30`. Neuspjelo uklanjanje iz praznog reda završava petlju; program ispisuje `empty`.

Povezane lekcije

  • C · Lekcija 86 · Napredno · Verzija: 3

Izvori