Queues, Deques, Ring Buffers

This chapter implements queues (FIFO), deques (double-ended), and ring buffers (fixed-size circular queues).

Why This Matters

Queues model producer/consumer and scheduling. Ring buffers are the standard lock-free-friendly, fixed-size queue used everywhere from audio to device drivers to networking. Deques generalize both ends.

Prerequisites

• c.ds.1 — foundations.

Core Concept

Queue

A FIFO structure with enqueue (push back) and dequeue (pop front). Can be built on a linked list or a dynamic array.

Deque

A double-ended queue supporting push/pop at both ends. Can be built on a doubly linked list or a dynamic ring.

Ring buffer

A fixed-size array used circularly, with head and tail indices and modular wraparound. size == capacity when full (or use a sentinel).

typedef struct {
    int *buf;
    size_t head;
    size_t tail;
    size_t capacity;
    size_t size;
} Ring;

Examples

Ring buffer push/pop

#include <stdbool.h>
#include <stdlib.h>

typedef struct {
    int *buf;
    size_t head, tail, capacity, size;
} Ring;

bool ring_push(Ring *r, int v)
{
    if (r->size == r->capacity) return false;
    r->buf[r->tail] = v;
    r->tail = (r->tail + 1) % r->capacity;
    r->size++;
    return true;
}

bool ring_pop(Ring *r, int *out)
{
    if (r->size == 0) return false;
    *out = r->buf[r->head];
    r->head = (r->head + 1) % r->capacity;
    r->size--;
    return true;
}

Queue on a linked list

Enqueue appends to the tail; dequeue removes from the head. Both are O(1) with head/tail pointers.

How It Works

The ring buffer uses modular arithmetic to wrap indices, so the fixed array is reused without shifting. A separate size distinguishes empty from full (the head==tail ambiguity).

Variations

Power-of-two capacity

When capacity is a power of two, % capacity can be replaced with a bitmask (& (capacity-1)), which is faster.

Single-producer single-consumer (SPSC)

A ring buffer can be made lock-free for SPSC by using atomic head/tail indices (c.conc.8).

Common Mistakes

• Confusing empty and full when head == tail.
• Forgetting modular wraparound.
• Indexing with a non-power-of-two modulo repeatedly (correct but slower).

Undefined Behavior

• Reading/writing out of the allocated buffer. VERIFIED
• Use-after-free of the internal buffer.

Portability

• Plain C, fully portable. A power-of-two capacity optimization is fine.

Under the Hood

A ring buffer is contiguous and cache-friendly; the fixed size makes it suitable for real-time and embedded use (no allocation at run time).

Practical Usage

• Use ring buffers for fixed-size producer/consumer queues (audio, serial,

network).

• Use deques for sliding-window and double-ended access patterns.

Exercises

1. Implement a ring buffer with push/pop/is_empty/is_full. 2. Add a peek that returns the front without removing it. 3. Implement a queue on a dynamic array with amortized O(1) enqueue. 4. Make the ring buffer capacity a power of two and use a bitmask.

Deep Challenge

Implement a lock-free SPSC ring buffer using _Atomic head/tail indices, and explain why it is safe for one producer and one consumer but not for multiple of either.

Related Concepts

• c.ds.2 — dynamic arrays.
• c.conc.8 — lock-free structures.
• c.audio.ring-buffer — audio use.

References

• Standard data-structure literature.

Verification

• Ring buffer semantics and SPSC reasoning. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Queue
• [ ] Deque
• [ ] Ring buffer
• [ ] Empty/full disambiguation

Mastery levels