CKTIS / C
Fila FIFO em C: buffer circular
Implemente uma fila FIFO de capacidade fixa e use `head`, `tail` e `size` para reutilizar posições do vetor sem deslocar os elementos.
Versão: ISO C23; implementation support may vary
Sintaxe
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;Uma fila FIFO (first in, first out, primeiro a entrar, primeiro a sair) retira o elemento mais antigo ainda presente. FIFO define a ordem; um buffer circular é uma forma de a implementar. Queue, enqueue e dequeue são definidos no exemplo e não pertencem à biblioteca padrão de C.
Queue q = {0}; inicializa uma fila vazia. head é o índice do elemento mais antigo quando a fila não está vazia, e tail é o índice da próxima escrita quando não está cheia. Ambos os índices vão de 0 a CAPACITY - 1. size conta as posições ocupadas, de 0 a CAPACITY. Matematicamente, tail ≡ head + size (mod CAPACITY), pelo que head == tail não distingue, por si só, uma fila vazia de uma cheia; quem as distingue é size.
Se houver espaço, enqueue escreve na posição tail, avança tail e incrementa size. Se a fila não estiver vazia, dequeue copia para *out o valor na posição head, avança head e decrementa size. Para avançar, usa-se (index + 1) % CAPACITY: % dá o resto da divisão, pelo que depois do último índice se volta a 0. CAPACITY tem de ser positiva; um divisor nulo em % causa comportamento indefinido.
As duas funções devolvem true em caso de sucesso e false quando a operação é recusada por a fila estar cheia ou vazia, respetivamente. A recusa não altera a fila nem, no caso de dequeue, *out. q tem de apontar para uma fila inicializada cujo tempo de vida não tenha terminado; out tem de apontar para um objeto int distinto, ainda válido e que permita escrita. Cada operação demora O(1) e o vetor ocupa O(CAPACITY) de memória. Esta implementação não faz alocação dinâmica de memória nem sincroniza threads. O exemplo pressupõe um ambiente alojado e não precisa de funcionalidades específicas de C23; o suporte do modo ISO C23 depende da implementação.
Exemplos
#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;
}
Resultado
full 10 20 30 40 empty
Após três escritas, `tail` volta a `0`. A tentativa de inserir `99` escreve `full` sem sobrescrever `10`. Depois de retirar `10`, a inserção de `40` reutiliza a posição `0`, mas `40` sai depois de `20` e `30`. A tentativa falhada de retirar da fila vazia termina o ciclo; o programa escreve `empty`.
Lições relacionadas
- C · Lição 86 · Avançado · Versão: 3