Sequences Last in, first out

Stack

The most recent thing comes back first.

You shorten a heading, decide the old one was better, and press Undo. You read an error, and in a JavaScript, Go, or Rust stack trace the function that threw sits on top, with its callers underneath. Each time, the most recent thing comes back first. That is the whole rule, and it has a name.

TypeScriptGoOne rule. Several places you already use it.

01 / The idea

Keep the order you need. Make it hard to get it wrong.

A stack is a collection with one rule: whatever went in last comes out first. Last in, first out, or LIFO. Add to the top, take from the top, and everything underneath waits its turn.

You rely on that rule more than you notice. Undo brings back your last edit before the one before it. Your editor knows which bracket to close, because the last one opened is the first one that must close. And a stack trace is a literal stack: JavaScript, Go, and Rust print the function that threw on top, whoever called it underneath, all the way down to where your program started. Python prints the same stack the other way up.

You have built one, too, without calling it that. An array already adds and removes at one end with push and pop. Giving that a name earns its place when several parts of your code share the pile and none of them should reach into the middle of it.

02 / Name the rule

Push adds. Peek looks. Pop takes.

Make a guess before you click: if first went in before second, which one does Pop hand back? Then try Peek. It shows you the same top value and leaves the stack exactly as it was.

The one thing that must stay true after every operation is the invariant: the top is the most recent push that has not been popped or cleared. An empty stack has no top. That is an ordinary state to handle, not automatically an error.

One end. Three operations.

What comes back next?

The stack

2 items

Shown top first; the implementation keeps its top at the array’s end.

Top · next outsecond
Belowfirst

Now push an empty string. The stack has an item in it, even though that item has no characters. “Nothing is here” and “what is here happens to be empty” are different answers, and Undo is going to need to tell them apart.

The rule and the storage are different thingsInterface vs. representation

A stack is a promise about which operations exist and what order they hand things back in. An array, a Go slice, a Rust Vec, or a chain of linked nodes can all keep that promise.

Here the top is the end of the underlying array. The diagram draws it at the top of a column so the next thing out is easy to spot. Same order, two ways of looking at it.

03 / Follow one operation

An editor needs somewhere to put the version you leave.

Most Undo buttons you have pressed work roughly like this. Keep the text you are looking at as the present, and a stack of earlier versions as Past. When you commit an edit, push the old present onto Past. Undo pops Past and makes that the present again.

Now add Redo. The version you leave when you Undo goes onto a second stack, Future. Undo twice, and the last thing pushed onto Future is exactly the one you want back first. Two stacks, one rule.

Playback controls

Stack

Undo has a memory.

01/ 05

The setup

Three versions of the same heading.

v3 is open. Undo should bring back v2 first.

Reduced motion: choose a scene to see its completed state.

Read this scene

v3 is open. Undo should bring back v2 first.

Completed history. The diagram and table show the same result. Illustrated heading: “Hello, curious world.”.

Past · bottom to top: Hello. → Hello, world.
Present: Hello, curious world.
Future · bottom to top: Empty

Try the example by reading

Undo keeps the current version in Future and restores the top of Past. Redo performs the reverse. A new edit keeps the previous version in Past and clears Future.

Two stacks, one present

A tiny editor with a memory.

Make a guess before clicking Undo. Then edit after undoing, and watch what happens to Future.

Past

2 items

Undo takes from this top.

Top · next outHello, world.
BelowHello.

Present

The committed version

Hello, curious world.

Future

0 items

Redo takes from this top.

Empty. Nothing to take yet.

Try Undo. Where should the current version go?

Follow the last few moves

Started with “Hello.”
Committed “Hello, world.”
Committed “Hello, curious world.”

Runs the TypeScript history shown below. Go and Rust are checked against the same cases. This is application state, not a memory-address diagram.

Watch restarts when you return. Step through keeps your selected step. Try it starts a fresh editor each time you open it.

The stacks give you the order. The editor decides the policy: a new edit after Undo throws the old future away. Committing the same text again changes nothing and keeps it. Those are choices this editor made, not laws that come with a stack.

