Queues (FIFO)

Overview

A queue is one of the most common data structures in all of computing. It models a line: the first item you put in is the first item you take out. This is called FIFO — first in, first out. Think of people waiting at a checkout, print jobs waiting for a printer, or network packets waiting to be sent. Whoever arrived first is served first.

This lesson builds directly on two earlier topics. From Arrays you already know how to store many values of the same type in a contiguous block and index them with [i]. From malloc and the heap you know how to ask the operating system for memory at run time and how to give it back with free. A queue here is just an array (allocated on the heap so its size can be chosen at run time) plus a tiny bit of bookkeeping that tells us where the line starts and how long it is.

The naive way to build a queue on an array is to keep the front at index 0 and shift every element down by one each time you remove the front. That works but is slow — removing one item costs work proportional to the number of items left. The professional solution is the ring buffer: instead of moving the data, we move two indices around a fixed array and let them wrap from the end back to the start, as if the array's two ends were joined into a circle. This lesson teaches the ring buffer because it is the standard, efficient implementation you will see in operating systems, audio drivers, and network stacks.

Key terminology you will use throughout:

• Front / head — the end you remove from.
• Back / tail — the end you add to.
• Enqueue — add an item at the back.
• Dequeue — remove (and usually return) the item at the front.
• Capacity (cap) — the maximum number of items the buffer can hold.
• Length (len) — how many items are in the queue right now.

Why it matters

Queues appear wherever work arrives faster than it can be processed, or wherever order must be preserved. A few concrete examples:

• Operating systems schedule processes and I/O requests with queues so tasks are handled fairly and in order.
• Networking uses queues (often ring buffers) for packets waiting in a network card before the CPU reads them.
• Audio and video pipelines use ring buffers so a producer (a microphone) and a consumer (the speaker driver) can run at slightly different speeds without losing samples.
• Web servers and message systems queue incoming requests or messages so bursts do not overwhelm the workers.

The ring-buffer version specifically matters because it gives O(1) (constant-time) enqueue and dequeue with no memory allocation per operation and no data copying. That predictability is exactly what real-time and embedded systems need: an audio driver cannot afford to call malloc in the middle of playing a sound. Learning to reason about wrap-around indices and full/empty conditions is also excellent training for the kind of careful bounds-thinking that prevents buffer overflows in C.

Core concepts

1. FIFO ordering

Definition. A queue is a collection where elements are removed in the same order they were added: first in, first out.

Plain language. It is a fair line. New arrivals go to the back; service happens at the front. Contrast this with a stack, which is LIFO (last in, first out) — like a stack of plates where you take the top one you just put down.

When to use it. Use a queue whenever order of arrival must be preserved: task scheduling, breadth-first search, buffering a stream of data between a fast producer and a slow consumer. Do not use a queue when you need random access by position, or when the most-recently-added item should come out first (use a stack), or when items have priorities (use a priority queue / heap).

Pitfall. Beginners sometimes mix up which end is which. Always pin it down: enqueue at the back, dequeue at the front.

  enqueue --> [ A ][ B ][ C ] --> dequeue
  (back)                          (front)
  C was added last; A leaves first.

Knowledge check. You enqueue 10, then 20, then 30, then dequeue once. Which value comes out, and what is left in the queue?

2. The ring buffer (circular buffer)

Definition. A ring buffer is a fixed-size array used as if its last index were followed by its first index, forming a logical circle. A queue stored in it tracks head (index of the front item) and len (how many items are stored).

Plain language. Imagine the array bent into a ring. As you enqueue, the back advances clockwise; as you dequeue, the front advances clockwise too. The data never moves — only the indices do. When an index reaches the end of the underlying array, it wraps to index 0.

How it works internally. Two facts drive everything:

• The next free slot (where the next enqueue goes) is (head + len) % cap.
• After a dequeue, the new front is (head + 1) % cap, and len decreases by one.

The % cap (modulo capacity) is what produces the wrap-around. If cap is 5 and an index would be 5, 5 % 5 == 0, so it lands back at the start.

Structure (memory layout).

cap = 5, head = 3, len = 3   (queue holds items at 3, 4, 0)

index:   0     1     2     3     4
       +-----+-----+-----+-----+-----+
       |  C  |     |     |  A  |  B  |
       +-----+-----+-----+-----+-----+
          ^                 ^
          |                 head (front = A)
          tail will be (3+3)%5 = 1  <- next enqueue lands here

Logical order front->back:  A (idx 3), B (idx 4), C (idx 0)

When NOT to use it. A ring buffer has a fixed capacity. If the number of items can grow without bound, a fixed ring will fill up; you then need either a dynamically resizable buffer or a linked-list queue.

