Queues and circular buffers

FIFO

A queue serves items in arrival order, like a ticket counter line. Typical uses: print jobs, tasks waiting for a worker, messages between parts of a program, and bytes arriving from hardware faster than the program reads them.

Why a circular buffer?

naive array queue after some enqueues and dequeues:
[ x | x | x | 40 | 50 | 60 |    |    ]
              head            tail
the slots before head are wasted; soon tail reaches the end even though space is free

circular buffer: the indexes wrap around to the start
[ 70 | 80 |    | 40 | 50 | 60 ]
        tail      head          (capacity 6, count 5)

Implementation

#define QCAP 8

typedef struct {
    int buf[QCAP];
    int head;     /* index of the oldest item */
    int tail;     /* index where the next item goes */
    int count;    /* items stored */
} Queue;

void q_init(Queue *q) { q->head = q->tail = q->count = 0; }

int enqueue(Queue *q, int v) {
    if (q->count == QCAP) return -1;          /* full */
    q->buf[q->tail] = v;
    q->tail = (q->tail + 1) % QCAP;           /* wrap around */
    q->count++;
    return 0;
}

int dequeue(Queue *q, int *out) {
    if (q->count == 0) return -1;             /* empty */
    *out = q->buf[q->head];
    q->head = (q->head + 1) % QCAP;
    q->count--;
    return 0;
}

Without a count, head == tail is ambiguous (empty or full?). The two standard fixes are keeping a count, as above, or always leaving one slot unused so "full" means (tail + 1) % cap == head. When the capacity is a power of two, (i + 1) & (cap - 1) replaces the % and is a little faster, a trick common in firmware.

Embedded use: a UART receive buffer

A microcontroller's serial port can receive bytes at any moment. An interrupt routine (module 12) stores each byte into a circular buffer as it arrives, and the main loop reads bytes out when it has time. Neither side ever moves data around; they just advance their own index.

Linked-list queues

A queue can also be a linked list with head and tail pointers: enqueue appends at the tail in O(1), dequeue removes from the head in O(1), and there is no fixed capacity, at the cost of a malloc per item.