Search tools and guides ⌘K
I · The linear primitives

Stack

Last in, first out.

1946 / 1955 · Alan Turing implicit; named by Klaus Samelson & Friedrich Bauer
The story

Turing used a "reserve" of return addresses in his 1946 ACE design. Samelson and Bauer named it Keller ("cellar") in 1955, to manage operator precedence in compiler design, what every modern parser still does.

How it works

Push and pop at the same end. Implementable as a dynamic array (cheap) or linked list (rare). The OS thread stack is just a hardware-managed instance.

Where it lives

Every function call you've ever made. JVM operand stack. Undo history. DFS. Expression parsing. Backtracking solvers.

The key insight

A program with deep recursion is a stack overflow waiting to happen. Tail-call optimisation eliminates the stack frame for tail-recursive calls. Required by Scheme, optional in most languages.

More in The linear primitives
Array A row of equal-sized boxes. Dynamic array (vector) An array that grows itself. Linked list A chain you can splice. Queue First in, first out. Deque Both ends, equally. Ring buffer A fixed-size queue that never allocates.
Across the cabinet
II B-tree / B+ tree The shape of a database index. II Heap (binary heap) A priority queue you can grep. II Skip list Probabilistic balance, beautifully. II Trie (prefix tree) A tree you walk one character at a time. II Segment tree Range queries in logarithmic time. II Fenwick tree (BIT) Prefix sums, with constant tweaks. II Treap BST and heap, secretly the same tree. II Splay tree No metadata — and surprising amortised guarantees.
← All data structures