04 / Read the shape

The same moves, expressed two ways.

Start with the small stack, then switch to In the wild for the two-stack history. TypeScript and Go run the same sequence of edits. The problem stays put while each language says it its own way.

Notice how little each language needs from us. TypeScript arrays already have push and pop. Go uses append and a reslice. The wrapper’s whole job is to hide everything else.

Read in

Compare with

A small stack with a clear empty result. The wrapper names the rule; the array or slice does the storing.

TypeScriptReading

history.ts

export type StackResult<T> = { found: true; value: T } | { found: false };

export function createStack<T>() {
	const items: T[] = [];
	return {
		get size() {
			return items.length;
		},
		push(value: T) {
			items.push(value);
		},
		pop(): StackResult<T> {
			if (items.length === 0) return { found: false };
			return { found: true, value: items.pop() as T };
		},
		peek(): StackResult<T> {
			if (items.length === 0) return { found: false };
			return { found: true, value: items[items.length - 1] };
		},
		clear() {
			items.length = 0;
		},
		values: () => [...items]
	};
}

GoAlongside

history.go

type Stack[T any] struct{ items []T }

func (s *Stack[T]) Len() int     { return len(s.items) }
func (s *Stack[T]) Push(value T) { s.items = append(s.items, value) }
func (s *Stack[T]) Pop() (T, bool) {
	var zero T
	if len(s.items) == 0 {
		return zero, false
	}
	i := len(s.items) - 1
	value := s.items[i]
	s.items[i] = zero // release references held by the removed slot
	s.items = s.items[:i]
	return value, true
}
func (s *Stack[T]) Peek() (T, bool) {
	if len(s.items) == 0 {
		var zero T
		return zero, false
	}
	return s.items[len(s.items)-1], true
}
func (s *Stack[T]) Clear()      { clear(s.items); s.items = s.items[:0] }
func (s *Stack[T]) Values() []T { return append([]T{}, s.items...) }

Reading the TypeScriptGenerics, a tagged result, and copies

T lets the stack hold a chosen type. StackResult<T> uses found to separate a value from absence. That remains unambiguous even when undefined itself is a valid stored value.

The length check proves Pop has something before the type assertion, which is a promise to the compiler rather than a runtime check. History stores strings, and each method returns whether it changed anything.

values() copies the outer array for inspection. Objects inside it would still be shared. With strings, editing the copy cannot rewrite the history.

Reading the GoZero values, ok, and the backing array

(T, bool) carries the same distinction: the boolean tells us whether an item existed. An empty string or a nil pointer can still be a successfully popped value.

Reslicing shortens the slice you see but keeps its backing array. So Pop clears the removed slot first, or that hidden tail would keep the value alive. That releases a reference and nothing more; closing a file is still your job. The Go team’s explanation of slice deletion shows why the invisible tail matters.

Pointer receivers let the methods change the stack in place. Values returns a separate slice. The sample uses the clear builtin, added in Go 1.21, and its module declares Go 1.23.

05 / Try a decision

The interesting moment is the edit after Undo.

Checking one push and one pop is easy. The moment that decides what Redo means is the edit you make right after Undo. Follow where each version goes before you answer.

06 / Follow the cost

Count the operation you are actually asking for.

Here is every operation at a glance, with n versions across both stacks. The stack operations themselves are constant. The row worth a second look is Commit.

Stack and undo history: time and extra space per operation
Operation	Time	Extra space	What it assumes
Push	`O(1) amortized`	`O(1) amortized`	Array-backed. The rare push that fills the array copies it once, and that still averages out.
Peek	`O(1)`	`O(1)`	Reads the top and leaves it where it is.
Pop	`O(1)`	`O(1)`	Takes the top. Go also clears the slot so the old value can be collected.
Undo or Redo	`O(1) amortized`	`O(1) amortized`	One pop from one stack, one push onto the other.
Commit an edit	`O(m + k) amortized`	`O(1) amortized`	Compares up to m characters to spot a no-op, pushes the old present, then clears the k versions in Future. Go zeroes each one; a JavaScript engine may truncate its array faster.
Snapshot for the screen	`O(n)`	`O(n)`	Copies both stacks.
Hold n versions	`—`	`O(n)`	n versions across Past and Future, plus each version’s own text. The sample history keeps them all.

