Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Building a Circular Queue in C with a Fixed-Size Array

A queue is one of the first data structures most people meet and one of the easiest to take for granted. The textbook version keeps its elements in a plain array and slides everything along whenever the front element leaves, which sounds tidy but costs time on every dequeue and leaves a growing hole at the front of the buffer. Replace that shifting with a pair of indices that wrap back to the start of the array and the same structure handles every operation in constant time.

This article builds that version from nothing: a fixed-size array, two indices and a counter, written in plain C with no library calls and no heap allocation. The same idea sits behind the receive buffer in a network card, the sliding window on a live dashboard, and the pile of scan events building up at a Woolworths self-checkout when half the shop decides to shop at once on a Saturday arvo. Getting the mechanics right also makes the surrounding theory — FIFO ordering, amortised costs, producer and consumer threads — far easier to hold on to.

Why the shifting version falls over

Consider the obvious implementation. Data lives in int buffer[100], and a head index marks the front while a tail index marks the back. When you dequeue, you copy every remaining element one position to the left and decrement the tail. That copy is the problem: removing one item from a queue holding a hundred items means a hundred assignments, so the operation is O(n) rather than O(1), and the front of the array accumulates dead space that has to be reclaimed by compaction.

The fix is to stop thinking of the array as a line with a beginning and an end. Treat it as a ring. The tail index advances until it reaches the last slot, at which point it returns to slot zero and carries on from there. Nothing ever moves, so nothing ever gets copied, and the space freed at the front is reused immediately by the next write.

Real systems rely on exactly this behaviour. The barcode reader at a Coles self-checkout fires off scan events faster than the checkout application can price them up, so the events wait in a small ring until the main loop drains them. Sydney bus operators use the same pattern for tap-on data coming off Opal card readers: vehicles disappear from the network for stretches, and the buffered records fill the gap without a single lost journey.

Laying out the memory and the two indices

A circular queue built on a fixed array needs four pieces of state: the storage itself, its capacity, the index of the next element to remove, the index where the next element will be written, and a count of how many elements are currently stored. The two indices are usually called head and tail.

Here is the subtlety that trips people up first. When the queue is empty, head equals tail. When the queue is full, head also equals tail. The two states look identical from the indices alone, so something has to distinguish them.

Two solutions exist. You can keep an explicit count of stored elements, which is what this implementation does, and the empty and full cases become unambiguous. The alternative is to sacrifice one slot: never allow the tail to catch the head, so a full queue is detected by the next index being the head, and one cell of capacity goes unused. The count is slightly more memory but wastes nothing, and for an array of integers the extra four bytes rarely matter.

A typical state looks like this, with three items stored and the tail having already wrapped past the end of the array:

index:    0     1     2     3     4
        +-----+-----+-----+-----+-----+
        | 70  |  .  |  .  | 40  | 50  |
        +-----+-----+-----+-----+-----+

Here head is 3, pointing at 40, the next value to be removed, and tail is 1, pointing at the cell where the next write will land. The values 70, 40 and 50 are the live elements, read in that order. The dot at index 1 is empty even though the tail sits there, because the tail marks the destination of the next write rather than a stored item.

The arithmetic that keeps the indices in range

Every index update is the same piece of arithmetic: add one, then reduce modulo the capacity. Advancing the tail after a write is tail = (tail + 1) % capacity, and advancing the head after a read is head = (head + 1) % capacity. The modulo operator wraps the value back into the range zero to capacity minus one, which is precisely the behaviour a ring needs.

In pseudocode, the two operations are short enough to see in one glance:

enqueue(value):
    if count == capacity: return FULL
    buffer[tail] = value
    tail = (tail + 1) % capacity
    count = count + 1
    return OK

dequeue():
    if count == 0: return EMPTY
    value = buffer[head]
    head = (head + 1) % capacity
    count = count - 1
    return OK

Note that neither index ever goes negative, which matters because C's % operator produces a negative remainder when the left operand is negative — a genuine hazard in other languages, and one that C programmers still meet in loops that count down. Here the only risk is a capacity of zero, which would cause a division by zero inside the modulo. The guards prevent it: with capacity zero, count equals capacity immediately, so the enqueue returns full and the modulo is never reached.

A complete implementation in C

The following version keeps its storage in an array supplied by the caller, so the queue itself can live on the stack and no allocation is required. If you would rather see how pointers and dynamic memory are handled, the language basics and memory rules are set out in our C programming notes.

#include <stdbool.h>
#include <stddef.h>

typedef enum {
    QUEUE_OK = 0,
    QUEUE_EMPTY,
    QUEUE_FULL
} queue_status;

