Stacks

How does an editor know what to undo next? It keeps every old value on a stack. Watch the last one saved come back first.

⋯10void push(struct stack *s, int v)11{12    if (s->top == CAP)13        return;14    s->items[s->top] = v;15    s->top = s->top + 1;16}17 18int pop(struct stack *s)19{20    s->top = s->top - 1;21    return s->items[s->top];22}⋯29int main(void)30{31    struct stack history = { .top = 0 };32    int value = 10;33    push(&history, value);34    value = 25;35    push(&history, value);36    value = 40;37    push(&history, value);38    value = 55;39    printf("now %d, last saved %d\n", value, peek(&history));40    while (history.top > 0) {41        value = pop(&history);42        printf("undo: %d\n", value);43    }44    return 0;45}

Last in, first out

Each time the editor is about to change a value, it saves the old one. When you press undo, it should bring back the most recent one saved, then the one before, and so on: the last saved is the first restored. A structure that hands things back in reverse order like that is a stack, named after a stack of plates, where you take from the top what you last put there. Last in, first out.

A stack has four operations:

• push: put an item on top.
• pop: take the top item off and return it.
• peek: read the top item without taking it.
• is empty: are there no items at all?

Nothing else is allowed: no reading the middle, no adding at the bottom. That restriction is what makes a stack simple and fast.

The code and its cost

An array and a top index

#define CAP 16

struct stack {
    int items[CAP];
    int top;
};

The items live in an array, the bottom one in items[0]. top is not the index of the top item: it is the number of items, so it is also the index of the next free cell. An empty stack has top 0; the top item, when there is one, is items[top - 1]. sizeof (struct stack) is 68 bytes: 64 for the array, 4 for top. In the clip, history sits at 0x7fa0, so items[i] is at 0x7fa0 + 4i and top at 0x7fe0.

void push(struct stack *s, int v)
{
    if (s->top == CAP)
        return;
    s->items[s->top] = v;
    s->top = s->top + 1;
}

int pop(struct stack *s)
{
    s->top = s->top - 1;
    return s->items[s->top];
}

int peek(const struct stack *s)
{
    return s->items[s->top - 1];
}

push writes into the next free cell, then moves top up. pop moves top down, then reads the cell top now points at. The functions take the stack’s address, &history, so that they change main’s stack and not a copy of it.

pop does not erase anything. After the three undos in the clip, items[0], items[1] and items[2] still hold 10, 25 and 40. They are simply above top, so they are no longer on the stack, and the next push will write over them.

Full and empty

A stack in an array has room for CAP items. A push on a full stack is an overflow; this push refuses it (lines 12 and 13) and the value is lost, which a real program would report. A pop or a peek on an empty stack is an underflow. These two functions do not check: they rely on the caller, and main only pops while history.top > 0 (line 40). The worked example shows what happens otherwise.

The same stack on nodes

The array is not the only way. Built on the nodes of Singly linked lists, the top of the stack is the head of the list: push is push_front, and pop removes the head node.

struct node *pop(struct node *top, int *v)
{
    struct node *next = top->next;
    *v = top->key;
    free(top);
    return next;
}

pop must give back two things, the key and the new top. It returns the new top, and writes the key through the pointer v into a variable of the caller’s.

1#include <stdio.h>2#include <stdlib.h>3 4struct node {5    int key;6    struct node *next;7};8 9struct node *push(struct node *top, int v)10{11    struct node *n = malloc(sizeof *n);12    if (n == NULL)13        exit(1);14    n->key = v;15    n->next = top;16    return n;17}18 19struct node *pop(struct node *top, int *v)20{21    struct node *next = top->next;22    *v = top->key;23    free(top);24    return next;25}26 27int main(void)28{29    struct node *top = NULL;30    int v;31    top = push(top, 10);32    top = push(top, 25);33    top = push(top, 40);34    while (top != NULL) {35        top = pop(top, &v);36        printf("%d ", v);37    }38    printf("\n");39    return 0;40}

The linked stack has no fixed capacity: it can grow until malloc fails. It pays with one malloc per push and one free per pop, and a next pointer in every node.

What it costs

Every operation is a fixed handful of steps, in both versions. Counted for the array stack: one comparison and two writes for push, a write and a read for pop, one read for peek. The linked stack’s counts differ (push calls malloc, checks it and writes two fields; pop reads two fields, writes v and calls free), but they are just as fixed. None of them looks at more than the top, so a stack of a million items is as fast as a stack of three.

Memory is another matter. The array stack takes its 68 bytes whatever it holds. The linked one takes one block per item, 32 bytes each on this platform with the C library’s spacing, so three items take 96 bytes.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic undo.c -o undo
./undo

It prints now 55, last saved 40, then undo: 40, undo: 25 and undo: 10. linked-stack.c builds the same way and prints 40 25 10.

Worked example

By hand. On an empty array stack: push 3, push 7, pop, push 2, push 9, pop, pop.

The pops return 7, 9 and 2. The stack ends holding only 3, with top 1, while items[1] still holds 2 and items[2] still holds 9: the push of 2 wrote over the 7 that had been popped.

In the clip. After line 37 runs, top is 3, and peek returns 40. After all three pops, items[0] still holds 10. And for a stack with push 1, 2, 3 and then two pops, the top item is 1, and top is 1 too.

Full. With CAP 16, sixteen pushes in a row fill items[0] to items[15] and make top 16; the seventeenth is refused, and the stack is unchanged.

Empty. Here is a pop on an empty stack:

int main(void)
{
    struct stack history = { .top = 0 };
    int value = pop(&history);
    printf("undo: %d\n", value);
    return 0;
}

pop makes top −1 and reads items[-1], an int just before the array, which is not part of it. C does not stop this. The program prints whatever those bytes hold. Built with -fsanitize=undefined, it reports the bad index, then carries on and prints whatever it read. The report:

underflow.c:13:20: runtime error: index -1 out of bounds for type 'int [16]'

The fix belongs to the caller: check that top is more than 0 before popping, as main does on line 40.

Where it’s used

The call stack. When a function calls another, the new frame goes on top of the caller’s, and when it returns, its frame comes off first. The frames of The call stack (1.3) are a stack in this exact sense: the code the compiler generates pushes a frame at each call and pops it at the return.

Undo. Editors keep the changes you make on a stack and undo the most recent first; many keep a second stack for redo.

The back button. A browser pushes each page you leave; back pops the last one.

Brackets and expressions. Compilers and calculators check that brackets match and work out expressions with a stack: Matching brackets (8.2), Infix to postfix (8.3) and Evaluating postfix (8.4). Depth-first search (19.3) explores a maze with one.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.