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.
- Network interface receive rings, where packets arrive faster than the protocol stack drains them.
- Audio and video pipelines, where frames must be delivered at a steady cadence rather than in bursts.
- Keyboard input buffers in embedded firmware, where a burst of key presses during a game at the MCG must not be lost.
- Producer and consumer work queues in threaded servers, paired with condition variables for waiting.
- Telemetry windows on dashboards, keeping the most recent samples and discarding the oldest when the buffer fills.
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.