CKTIS / C
Cola FIFO con búfer circular
Implementa una cola FIFO de capacidad fija en un arreglo con dos índices y un contador, para reutilizar las posiciones libres sin desplazar elementos.
Versión: ISO C23; implementation support may vary
Sintaxis
#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. */FIFO significa que se extrae primero el elemento que se insertó antes de todos los que aún siguen en la cola. Un búfer circular mantiene ese orden en un arreglo de capacidad fija: tras la última posición, el índice vuelve a cero sin desplazar ningún elemento. Es un patrón de implementación, no un tipo de la biblioteca estándar de C. El ejemplo no usa características exclusivas de C23; la compatibilidad con C23 depende de la implementación.
En esta convención, head indica el próximo elemento que se puede leer si la cola no está vacía, tail la próxima posición de escritura si no está llena y size el número de elementos. Con CAPACITY > 0, los índices están en [0, CAPACITY) y size en [0, CAPACITY]. Matemáticamente, tail es (head + size) mod CAPACITY. Los tres campos empiezan en cero. head == tail se cumple tanto en una cola vacía como en una llena; size las distingue. Todas las posiciones son utilizables.
enqueue rechaza la escritura cuando size == CAPACITY sin sobrescribir nada. Si hay sitio, escribe en tail, avanza ese índice e incrementa size. dequeue rechaza la lectura cuando size == 0; de lo contrario, copia el valor de head a *out, avanza head y decrementa size. Ambas devuelven 1 si tienen éxito y 0 si rechazan la operación; el rechazo no cambia la cola ni la variable de salida, si la hay. La extracción no borra la posición. (i + 1) % CAPACITY usa el resto de la división entera para que un índice válido vuelva de la última posición a cero. La capacidad no tiene que ser una potencia de dos; el divisor no puede ser cero.
Cada operación tarda O(1) y el arreglo ocupa O(CAPACITY) de espacio. Pasa un puntero a una cola inicializada cuyo tiempo de vida no haya terminado; out debe apuntar a un objeto int distinto y modificable. No hay sincronización interna: si varios hilos acceden a la cola y al menos uno la modifica, hace falta sincronización externa.
Ejemplos
#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
Tras insertar `10`, `20` y `30`, la cola rechaza `99`. Extraer `10` libera la posición `0` para `40`. Pese a su posición en el arreglo, `40` sale después de `20` y `30`. En el último intento de extracción, la cola está vacía.
Lecciones relacionadas
- C · Lección 86 · Avanzado · Versión: 3