typedef struct {
    int   *items;
    size_t capacity;
    size_t head;   /* next element to be removed */
    size_t tail;   /* where the next element will be written */
    size_t count;  /* elements currently stored */
} circular_queue;

void queue_init(circular_queue *q, int *storage, size_t capacity) {
    q->items    = storage;
    q->capacity = capacity;
    q->head     = 0;
    q->tail     = 0;
    q->count    = 0;
}

queue_status queue_enqueue(circular_queue *q, int value) {
    if (q->count == q->capacity) {
        return QUEUE_FULL;
    }
    q->items[q->tail] = value;
    q->tail = (q->tail + 1) % q->capacity;
    q->count++;
    return QUEUE_OK;
}

queue_status queue_dequeue(circular_queue *q, int *out) {
    if (q->count == 0) {
        return QUEUE_EMPTY;
    }
    *out = q->items[q->head];
    q->head = (q->head + 1) % q->capacity;
    q->count--;
    return QUEUE_OK;
}

bool   queue_is_empty(const circular_queue *q) { return q->count == 0; }
bool   queue_is_full (const circular_queue *q) { return q->count == q->capacity; }
size_t queue_size     (const circular_queue *q) { return q->count; }

A short driver shows the wrap in action, with a five-slot buffer that fills, drains two elements and then accepts two more values into the slots freed at the front:

int main(void) {
    int storage[5];
    circular_queue q;
    queue_init(&q, storage, 5);

    for (int i = 1; i <= 5; i++) {
        queue_enqueue(&q, i * 10);          /* 10 20 30 40 50 */
    }

    int out;
    queue_dequeue(&q, &out);                /* out == 10 */
    queue_dequeue(&q, &out);                /* out == 20 */
    queue_enqueue(&q, 60);                  /* writes index 0 */
    queue_enqueue(&q, 70);                  /* writes index 1 */
    queue_dequeue(&q, &out);                /* out == 30 */
    return 0;
}

Compile it with gcc -std=c11 -Wall -Wextra -pedantic queue.c -o queue and the compiler will point out any signed and unsigned mixing you introduce, which is the most common source of subtle index bugs in this kind of code.

Comparing the queue implementations you could have built instead

Weighing the available options against each other makes it clearer when the ring structure is worth the effort and when a simpler queue would do the job just as well:

Approach Memory behaviour enqueue / dequeue cost Capacity wasted Best fit
Linked-list queue One heap node per item, scattered addresses O(1) both None Unbounded or unpredictable sizes
Linear array with shifting Contiguous, front compacted by copying O(n) enqueue, O(1) dequeue Up to one array length Teaching examples only
Dynamic array with realloc Contiguous, grows on demand O(1) amortised Occasional reallocation copy General-purpose library queues
Circular queue on a fixed array Contiguous, allocated once O(1) both, no copying None when a count is kept Embedded and bounded buffers
Single-producer ring with atomic indices Contiguous, two indices only O(1) with no locks None Audio, video and network pipelines

The linked list gives you flexibility but pays for it in allocations and cache misses. The dynamic array is the sensible default for a general library queue. The fixed circular queue wins whenever the size of the buffer is known in advance and the data must not be copied or moved, which is exactly the situation in firmware, drivers and real-time pipelines. The lock-free variant at the bottom is the version you will meet inside a network card or a codec.

Pitfalls that quietly corrupt the buffer

Most bugs in this structure come from the same handful of mistakes, and each of them produces wrong answers long before it produces a crash. The compiler is happy with all of them, so the only defence is checking the invariants by hand after every change.

A second round of problems appears when the queue grows a thread safety requirement. Without a lock, a producer writing the tail and a consumer writing the head can still interfere through the count field, which both threads update. The usual remedy is a mutex around the operations, or a careful redesign in which the producer owns the tail and the consumer owns the head, with the count field left out entirely. Getting the locking wrong produces a buffer that occasionally returns the same element twice, which is far harder to diagnose than a crash.

Where ring buffers turn up in working software

Once the mechanics are second nature, the same pattern turns up everywhere, usually with the same four ingredients: fixed storage, two indices, a full check and an empty check.

The applications are varied enough that the structure proves its worth well beyond coursework, and the reason it survives is that it never copies data and never asks the operating system for more memory mid-flight.

String processing work benefits from the same careful thinking about buffers and index handling, and a detailed Manacher's algorithm walkthrough shows how much can be achieved once the memory layout is fully under control. None of this is exotic technology: three fields, two index updates and a pair of comparisons are enough to describe it, yet the same arithmetic is still running behind the card reader at a self-checkout lane and behind the crowd noise filter at a Friday night AFL game in Melbourne, where the commentary feed and the stadium data both arrive faster than anyone can read them.