Pressing Undo moved two versions, one pop and one push, however long the history; you watched it happen in the story. Committing a new edit after a run of Undo does something bigger. It throws the whole redo branch away, and every version on that branch has to go. With a short branch you will never notice. After fifty Undos, the next edit you commit has fifty versions to throw away.

So “undo is O(1)” is true, amortized, and still incomplete. The stack operations are constant. What the editor does around them, comparing text, clearing a branch, copying a snapshot for the screen, is not. Push is amortized for the same reason a growing array is, and Dynamic array walks through why.

07 / Give it a real job

It works. Now leave the editor open all afternoon.

Keeping every previous version whole is a lovely place to start, and for a short document and a short session it may be all you ever need. But how many versions pile up over a few hours of real work? What if each one is a canvas, a long form, or a whole document?

Keep the order and change what gets kept. The explorer starts with a limit of 100 undo steps. Try keeping everything, then group edits together, and watch how much history you can walk back through next to how much it holds on to.

Your editor has been open all afternoon.

The document still looks small. How much are its old versions keeping alive? Change one decision and follow both the payload and the undo steps.

Edits made 1,000 Document payload One undo step per Keep undo steps Store history as

Every edit · keep all snapshots: 1.001 GB
Your policy · retained payload: 101 MB

100 undo steps cover 100 recent edits. 900 older edits are outside this history.

What your policy retains Cards show groups, not proportional sizes

Present1 MBCurrent document

Undo group 1,0001 MBOne previous document

Undo group 9991 MBOne previous document

Undo group 9981 MBOne previous document

…and 97 earlier retained groups.

Full snapshot after every edit · keep all
Full snapshots · your policy

View data table

Retained history payload as edits accumulate — exact plotted values
Series	Edits made	Retained payload (MB)
Full snapshot after every edit · keep all	0	1
Full snapshot after every edit · keep all	25	26
Full snapshot after every edit · keep all	50	51
Full snapshot after every edit · keep all	75	76
Full snapshot after every edit · keep all	100	101
Full snapshot after every edit · keep all	101	102
Full snapshot after every edit · keep all	125	126
Full snapshot after every edit · keep all	150	151
Full snapshot after every edit · keep all	175	176
Full snapshot after every edit · keep all	200	201
Full snapshot after every edit · keep all	225	226
Full snapshot after every edit · keep all	250	251
Full snapshot after every edit · keep all	275	276
Full snapshot after every edit · keep all	300	301
Full snapshot after every edit · keep all	325	326
Full snapshot after every edit · keep all	350	351
Full snapshot after every edit · keep all	375	376
Full snapshot after every edit · keep all	400	401
Full snapshot after every edit · keep all	425	426
Full snapshot after every edit · keep all	450	451
Full snapshot after every edit · keep all	475	476
Full snapshot after every edit · keep all	500	501
Full snapshot after every edit · keep all	525	526
Full snapshot after every edit · keep all	550	551
Full snapshot after every edit · keep all	575	576
Full snapshot after every edit · keep all	600	601
Full snapshot after every edit · keep all	625	626
Full snapshot after every edit · keep all	650	651
Full snapshot after every edit · keep all	675	676
Full snapshot after every edit · keep all	700	701
Full snapshot after every edit · keep all	725	726
Full snapshot after every edit · keep all	750	751
Full snapshot after every edit · keep all	775	776
Full snapshot after every edit · keep all	800	801
Full snapshot after every edit · keep all	825	826
Full snapshot after every edit · keep all	850	851
Full snapshot after every edit · keep all	875	876
Full snapshot after every edit · keep all	900	901
Full snapshot after every edit · keep all	925	926
Full snapshot after every edit · keep all	950	951
Full snapshot after every edit · keep all	975	976
Full snapshot after every edit · keep all	1000	1001
Full snapshots · your policy	0	1
Full snapshots · your policy	25	26
Full snapshots · your policy	50	51
Full snapshots · your policy	75	76
Full snapshots · your policy	100	101
Full snapshots · your policy	101	101
Full snapshots · your policy	125	101
Full snapshots · your policy	150	101
Full snapshots · your policy	175	101
Full snapshots · your policy	200	101
Full snapshots · your policy	225	101
Full snapshots · your policy	250	101
Full snapshots · your policy	275	101
Full snapshots · your policy	300	101
Full snapshots · your policy	325	101
Full snapshots · your policy	350	101
Full snapshots · your policy	375	101
Full snapshots · your policy	400	101
Full snapshots · your policy	425	101
Full snapshots · your policy	450	101
Full snapshots · your policy	475	101
Full snapshots · your policy	500	101
Full snapshots · your policy	525	101
Full snapshots · your policy	550	101
Full snapshots · your policy	575	101
Full snapshots · your policy	600	101
Full snapshots · your policy	625	101
Full snapshots · your policy	650	101
Full snapshots · your policy	675	101
Full snapshots · your policy	700	101
Full snapshots · your policy	725	101
Full snapshots · your policy	750	101
Full snapshots · your policy	775	101
Full snapshots · your policy	800	101
Full snapshots · your policy	825	101
Full snapshots · your policy	850	101
Full snapshots · your policy	875	101
Full snapshots · your policy	900	101
Full snapshots · your policy	925	101
Full snapshots · your policy	950	101
Full snapshots · your policy	975	101
Full snapshots · your policy	1000	101

