CKTIS / C
FIFO queue in C: a circular buffer
Implement a fixed-capacity FIFO queue and use `head`, `tail`, and `size` to reuse array slots without shifting elements.
Version: ISO C23; implementation support may vary
Syntax
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;A FIFO queue (first in, first out) removes the oldest item still in the queue. FIFO defines the order; a circular buffer is one way to implement it. Queue, enqueue, and dequeue are defined by the example, not by the C standard library.
Queue q = {0}; initializes an empty queue. head indexes the oldest item when the queue is not empty, and tail indexes the next write when the queue is not full. Both indices range from 0 to CAPACITY - 1. size counts occupied slots, from 0 to CAPACITY. Mathematically, tail ≡ head + size (mod CAPACITY), so head == tail alone cannot distinguish empty from full; size does.
If there is room, enqueue writes at tail, advances tail, and increments size. If the queue is not empty, dequeue copies the value at head into *out, advances head, and decrements size. Each advance uses (index + 1) % CAPACITY: % gives the remainder, so advancing from the last index returns to 0. CAPACITY must be positive; a zero divisor for % causes undefined behavior.
Both functions return true on success and false when refused because the queue is full or empty, respectively. Refusal leaves the queue unchanged and, for dequeue, leaves *out unchanged. q must point to a live, initialized queue; out must point to a separate, live, writable int object. Each operation takes O(1) time and the array uses O(CAPACITY) storage. This implementation neither allocates dynamically nor synchronizes threads. The example assumes a hosted environment and needs no C23-specific features; support for ISO C23 mode varies by implementation.
Examples
#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;
}
Result
full 10 20 30 40 empty
After three writes, `tail` wraps to `0`. Attempting to insert `99` prints `full` without overwriting `10`. After removing `10`, inserting `40` reuses slot `0`, but `40` still comes out after `20` and `30`. A failed removal from the empty queue ends the loop; the program prints `empty`.
Related lessons
- C · Lesson 86 · Advanced · Version: 3