Stacks and queues

Why this matters

Stacks and queues are less data structures than disciplines: rules about which element you may take out next. A stack hands back the most recently added element; a queue hands back the oldest. These two rules turn up everywhere. The call stack that holds your function frames is a stack. Undo is a stack. Parsers use stacks to match brackets and evaluate expressions. Keyboard input, network packets, print jobs and messages between threads wait in queues. Both are easy to build from what you already have, and the ring buffer you will write for the queue is one of the most widely used structures in systems programming: it sits inside every terminal driver, audio pipeline and network card.

Stacks: last in, first out

A stack supports push (add on top), pop (remove from the top), and often peek (look at the top without removing it). Pop on an empty stack is underflow, an error the code must report.

   push 1    push 2    push 3    pop -> 3   pop -> 2
                         [3]
               [2]       [2]       [2]
     [1]       [1]       [1]       [1]        [1]

A dynamic array is a perfect stack: the top is the end of the array, so push and pop are O(1) and nothing ever shifts.

typedef struct {
    int *data;
    size_t len, cap;
} Stack;

int stack_push(Stack *s, int value)
{
    if (s->len == s->cap) {
        size_t new_cap = s->cap ? s->cap * 2 : 8;
        int *tmp = realloc(s->data, new_cap * sizeof *tmp);
        if (tmp == NULL)
            return -1;
        s->data = tmp;
        s->cap = new_cap;
    }
    s->data[s->len++] = value;
    return 0;
}

int stack_pop(Stack *s, int *out)
{
    if (s->len == 0)
        return -1;          /* underflow */
    *out = s->data[--s->len];
    return 0;
}

Pushing 1, 2, 3 and then popping until empty prints pop 3, pop 2, pop 1. Notice s->data[--s->len]: decrement first, then index, because len is one past the top element. A linked list with push_front and a "pop front" also makes a fine stack, with one allocation per element.

A classic use: matching brackets

To check that f(a[1], {b}) is properly nested, scan left to right. Push every opener. At every closer, the most recent unclosed opener (the top of the stack) must be its partner: pop it. A mismatch, or a closer when the stack is empty, is an error; openers left at the end are unclosed.

  input:   f  (  a  [  1  ]  ,     {  b  }  )
  stack:      (     ([    (        ({    (
                       pop [          pop {  pop (   -> empty at end: ok

Compilers, JSON parsers and your text editor's bracket highlighting all use this idea.

Queues: first in, first out

A queue supports enqueue (add at the back) and dequeue (remove from the front). Using a plain array with the front at index 0 would make dequeue O(n), because everything shifts left. Two good implementations avoid that:

1. A linked list with a tail pointer: enqueue appends at the tail, dequeue removes the head, both O(1). Unbounded, but one malloc per element.
2. A ring buffer (circular buffer): a fixed array where the front index moves forward and wraps around. No allocation at all after setup, which is why low-level code loves it.

The ring buffer

Keep an array, the index of the oldest element (head), and how many elements are stored (count). The next free slot is head + count, wrapped around the end of the array:

#define QCAP 4

typedef struct {
    int items[QCAP];
    size_t head;    /* index of the oldest item */
    size_t count;   /* number of items stored */
} Queue;

int queue_push(Queue *q, int value)
{
    if (q->count == QCAP)
        return -1;                              /* full */
    q->items[(q->head + q->count) % QCAP] = value;
    q->count++;
    return 0;
}

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

Trace it with capacity 4: push 1 to 5, pop twice, push 6 and 7, then pop everything.

  push 1..4     [1][2][3][4]   head=0 count=4    push 5 -> full
  pop, pop      [.][.][3][4]   head=2 count=2    (returned 1, 2)
  push 6        [6][.][3][4]   head=2 count=3    slot (2+2)%4 = 0
  push 7        [6][7][3][4]   head=2 count=4    slot (2+3)%4 = 1
  pop x4        returns 3, 4, 6, 7; head goes 3, 0, 1, 2

The real program prints:

queue full, 5 rejected
dequeue 1
dequeue 2
dequeue 3 (head now 3)
dequeue 4 (head now 0)
dequeue 6 (head now 1)
dequeue 7 (head now 2)

The elements never move; only head chases around the circle. When the capacity is a power of two, % QCAP can be & (QCAP - 1) (from the bit tricks lesson), which is why real ring buffers are usually sized 256, 4096 and so on.

Note: a ring buffer can also overwrite the oldest item when full instead of rejecting the new one. Logging systems and the kernel's dmesg buffer do exactly that: you keep the most recent N messages.

Choosing an implementation

Common mistakes

• Not checking for underflow. Popping an empty array-based stack reads data[-1] (len - 1 wraps to a huge size_t, so in fact far outside the block): undefined behavior.
• Off-by-one on the top. len is the count, so the top element is data[len - 1].
• Forgetting to wrap. head++ without the modulo runs off the end of the array after QCAP pops. AddressSanitizer reports a stack-buffer-overflow or global-buffer-overflow.
• Using & (N - 1) when N is not a power of two. It silently computes the wrong slot.
• Confusing full and empty in a ring buffer that has only two indexes and no count.

Recap

• Stack: push and pop at the same end (LIFO). A dynamic array's end is an O(1) stack.
• Queue: add at the back, remove from the front (FIFO). Use a linked list with a tail pointer or a ring buffer, never an array that shifts.
• A ring buffer stores head and count; the free slot is (head + count) % N and pop advances head modulo N.
• Always report underflow (empty) and, for bounded structures, overflow (full).

Going further: extend the ring buffer to grow: when full, allocate a block twice the size and copy the elements in queue order (two memcpy calls, because the contents may wrap). Then read about how the Linux kernel's kfifo uses free-running unsigned indexes and power-of-two masks.