Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C

Čakalna vrsta FIFO v C-ju: krožni medpomnilnik

Izvedi čakalno vrsto FIFO s fiksno kapaciteto ter z `head`, `tail` in `size` znova uporabi mesta v tabeli, ne da bi premikal elemente.

Različica: 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;

Čakalna vrsta FIFO (first in, first out, prvi noter, prvi ven) odstrani najstarejši element, ki je še v vrsti. FIFO določa vrstni red; krožni medpomnilnik je eden od načinov izvedbe. Queue, enqueue in dequeue so definirani v primeru in niso del standardne knjižnice jezika C.

Queue q = {0}; inicializira prazno vrsto. head je indeks najstarejšega elementa, kadar vrsta ni prazna, tail pa je indeks naslednjega vpisa, kadar vrsta ni polna. Oba indeksa sta v območju od 0 do CAPACITY - 1. size šteje zasedena mesta, od 0 do CAPACITY. Matematično velja tail ≡ head + size (mod CAPACITY), zato samo head == tail ne loči prazne vrste od polne; loči ju size.

Če je v vrsti prostor, enqueue zapiše vrednost na mesto tail, premakne tail naprej in poveča size. Če vrsta ni prazna, dequeue prekopira vrednost z mesta head v *out, premakne head naprej in zmanjša size. Za premik se uporabi (index + 1) % CAPACITY: % vrne ostanek pri deljenju, zato zadnjemu indeksu sledi 0. CAPACITY mora biti pozitivna; delitelj nič pri % povzroči nedefinirano obnašanje.

Obe funkciji vrneta true ob uspehu in false, če je operacija zavrnjena, ker je vrsta polna oziroma prazna. Zavrnitev ne spremeni vrste, pri dequeue pa tudi ne *out. q mora kazati na inicializirano vrsto, katere življenjska doba še ni potekla; out mora kazati na ločen objekt tipa int, ki še obstaja in vanj je mogoče pisati. Vsaka operacija traja O(1), tabela pa zasede O(CAPACITY) pomnilnika. Izvedba ne dodeljuje pomnilnika dinamično in ne sinhronizira niti. Primer predpostavlja gostovano okolje in ne zahteva funkcionalnosti, značilnih za C23; podpora za način ISO C23 je odvisna od implementacije.

Primeri

#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

Po treh vpisih se `tail` vrne na `0`. Poskus vstavljanja `99` izpiše `full`, ne da bi prepisal `10`. Po odstranitvi `10` vstavljanje `40` znova uporabi mesto `0`, vendar `40` pride iz vrste za `20` in `30`. Neuspešen poskus odstranitve iz prazne vrste konča zanko; program izpiše `empty`.

Povezane lekcije

  • C · Lekcija 86 · Napredna · Različica: 3

Viri