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

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

Fontes