CKTIS / C
Fila FIFO com buffer circular
Implemente uma fila FIFO de capacidade fixa num vetor com dois índices e um contador, para reutilizar as posições libertadas sem deslocar elementos.
Versão: ISO C23; implementation support may vary
Sintaxe
#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. */Em FIFO, retira-se primeiro o elemento inserido há mais tempo entre os que ainda estão na fila. Um buffer circular mantém esta ordem num vetor de capacidade fixa: após a última posição, o índice volta a zero sem deslocar elementos. É um padrão de implementação, não um tipo da biblioteca padrão de C. O exemplo não usa funcionalidades exclusivas de C23; o suporte de C23 varia consoante a implementação.
Nesta convenção, head indica o próximo elemento a ler quando a fila não está vazia, tail a próxima posição de escrita quando não está cheia e size conta os elementos. Para CAPACITY > 0, os índices estão em [0, CAPACITY) e size em [0, CAPACITY]. Matematicamente, tail é igual a (head + size) mod CAPACITY. Os três campos começam a zero. head == tail verifica-se tanto quando a fila está vazia como quando está cheia; size distingue os dois estados. Todas as posições podem ser usadas.
enqueue recusa a escrita quando size == CAPACITY, sem sobrescrever nada. Caso contrário, escreve no índice tail, avança-o e incrementa size. dequeue recusa a leitura quando size == 0; caso contrário, copia o valor no índice head para *out, avança head e decrementa size. Ambas devolvem 1 em caso de sucesso e 0 em caso de recusa; a recusa deixa a fila e a eventual variável de saída inalteradas. A remoção não apaga a posição. (i + 1) % CAPACITY usa o resto da divisão inteira para levar um índice válido da última posição de volta a zero. A capacidade não tem de ser uma potência de dois; o divisor não pode ser zero.
Cada operação demora tempo O(1) e o vetor ocupa espaço O(CAPACITY). Passe um apontador para uma fila inicializada cujo tempo de vida ainda não terminou; out deve apontar para um objeto int distinto e gravável. A implementação não sincroniza os acessos: se várias threads acederem à fila e pelo menos uma a modificar, é necessária sincronização externa.
Exemplos
#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;
}
Resultado
full: rejected 99 dequeued: 10 dequeued: 20 dequeued: 30 dequeued: 40 empty: nothing to dequeue
Depois de inserir `10`, `20` e `30`, a fila recusa `99`. Remover `10` liberta a posição `0` para `40`. Apesar da sua posição no vetor, `40` sai depois de `20` e `30`. A última tentativa de remoção encontra a fila vazia.
Lições relacionadas
- C · Lição 86 · Avançado · Versão: 3