📈 Algorithms & Complexity

Stacks & queues: LIFO meets FIFO

⏱ 14 min · free interactive lesson · quizzes, visualizations & a real compiler

Arrays let you touch any element any time. Sometimes that freedom is exactly wrong — you want discipline. A stack only lets you touch the newest item (that's the "last in, first out" — LIFO — of the title); a queue only the oldest ("first in, first out" — FIFO). These two constraints turn out to run half of computing: your function calls, your undo history, your print jobs, the part of the operating system that decides which program runs next.

The stack: Last In, First Out

Picture a stack of plates. You can push a plate on top, pop the top one off, or peek at it. The one you get back is always the most recently added — LIFO. An array plus one integer is all it takes:

#include <stdio.h>
#include <stdbool.h>

#define CAP 16

typedef struct {
    int data[CAP];
    int top;              /* count; index of next free slot */
} Stack;

void st_init(Stack *s) { s->top = 0; }

bool st_push(Stack *s, int v) {
    if (s->top == CAP) return false;      /* full: overflow  */
    s->data[s->top++] = v;
    return true;
}

bool st_pop(Stack *s, int *out) {
    if (s->top == 0) return false;        /* empty: underflow */
    *out = s->data[--s->top];
    return true;
}

bool st_peek(const Stack *s, int *out) {
    if (s->top == 0) return false;
    *out = s->data[s->top - 1];           /* look, don't take */
    return true;
}

int main(void) {
    Stack s; st_init(&s);
    st_push(&s, 10); st_push(&s, 20); st_push(&s, 30);
    int v;
    while (st_pop(&s, &v)) printf("popped %d\n", v);
    return 0;
}

$ gcc stack.c -o stack && ./stack
popped 30
popped 20
popped 10
# pushed 10,20,30 — got them back REVERSED. That's LIFO.

Note the elegant symmetry: push is data[top++] (store, then step up), pop is data[--top] (step down, then read). top always equals the number of elements, and every operation is a single index tweak — O(1).

Stacks are everywhere (you've been using one all along)

• The call stack — last function called is first to return. Recursion IS a stack; last lesson's trace was push/pop in disguise.
• Undo (Ctrl+Z) — the most recent change reverts first.
• The back button — most recent page first.
• Matched brackets — the classic interview problem, worked below.

Why does a stack solve bracket matching? Because a closing bracket must match the most recently opened, not-yet-closed one — "most recent first" is literally the stack's job description. Step through checking "([])":

▶ This spot has an interactive trace widget — open the interactive lesson to play with it.

The queue: First In, First Out

A queue is the line at the bakery: enqueue at the tail, dequeue from the head, and the first one in is the first one out — FIFO. Naive array version: dequeue from index 0 and shift everything left — O(n), yuck. The classy fix is the circular buffer: let head and tail chase each other around a fixed array, wrapping with modulo:

#include <stdio.h>
#include <stdbool.h>

#define CAP 8

typedef struct {
    int data[CAP];
    int head;    /* index of the oldest element        */
    int tail;    /* index where the next enqueue lands */
    int count;
} Queue;

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

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

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

int main(void) {
    Queue q; q_init(&q);
    for (int i = 1; i <= 5; i++) enqueue(&q, i * 10);
    int v;
    dequeue(&q, &v); printf("first out: %d\n", v);
    dequeue(&q, &v); printf("then     : %d\n", v);
    enqueue(&q, 60); enqueue(&q, 70); enqueue(&q, 80);
    enqueue(&q, 90);      /* tail wraps: 7 -> 0 ! */
    while (dequeue(&q, &v)) printf("%d ", v);
    printf("\n");
    return 0;
}

$ gcc queue.c -o queue && ./queue
first out: 10
then     : 20
30 40 50 60 70 80 90
# in: 10..90, out: 10..90 — same order. That's FIFO.

Here's the buffer from that program at the moment right after enqueue(90) — the tail ran off the end of the array and wrapped around to slot 0:

▶ This spot has an interactive memgrid widget — open the interactive lesson to play with it.

Scoreboard & variants

Both can also be built on linked lists (push/pop at the list head; enqueue at a tail pointer): still O(1) per operation and never "full", at the cost of a heap allocation per element and worse cache behavior. Array-backed wins for a known size bound; linked wins for unbounded growth. Circular buffers in particular are the backbone of real systems — keyboard input, audio streaming, network packet rings.

▶ This spot has an interactive editor widget — open the interactive lesson to play with it.

Stacks and queues organize data by when it arrived — but to find things by what they are, in O(1), you need one more trick: hashing.