Pitfall. Forgetting the % cap so an index walks off the end of the array — that is an out-of-bounds read or write (undefined behavior in C).

Knowledge check (predict the output). With cap = 4, head = 2, len = 2, at which array index does the next enqueue store its value?

3. Full and empty conditions

Definition. The queue is empty when len == 0 and full when len == cap.

Plain language. Because we store len explicitly, these checks are trivial and unambiguous. (An alternative design stores only head and tail indices without len, which makes full and empty look identical and forces tricks like leaving one slot unused. Tracking len avoids that whole class of bugs.)

When to use which check. Always test full before enqueue and empty before dequeue. Skipping these is the most common queue bug.

Pitfall. Dequeuing from an empty queue reads a slot that holds stale or uninitialized data, and enqueuing into a full queue overwrites a live item. Both must be rejected, not ignored.

empty:  len == 0   -> nothing to dequeue
full:   len == cap -> no room to enqueue
okay:   0 < len < cap -> both operations allowed

Knowledge check (explain in your own words). Why is storing an explicit len field simpler than trying to tell "full" from "empty" using only head and tail?

Syntax notes

A ring-buffer queue needs a struct holding the backing array and the bookkeeping, plus functions for the operations. Here is the annotated shape:

typedef struct {
    int    *buf;   /* heap array of capacity 'cap' */
    size_t  cap;   /* maximum number of items       */
    size_t  len;   /* items currently stored        */
    size_t  head;  /* index of the front item       */
} queue_t;

/* The two key formulas: */
/*   next free slot (tail) = (head + len) % cap   */
/*   new front after deq   = (head + 1)   % cap   */

Notes on choices:

• size_t is the natural type for sizes and array indices in C; it is unsigned and large enough for any object size.
• We store head + len rather than head + tail. Either is valid, but len makes full/empty checks a single comparison.
• The functions return an int status (0 for success, -1 for failure) so callers can detect a full or empty queue instead of crashing.

Lesson

What a queue is

A queue is a first in, first out (FIFO) collection. The first item you add is the first one you remove, like people waiting in line.

Two operations define it:

• enqueue — add an item at the back.
• dequeue — remove an item from the front.

The ring buffer

The classic array-based implementation is a ring buffer (also called a circular buffer). It is a fixed-capacity array with two pieces of state:

• head — the index of the front element.
• len — how many elements the queue currently holds.

All indexing is done modulo the capacity. When an index runs past the end of the array, it wraps back to the start.

This lets the queue reuse storage as items come and go, without shifting elements down on every removal.

Code examples

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int    *buf;
    size_t  cap;
    size_t  len;
    size_t  head;
} queue_t;

/* Create a queue with room for 'cap' integers. Returns 0 on success. */
int q_init(queue_t *q, size_t cap) {
    q->buf = malloc(cap * sizeof *q->buf); /* size from the element, not a literal */
    if (q->buf == NULL) return -1;         /* allocation can fail; report it */
    q->cap  = cap;
    q->len  = 0;
    q->head = 0;
    return 0;
}

/* Add v at the back. Returns 0 on success, -1 if the queue is full. */
int q_enq(queue_t *q, int v) {
    if (q->len == q->cap) return -1;            /* reject when full */
    size_t tail = (q->head + q->len) % q->cap;  /* next free slot, with wrap */
    q->buf[tail] = v;
    q->len++;
    return 0;
}

/* Remove the front item into *out. Returns 0 on success, -1 if empty. */
int q_deq(queue_t *q, int *out) {
    if (q->len == 0) return -1;             /* reject when empty */
    *out = q->buf[q->head];                 /* read the front */
    q->head = (q->head + 1) % q->cap;       /* advance front, with wrap */
    q->len--;
    return 0;
}

/* Release the backing storage. Safe to call once after q_init succeeds. */
void q_free(queue_t *q) {
    free(q->buf);
    q->buf = NULL;   /* avoid a dangling pointer / double free */
    q->cap = q->len = q->head = 0;
}

int main(void) {
    queue_t q;
    if (q_init(&q, 3) != 0) {               /* tiny capacity to show wrap-around */
        fprintf(stderr, "out of memory\n");
        return 1;
    }

    q_enq(&q, 10);
    q_enq(&q, 20);
    q_enq(&q, 30);
    if (q_enq(&q, 40) == -1)                 /* full: this is rejected */
        printf("queue full, 40 rejected\n");

    int x;
    q_deq(&q, &x);                           /* removes 10 */
    printf("dequeued %d\n", x);

    q_enq(&q, 40);                           /* now there is room; wraps to index 0 */

    while (q_deq(&q, &x) == 0)               /* drain the rest in FIFO order */
        printf("dequeued %d\n", x);

    q_free(&q);
    return 0;
}

