Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

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

Fontes