Embedded C

Stacks, Queues & Ring Buffers

The ring buffer isn't just one data structure among several here — it's arguably the single most-used data structure in all of embedded C, because it solves the one problem that comes up in nearly every driver: an interrupt handler produces data at its own unpredictable pace, and the main loop consumes it at a completely different pace, with nothing to make the two agree on timing.

Stacks (LIFO)

A stack supports push, pop, and peek, all O(1) — the last element pushed is always the first one popped. Array-based implementation (a fixed-size array plus a top index) is the standard embedded approach; a linked-list-based stack exists too, but drags in per-node allocation for no benefit a stack actually needs.

#define STACK_SIZE 16
static int data[STACK_SIZE];
static int top = 0;

bool stack_push(int value) {
    if (top >= STACK_SIZE) return false;   // full — never silently overflow
    data[top++] = value;
    return true;
}

bool stack_pop(int *out) {
    if (top == 0) return false;             // empty
    *out = data[--top];
    return true;
}

The call stack is the same structure

This isn't just an analogy — the CPU's own call stack (covered as the Stack region in Storage Classes) is a literal LIFO stack: every function call pushes a frame (local variables, the return address), and returning pops it. An RTOS giving each task its own separate stack — see RTOS — exists specifically because each task needs its own independent LIFO call history, not a shared one every other task would corrupt.

Queues (FIFO) and the naive-shift problem

A queue supports enqueue/dequeue, FIFO order — first in, first out. The naive array implementation shifts every remaining element down by one on every dequeue to keep the front at index 0:

/* naive — O(n) per dequeue, gets worse as the queue grows */
int dequeue_naive(int *arr, int *count) {
    int front = arr[0];
    for (int i = 1; i < *count; i++) {
        arr[i - 1] = arr[i];   // shift everything down one slot
    }
    (*count)--;
    return front;
}

This is a genuine, common beginner mistake — it works correctly, and is O(n) per operation for no real reason. The fix doesn't require a linked list; it requires letting the "front" position move instead of always being index 0, which is exactly what a ring buffer does.

The ring buffer

A ring (circular) buffer is a fixed-size array with two independent indices — head (where the next write goes) and tail (where the next read comes from) — that both wrap back to zero on reaching the end, so a full buffer's worth of space is reused forever without ever shifting a single element.

The one real design problem a ring buffer has to solve: when head == tail, is the buffer empty, or completely full? Both states produce the same index comparison. A count field sidesteps the ambiguity entirely:

#define RB_SIZE 8   // power of 2 — enables the cheap mask below

typedef struct {
    uint8_t buf[RB_SIZE];
    volatile uint8_t head;   // volatile — written by the ISR
    volatile uint8_t tail;   // volatile — written by the main loop
    volatile uint8_t count;  // resolves the head==tail ambiguity
} ring_buffer_t;

bool rb_push(ring_buffer_t *rb, uint8_t byte) {
    if (rb->count == RB_SIZE) return false;      // full
    rb->buf[rb->head] = byte;
    rb->head = (rb->head + 1) & (RB_SIZE - 1);   // wrap via bitmask
    rb->count++;
    return true;
}

bool rb_pop(ring_buffer_t *rb, uint8_t *out) {
    if (rb->count == 0) return false;             // empty
    *out = rb->buf[rb->tail];
    rb->tail = (rb->tail + 1) & (RB_SIZE - 1);
    rb->count--;
    return true;
}

& (RB_SIZE - 1) only works because RB_SIZE is a power of 2 — it's a bitmask equivalent to % RB_SIZE that's meaningfully cheaper on a small MCU without a hardware divider, the same class of "know what the hardware actually costs" reasoning behind preferring unsigned types in Data Types & Integer Overflow.

Real-world applications

• UART RX buffering — the canonical case: a UART receive interrupt pushes each incoming byte into a ring buffer, and the main loop drains it at its own pace — see UART.
• RTOS message queues — built on exactly this FIFO/ring-buffer concept, extended with blocking semantics — see RTOS.
• DMA/audio sample buffering — a DMA peripheral filling one half of a ring buffer while processing code reads the other half is the same pattern at a larger scale.
• Logging buffers — a fixed-size circular log buffer that keeps only the most recent N entries, overwriting the oldest, is a ring buffer used deliberately as a bounded history.

Gotchas