Treiber stack (1986) is the simplest lock-free data structure, a singly-linked stack where push and pop both use compare-and-swap on the head pointer, retrying if contended. It demonstrates the CAS-retry pattern that appears everywhere in lock-free programming.

It requires a memory reclamation scheme (hazard pointers or RCU) to safely handle the ABA problem when freed nodes are reused.

#include <stdio.h>
#include <stdlib.h>
#include <stdatomic.h>
 
struct node { int val; atomic_intptr_t next; };
atomic_intptr_t head = 0;
 
void push(int val) {
    struct node* n = malloc(sizeof(*n));
    n->val = val;
    struct node* h;
    do {
        h = (struct node*)atomic_load(&head);
        atomic_store(&n->next, (intptr_t)h);
    } while (!atomic_compare_exchange_weak(&head, (void*)&h, n));
}
 
int pop() {
    struct node* h;
    do {
        h = (struct node*)atomic_load(&head);
        if (!h) return -1;
    } while (!atomic_compare_exchange_weak(&head, &h, atomic_load(&h->next)));
    int v = h->val;
    free(h);
    return v;
}