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