Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C

FIFO red s kružnim međuspremnikom

Izvedi FIFO red stalnog kapaciteta u polju s dva indeksa i brojačem kako bi se oslobođena mjesta ponovno koristila bez premještanja elemenata.

Verzija: ISO C23; implementation support may vary

Sintaksa

#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 znači da se prvo uklanja najranije umetnuti element među onima koji su još u redu. Kružni međuspremnik održava taj redoslijed u polju stalnog kapaciteta: nakon posljednjeg mjesta indeks se vraća na nulu, bez premještanja elemenata. To je način implementacije, a ne tip iz standardne biblioteke jezika C. Primjer ne koristi značajke uvedene tek u C23; podrška za C23 ovisi o implementaciji.

Prema ovoj konvenciji head označava sljedeći element za čitanje kad red nije prazan, tail sljedeće mjesto za upis kad nije pun, a size broj elemenata. Za CAPACITY > 0 oba su indeksa u [0, CAPACITY), a size je u [0, CAPACITY]. Matematički je tail jednak (head + size) mod CAPACITY. Sva tri člana strukture počinju od nule. head == tail vrijedi i kad je red prazan i kad je pun; size razlikuje ta stanja. Sva se mjesta mogu iskoristiti.

enqueue odbija upis kad je size == CAPACITY i ništa ne prepisuje. Inače upisuje na indeks tail, pomiče ga naprijed i povećava size. dequeue odbija čitanje kad je size == 0; inače kopira vrijednost s indeksa head u *out, pomiče head naprijed i smanjuje size. Obje funkcije vraćaju 1 pri uspjehu i 0 pri odbijanju; odbijanje ne mijenja red ni eventualnu izlaznu varijablu. Uklanjanje ne briše sadržaj mjesta. Izraz (i + 1) % CAPACITY koristi ostatak cjelobrojnog dijeljenja kako bi valjani indeks s posljednjeg mjesta vratio na nulu. Kapacitet ne mora biti potencija broja dva; djelitelj ne smije biti nula.

Svaka operacija traje O(1), a polje zauzima O(CAPACITY) prostora. Predaj pokazivač na inicijalizirani red kojem životni vijek nije završio; out mora pokazivati na zaseban objekt tipa int u koji se može pisati. Implementacija ne sinkronizira pristup: ako redu pristupa više dretvi i barem ga jedna mijenja, potrebna je vanjska sinkronizacija.

Primjeri

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

Rezultat

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

Nakon umetanja `10`, `20` i `30`, red odbija `99`. Uklanjanje `10` oslobađa mjesto `0` za `40`. Unatoč položaju u polju, `40` izlazi nakon `20` i `30`. Pri posljednjem pokušaju uklanjanja red je prazan.

Povezane lekcije

  • C · Lekcija 86 · Napredno · Verzija: 3

Izvori