A Treiber stack (R.K. Treiber, 1986) is the simplest lock-free data structure built entirely on compare-and-swap: a singly-linked stack where push and pop both work by CASing the head pointer, retrying if another thread got there first. It's usually the first lock-free structure taught, since it's a direct, minimal demonstration of the CAS-retry-loop pattern that shows up everywhere in lock-free programming, including in the more complex Michael-Scott queue.

struct node {
    void                   *data;
    _Atomic(struct node *)  next;
};
 
_Atomic(struct node *) head = NULL;
 
void push(void *data) {
    struct node *n = malloc(sizeof *n);
    n->data = data;
    struct node *old_head;
    do {
        old_head = atomic_load(&head);
        n->next = old_head;
    } while (!atomic_compare_exchange_weak(&head, &old_head, n));
}
 
void *pop(void) {
    struct node *old_head;
    struct node *new_head;
    do {
        old_head = atomic_load(&head);
        if (old_head == NULL) return NULL;        // empty stack
        new_head = atomic_load(&old_head->next);
    } while (!atomic_compare_exchange_weak(&head, &old_head, new_head));
    void *data = old_head->data;
    free(old_head);   // unsafe without reclamation - see below
    return data;
}

A stack only ever needs to touch one end, the head, so both push and pop are a single CAS loop with no helping mechanism required. Compare this to the Michael-Scott queue, where enqueue and dequeue touch head and tail separately and sometimes need to help a stalled thread finish updating tail. The Treiber stack's simplicity is exactly why it's the standard first example: it shows the CAS-retry pattern with none of the extra bookkeeping a two-ended structure needs.

The free(old_head) in pop has the identical hazard as in the Michael-Scott queue: if the freed node is reused and pushed again before every concurrent pop has finished dereferencing it, a stale CAS can succeed against a coincidentally-matching address (the ABA problem). Production implementations need hazard pointers or epoch-based reclamation rather than an immediate free, exactly as with any other CAS-based lock-free structure.