Limiting history limits what you can undo. Grouping can keep more edits within the same step budget, but an Undo becomes a larger move.

Read the assumptions and the production trade-off

A snapshot stores a complete independent document per undo step. The changes model keeps the current document plus forward and inverse payload for each retained edit. It assumes those records can correctly undo and redo the change; implementing and applying them has a separate cost. Any final partial edit group is committed.

Real editors can share unchanged structure or use checkpoints and patches. Immer exposes patches and inverse patches, but does not promise a minimal patch set. This is a way to explore a policy, not a replacement editor implementation.

Our earlier lab stores strings and copies its history arrays for inspection. Its actual memory use is not given by this independent-document model. Start with the simple policy when it fits; change it when the workload and retention requirements justify the extra machinery.

Payload model, not a heap measurement. Decimal units: 1 MB = 1,000,000 bytes. Document size is held constant; present is included once. No structural sharing, compression, metadata, allocation overhead, temporary copies, or redo branch. Curves join sampled edit counts; axes adapt to the chosen workload.

The first version earned its place: it made the behavior easy to see. A heavier workload is a reason to revisit what you store and for how long, as long as Undo still does what the person pressing it expects.

These versions are strings. Once a version is an object or a whole document, you also have to decide whether old versions are copies or shared. A stack keeps order. It cannot keep a snapshot of something someone else is still changing.

What changes in a production editor?Grouping, limits, ownership, and more than one editor

Choose the unit of an edit. Undoing a keystroke and undoing a finished drag feel very different. Group changes wherever the person expects one Undo to take them all back.

Bound what you keep. The sample history keeps everything, and the explorer above shows what a limit costs you. Pick a maximum in versions or bytes. Notice that dropping the oldest version means taking from the bottom of the stack, which a pure stack cannot do. That is a deque, or, with a fixed limit, a ring buffer.

Decide what a version owns. Immutable values, copied snapshots, patches, and reversible commands each trade memory against work. And putting an old value back on screen does not unsend an email or refund a payment.

Keep histories separate. One editor’s Undo should never pop another editor’s version. Once edits come from more than one person, decide whose changes Undo can take back before you stretch this model.

Build UIs?You have a stack open right now, and one day you will need to own one.

Where it already is in your components

