Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C

Cola FIFO en C: búfer circular

Implementa una cola FIFO de capacidad fija y usa `head`, `tail` y `size` para reutilizar las posiciones del arreglo sin desplazar los elementos.

Versión: ISO C23; implementation support may vary

Sintaxis

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;

Una cola FIFO (first in, first out, primero en entrar, primero en salir) retira el elemento más antiguo que aún contiene. FIFO define el orden; un búfer circular es una forma de implementarlo. Queue, enqueue y dequeue se definen en el ejemplo y no forman parte de la biblioteca estándar de C.

Queue q = {0}; inicializa una cola vacía. head es el índice del elemento más antiguo si la cola no está vacía; tail es el índice de la próxima escritura si no está llena. Ambos índices van de 0 a CAPACITY - 1. size cuenta las posiciones ocupadas, de 0 a CAPACITY. Matemáticamente, tail ≡ head + size (mod CAPACITY), así que head == tail por sí solo no distingue una cola vacía de una llena; size sí.

Si hay espacio, enqueue escribe en la posición tail, avanza tail e incrementa size. Si la cola no está vacía, dequeue copia a *out el valor de la posición head, avanza head y decrementa size. Para avanzar se usa (index + 1) % CAPACITY: % da el resto de la división, por lo que después del último índice se vuelve a 0. CAPACITY debe ser positiva; un divisor cero en % provoca un comportamiento indefinido.

Ambas funciones devuelven true si tienen éxito y false si rechazan la operación porque la cola está llena o vacía, respectivamente. El rechazo deja intacta la cola y, en el caso de dequeue, también *out. q debe apuntar a una cola inicializada cuya vida útil no haya terminado; out debe apuntar a un objeto int distinto, vigente y en el que se pueda escribir. Cada operación tarda O(1) y el arreglo ocupa O(CAPACITY) de memoria. Esta implementación no reserva memoria dinámicamente ni sincroniza hilos. El ejemplo presupone un entorno alojado y no requiere características exclusivas de C23; la compatibilidad con el modo ISO C23 varía según la implementación.

Ejemplos

#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

Tras tres escrituras, `tail` vuelve a `0`. El intento de insertar `99` imprime `full` sin sobrescribir `10`. Tras retirar `10`, el valor `40` reutiliza la posición `0`, pero sale después de `20` y `30`. El intento fallido de retirar un elemento de la cola vacía termina el bucle; el programa imprime `empty`.

Lecciones relacionadas

  • C · Lección 86 · Avanzado · Versión: 3

Fuentes