Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C

FIFO queue with a circular buffer

Implement a fixed-capacity FIFO queue in an array using two indices and a count, so freed slots can be reused without shifting elements.

Version: ISO C23; implementation support may vary

Syntax

#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 means the earliest inserted item still in the queue is removed first. A circular buffer implements that order in a fixed-capacity array: after the last slot, an index wraps to zero and no elements are shifted. This is an implementation pattern, not a C standard-library type. The example uses no C23-only features; C23 support varies by implementation.

In this convention, head marks the next item to read when nonempty, tail marks the next slot to write when not full, and size counts the items. With CAPACITY > 0, both indices are in [0, CAPACITY) and size is in [0, CAPACITY]. Mathematically, tail equals (head + size) mod CAPACITY. All three fields start at zero. head == tail holds both when empty and when full; size distinguishes them. Every slot is usable.

enqueue rejects a write at size == CAPACITY without overwriting anything. Otherwise it writes at tail, advances it, and increments size. dequeue rejects a read at size == 0; otherwise it copies the value at head to *out, advances head, and decrements size. Both return 1 on success and 0 on rejection; rejection leaves the queue and any output variable unchanged. Removal does not erase the slot. The update (i + 1) % CAPACITY uses integer remainder to wrap a valid index from the last slot to zero. Capacity need not be a power of two; the divisor must not be zero.

Each operation takes O(1) time, and the array uses O(CAPACITY) space. Pass a pointer to a live, initialized queue; out must point to a separate writable int. The implementation provides no synchronization: if multiple threads access the queue and at least one modifies it, external synchronization is required.

Examples

#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;
}

Result

full: rejected 99
dequeued: 10
dequeued: 20
dequeued: 30
dequeued: 40
empty: nothing to dequeue

After inserting `10`, `20`, and `30`, the queue rejects `99`. Removing `10` frees slot `0` for `40`. Despite its position in the array, `40` comes out after `20` and `30`. The last removal attempt finds the queue empty.

Related lessons

  • C · Lesson 86 · Advanced · Version: 3

Sources