What it does. It creates a queue that can hold 3 integers, enqueues 10/20/30 (filling it), shows that a 4th enqueue is rejected, dequeues the front (10), then enqueues 40 into the slot freed at the front of the array (demonstrating wrap-around), and finally drains everything in arrival order.

Expected output:

queue full, 40 rejected
dequeued 10
dequeued 20
dequeued 30
dequeued 40

Edge cases. Capacity 0 would make % q->cap a division by zero — a real program should reject a zero capacity in q_init. Dequeuing an empty queue and enqueuing a full one are both handled by returning -1. q_free nulls the pointer so a second accidental q_free does not double-free.

Line by line

We trace the program with cap = 3. The queue starts head = 0, len = 0.

The interesting moment is step 6. The front has moved to index 1, but there is a free slot back at index 0 (vacated in step 5). The formula (head + len) % cap = (1 + 2) % 3 = 0 lands the new value exactly there. This is the wrap-around in action: the buffer is reused without shifting any data. In step 7, dequeue reads starting at head = 1, giving 20, 30, then wraps to index 0 for 40 — the correct FIFO order.

Common mistakes

Mistake 1: dropping the % cap.

/* WRONG: index can run off the end of the array */
size_t tail = q->head + q->len;
q->buf[tail] = v;          /* out-of-bounds write once tail >= cap */

Why it is wrong: once the queue has wrapped, head + len exceeds cap, so you write past the array — undefined behavior, often a silent corruption. Fix: always reduce with % cap:

size_t tail = (q->head + q->len) % q->cap;

Recognize it by crashes or garbage values that appear only after the queue fills and wraps.

Mistake 2: forgetting the full/empty guard.

/* WRONG: no check, overwrites a live item or reads stale data */
int q_enq(queue_t *q, int v) {
    q->buf[(q->head + q->len) % q->cap] = v;
    q->len++;
    return 0;
}

When len == cap, this overwrites the oldest item and pushes len past cap, corrupting all later math. Fix: test if (q->len == q->cap) return -1; first (and the symmetric len == 0 check before dequeue).

Mistake 3: confusing the tail with len. The next slot is (head + len) % cap, not len. Using len directly works only while head is still 0; after any dequeue it points to the wrong place. Always derive the tail from head and len.

Mistake 4: returning the dequeued value through the return type while also using -1 as the status. If queued values can themselves be -1, you cannot tell a real value from an error. Fix: return the value through an out-parameter (int *out) and reserve the return code for success/failure, as the example does.

Debugging tips

Compiler errors.

• error: division by zero is undefined (or a runtime crash) usually means cap was 0. Validate capacity in q_init.
• warning: comparison of integer expressions of different signedness appears if you compare a size_t (unsigned) with a signed int. Keep sizes and indices as size_t.
• implicit declaration of malloc means you forgot #include <stdlib.h>.

Runtime errors.

• A segmentation fault on enqueue/dequeue almost always means an index escaped the array (missing % cap) or q->buf was used before q_init or after q_free.
• Garbage values out of dequeue mean you dequeued past len (missing empty check) and read uninitialized memory.

Logic errors.

• Items come out in the wrong order: check that enqueue uses head + len and dequeue advances head, not the other way around.
• The queue "loses" capacity over time: you are probably incrementing head on enqueue or len on dequeue by mistake.

Concrete steps. Add a debug printer that prints head, len, and the array, and call it after every operation. Run under a memory checker — gcc -fsanitize=address,undefined -g queue.c && ./a.out will pinpoint the exact out-of-bounds access or use-after-free. Questions to ask: Did I check full/empty? Is every index reduced % cap? Is head advanced only on dequeue and len adjusted in both directions?

Memory safety

This is a hand-managed C data structure, so the usual heap concerns apply directly:

• Bounds. Every array access must use an index reduced % cap. The two formulas (head + len) % cap and (head + 1) % cap are the only correct ways to compute slots; any raw head + len is a potential out-of-bounds access. Run the example under -fsanitize=address to confirm no access escapes buf[0..cap-1].
• Initialization. q_init sets len and head before any operation. Never use a queue_t whose buf was not successfully allocated — check q_init's return value.
• Allocation failure. malloc can return NULL; the code checks it and reports -1 rather than dereferencing a null pointer.
• Lifetimes / use-after-free. After q_free, buf is set to NULL and the fields zeroed, so an accidental later use fails loudly instead of touching freed memory, and a second q_free becomes a harmless free(NULL).
• Integer overflow. cap * sizeof *q->buf could overflow for an enormous cap. For untrusted sizes, validate cap against a sane maximum before multiplying.
• No reads of stale slots. Because dequeue is rejected when len == 0, the code never returns a slot that was never written or was already consumed.

