Stacks & Queues

A stack (last-in, first-out) and a queue (first-in, first-out) are both commonly built on top of a linked list:

typedef struct Node {
    int value;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
} Stack;

void push(Stack *s, int value) {
    Node *node = malloc(sizeof(Node));
    node->value = value;
    node->next = s->top;
    s->top = node;
}

int pop(Stack *s) {
    Node *top = s->top;
    int value = top->value;
    s->top = top->next;
    free(top);
    return value;
}

A stack matches how function calls themselves work (the "call stack" from Recursion) — the most recently called function is the first to return. A queue matches a real-world line: whoever joined first is served first.