Every app has a pile of things that open on top of each other: a dialog, then a popover inside it, then a menu inside that. Escape closes the top one, and only the top one. That is a stack, and you wrote it with an array: push when something opens, pop on Escape, peek to know which layer owns focus. React copies the array each time. Svelte lets you push in place. The browser’s Back and Forward buttons follow the same rule as Undo and Redo, and you do not own them, which is the next part.

When you have to own it

A settings sheet with nested screens: Account, then Security, then Change password. Back inside the sheet should go up one screen. Closing the sheet should forget all of it. Neither should touch the browser’s back button. Reach for pushState here and every screen becomes an entry in the tab’s history, so the browser’s Back button walks back through the sheet. For this sheet, that is not what you want.

So you own a stack. Push a screen, pop on Back, reset on close, render the top. The hook is about a dozen lines, and it is Undo’s Past stack applied to screens. The Redux undo-history guide builds the full version with past, present, and future, if you ever want Forward too.

Layered UI. Push when something opens, pop on Escape, peek for focus. React copies the array; Svelte pushes in place.

ReactAlready in your code

Layers.tsx

import { useEffect, useState } from 'react';
import { Dialog, Menu, Popover } from './layers';

type Layer = 'dialog' | 'popover' | 'menu';

export function Layers() {
	// Whatever opened last is on top. Escape closes it, and only it.
	const [open, setOpen] = useState<Layer[]>([]);

	function push(layer: Layer) {
		// push: a new array with one more on top. A layer is open once or not at all.
		setOpen((stack) => (stack.includes(layer) ? stack : [...stack, layer]));
	}

	useEffect(() => {
		function onKey(event: KeyboardEvent) {
			if (event.key !== 'Escape') return;
			setOpen((stack) => stack.slice(0, -1)); // pop: everything but the top
		}
		window.addEventListener('keydown', onKey);
		return () => window.removeEventListener('keydown', onKey);
	}, []);

	const top = open.at(-1); // peek: who owns focus right now

	return (
		<>
			<button onClick={() => push('dialog')}>Open dialog</button>
			{open.includes('dialog') && (
				<Dialog active={top === 'dialog'} onMore={() => push('popover')} />
			)}
			{open.includes('popover') && (
				<Popover active={top === 'popover'} onMore={() => push('menu')} />
			)}
			{open.includes('menu') && <Menu active={top === 'menu'} />}
		</>
	);
}

08 / Make the call

Ask what “next” means here.

Reach for a stack when the most recent thing is the next thing to deal with. Keep it concrete: the latest edit, the innermost bracket, the screen to go back to.

If the oldest thing comes next, that is a queue. If the next thing is picked by priority, that is a heap. If you pull out a particular item by id, you want a lookup. The values can look identical while the question is different.

Keep a plain array when push and pop already say what you mean. A wrapper earns its place when it stops callers reaching into the middle.

What about recursion and the call stack?Another place to recognize the idea

Conceptually, each function call pushes a frame onto the call stack and each return pops it. Compilers may inline a call or reuse a frame, but the order is preserved. That is the stack trace you read when something throws. Recursion leans on it directly. An explicit stack does the same job in your own data, which is how a depth-first walk survives a tree too deep for the call stack.

Neither is free. An explicit stack still uses memory, and how deep the call stack can go depends on the language and runtime.

For a given tree, ask whether plain recursion reads clearly, whether the walk has to pause and resume, and how deep the input can get. That settles it better than picking a side.

09 / Take the idea with you

Explain the order without saying “stack.”

“When I leave a version, I keep it where I can get the most recent one back first.” That is the design in one sentence. The name is just shorter.

Before moving on, try three notes: what a stack promises, why empty text was still a value, and which part of undo and redo was this editor’s policy. Then, the next time something throws, read the stack trace from the top down: that is the order the stack would pop.

Connections to follow nextRelated lessons

Factory creates a fresh history instance with its own state.
Command gives an action a value: retain an executable request and what its execution needs to undo.
Depth-first search uses a stack to decide which pending node to visit next.