General robustness habit: treat the full and empty checks as non-negotiable preconditions, and let the sanitizer prove your index math during development.

Real-world uses

Concrete uses.

• Operating-system and device drivers. Network interface cards and serial/UART drivers use ring buffers to hold incoming bytes/packets between the hardware interrupt and the code that processes them, precisely because enqueue/dequeue are O(1) and need no allocation.
• Audio/DSP. A ring buffer decouples the audio callback (consumer) from the code generating samples (producer), so neither stalls the other.
• Logging and telemetry. A fixed ring keeps the most recent N events with bounded memory; old entries are naturally overwritten or dequeued.
• Algorithms. Breadth-first search over a graph uses a FIFO queue to visit nodes level by level.

Professional best-practice habits.

Beginner rules:

• Always check full before enqueue and empty before dequeue.
• Always reduce indices with % cap.
• Always pair q_init with q_free; check q_init's return value.
• Use sizeof *ptr (not a hard-coded type) in malloc.

Advanced rules:

• Validate cap > 0 and guard against cap * sizeof overflow for untrusted input.
• Keep the API status-based (int return) so callers handle full/empty gracefully instead of crashing.
• For producer/consumer use across threads, a single-producer/single-consumer ring can be made lock-free, but that requires memory-ordering care beyond this lesson — start with a mutex.
• Document whether the queue is fixed-capacity or growable so callers know whether enqueue can fail.

Practice tasks

Beginner 1 — Add a peek. Write int q_peek(const queue_t *q, int *out) that copies the front item into *out without removing it. Return 0 on success, -1 if empty. Requirements: do not modify head or len. Hint: the front lives at q->buf[q->head]. Concepts: front index, empty check.

Beginner 2 — Report fullness. Write helpers int q_is_empty(const queue_t *q) and int q_is_full(const queue_t *q) returning 1/0. Then print the queue's length and whether it is full after each enqueue in main. Concepts: len, cap, boundary conditions.

Intermediate 1 — Trace and verify wrap-around. Using cap = 4, enqueue 1,2,3,4; dequeue twice; enqueue 5,6. Print the array contents and head/len after each step. Expected: the values 5 and 6 should land at indices 0 and 1 (wrapped). Requirements: add a debug printer that shows the raw array and the logical front-to-back order. Concepts: (head+len)%cap, modular wrap.

Intermediate 2 — Generic element type. Change the queue to store void * (or a fixed-size struct) instead of int, keeping the same ring logic. Enqueue a few heap-allocated strings and dequeue/print them in order, freeing each. Requirements: no leaks (verify with a sanitizer). Hint: only the element type and sizeof change; the index math is identical. Concepts: element-size abstraction, ownership, cleanup.

Challenge — Growable queue. Add int q_enq_grow(queue_t *q, int v) that, when the buffer is full, allocates a new buffer of 2 * cap, copies the existing items in logical (FIFO) order starting at index 0, updates head = 0, cap, and frees the old buffer; then enqueues v. Requirements: preserve FIFO order across the resize; handle malloc failure without losing the existing data; no leaks. Hint: copy item i from (head + i) % cap for i in 0..len-1. Constraints: keep all operations correct after several grows. Concepts: reallocation, copying a wrapped ring into a linear order, error handling.

Summary

A queue is a FIFO collection: enqueue adds at the back, dequeue removes from the front, preserving arrival order. The efficient array implementation is a ring buffer — a fixed-capacity heap array plus head (front index) and len (count). The two formulas to memorize are: the next free slot (tail) is (head + len) % cap, and the new front after a dequeue is (head + 1) % cap. The % cap is what makes indices wrap from the end back to the start so storage is reused with no data shifting, giving O(1) enqueue/dequeue.

The critical rules: check full (len == cap) before enqueue and empty (len == 0) before dequeue, and reduce every index % cap. The most common mistakes are dropping the % cap (out-of-bounds access), skipping the full/empty guards (corruption or stale reads), and confusing the tail position with len. In C, also check malloc for NULL, pair q_init with q_free, null the pointer after freeing, and lean on -fsanitize=address,undefined to prove your index math is safe. Remember: front out first, back in last, indices wrap.

Practice with these exercises

• Ring-buffer index
• Queue length in a ring