Stacks & Queues — Algorithms & DS

When you call a function in C, the CPU doesn't just jump to the function — it pushes a return address onto a stack. When the function returns, it pops that address and jumps back. You've been using a stack since your first main(). The pattern is everywhere, and knowing when to use which access order is half of algorithm design.

Stack — last in, first out

A stack has one open end: the top. You push onto it, and you pop from it. Whatever you pushed last comes out first. That's LIFO.

c

#define CAP 256

typedef struct {
    int data[CAP];
    int top;          // index of the top element; -1 = empty
} Stack;

void stack_init(Stack *s) { s->top = -1; }

int stack_push(Stack *s, int v) {
    if (s->top == CAP - 1) return 0;  // overflow
    s->data[++s->top] = v;
    return 1;
}

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

int stack_peek(const Stack *s) { return s->data[s->top]; }
int stack_empty(const Stack *s) { return s->top == -1; }
          

Push and pop are O(1) — just increment or decrement top and read/write that index. The array is cache-friendly: the top element is always near the previously accessed element. This is as fast as it gets.

⚠️

Stack overflow and underflow are silent in C. The version above returns 0 on failure, but many textbook examples skip the check entirely and write past the array boundary. In production code, always guard both edges.

Where stacks appear

The call stack. Every function call pushes a frame (return address + locals); every return pops it. Infinite recursion = stack overflow.
Undo/redo. Each action pushes to an undo stack. Undo pops and pushes to redo.
Expression evaluation. Compilers use stacks to parse and evaluate arithmetic expressions with the correct operator precedence.
Iterative DFS. Replace the recursion stack implicitly used in recursive DFS with an explicit stack to avoid stack overflow on deep graphs.
Matching delimiters. Push open brackets; on a close bracket, pop and check if it matches.

Queue — first in, first out

A queue has two open ends: you enqueue at the back and dequeue from the front. Whatever arrived first leaves first. That's FIFO.

The naive array queue has a problem: each dequeue moves head forward, consuming the slot permanently. After N dequeues you've "used up" all N slots at the front, even if they're empty — and you can't enqueue anymore even though the array isn't full.

The fix is a circular buffer: wrap the index back to 0 when it hits the capacity. Slots at the front become available again after dequeue.

c

typedef struct {
    int data[CAP];
    int head;   // index of front element
    int tail;   // index where the NEXT item will be written
    int count;  // current number of elements
} Queue;

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

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

int dequeue(Queue *q, int *out) {
    if (!q->count) return 0;             // empty
    *out = q->data[q->head];
    q->head = (q->head + 1) % CAP;     // wrap around
    q->count--;
    return 1;
}
          

💡

How the modulo wrap works: if tail is at index 255 and capacity is 256, (255 + 1) % 256 == 0 — it wraps back to the start. The count field distinguishes "full" from "empty" when head and tail point to the same index. Without it, you can't tell if a coinciding head/tail means 0 items or 256 items.

Where queues appear

BFS. Enqueue the start node; on each step, dequeue and enqueue unvisited neighbors. The FIFO order is what guarantees the shortest path in unweighted graphs.
OS scheduling. The run queue holding processes waiting for CPU time.
Producer/consumer buffers. One thread writes to the tail, another reads from the head. Add a mutex and you have a thread-safe message queue.
Network packet buffers. Packets arrive in order and are processed in order.

Choosing the backing structure

Both stack and queue can be backed by an array or a linked list. The tradeoff is the same as always: arrays are cache-friendly and need a fixed capacity (or a resize strategy); linked lists are dynamic but scatter nodes across the heap. For a stack, push/pop at the linked list's head is O(1) with no capacity limit. For a queue, you need a pointer to both ends — maintain a tail pointer and push/pop happen at opposite ends.

The visualization

The viz shows both structures in action. Watch how the stack's top index moves, and how the queue's head and tail indices wrap around the circular buffer.

one-line takeaway

A stack reverses order; a queue preserves it — pick by whether the last thing in or the first thing in should come out next.