cf.completefrontend
ALGORITHMS IN FRONTEND WORK · FOUNDATION

Undo and redo with two stacks

Keep past states on an undo stack and undone states on a redo stack, so undo and redo each move one state between them.

Time O(1) per operationSpace O(h)3 practice problemsStep-through picture

The idea

Every editor needs undo and redo. The simplest correct design keeps three things: present, the current state; undoStack, the states before it, most recent on top; and redoStack, the states you undid, most recently undone on top.

A new change pushes present onto undoStack, makes the new state the present, and empties redoStack, because the undone future no longer fits after a new change. Undo pushes present onto redoStack and pops the top of undoStack into present. Redo does the mirror image.

A stack is the right tool because undo always goes back to the most recent state first: last in, first out. Each operation is O(1).

An everyday example

Two piles of drawings

You draw on a sheet. Before each change, you put a copy of the current drawing on the left pile. To undo, you put your current sheet on the right pile and take the top sheet from the left pile. To redo, you do the opposite. If you draw something new after undoing, the sheets on the right pile describe a future that didn't happen, so you throw that pile away.

How the example maps to the code
In the exampleIn the code
The sheet in front of youthis.present
The left pile of earlier drawingsthis.undoStack
The right pile of undone drawingsthis.redoStack
Drawing something newcommit(next), which also empties redoStack
Swapping a sheet between pilesundo() and redo()

From the slow way to undo and redo with two stacks

  1. Start with the obvious way: keep one previous value next to the current one, and swap them on undo. That gives one level of undo. Press undo twice and you are back where you started, because the swap just toggles between two states.
  2. To undo many steps, keep every past state. The state you go back to first is always the most recent one, then the one before it. Most recent first is last in, first out, so the past states belong on a stack: push the current state before each change, pop it on undo.
  3. But undo then throws away the state you were on, and redo needs it. So when undoing, push the current state onto a second stack instead of dropping it. Redo is the mirror image: push the current state back onto the undo stack and pop from the redo stack.
  4. One rule is left. If the user undoes and then makes a new change, the states on the redo stack belong to a future that will never happen. Mixing them in would jump between two timelines, so a new change empties the redo stack. Those two stacks around a present value are undo and redo history.

How it works

  1. Start with present set to the initial state and two empty stacks.
  2. commit(next): push present onto undoStack, set present = next, and clear redoStack.
  3. undo(): if undoStack is empty, there's nothing to undo, so return present. Otherwise push present onto redoStack and pop undoStack into present.
  4. redo(): if redoStack is empty, return present. Otherwise push present onto undoStack and pop redoStack into present.
  5. Each method returns the new present, so the caller can render it.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. class History {
  2. constructor(initial) {
  3. this.present = initial;
  4. this.undoStack = [];
  5. this.redoStack = [];
  6. }
  7. commit(next) {
  8. this.undoStack.push(this.present);
  9. this.present = next;
  10. this.redoStack = [];
  11. }
  12. undo() {
  13. if (this.undoStack.length === 0) return this.present;
  14. this.redoStack.push(this.present);
  15. this.present = this.undoStack.pop();
  16. return this.present;
  17. }
  18. redo() {
  19. if (this.redoStack.length === 0) return this.present;
  20. this.undoStack.push(this.present);
  21. this.present = this.redoStack.pop();
  22. return this.present;
  23. }
  24. }

How fast it is

TimeO(1) per operation
Extra memoryO(h)

Each method does at most one push and one pop. The stacks hold one entry per saved state, h in total.

  • Best caseO(1)

    Any call: undo and redo do one push and one pop, and commit does one push and one assignment.

  • Average caseO(1)

    The same for every call, however long the history is.

  • Worst caseO(1)

    Still one push and one pop. Replacing redoStack with [] is one assignment; the old array is cleaned up later by the engine. Making the next state is the caller's job and can cost more.

Common mistakes

  • Forgetting to clear redoStack on a new change. Redo then jumps to a state from an abandoned timeline.
  • Saving a reference to a mutable object and then changing it. Every history entry points at the same object and undo shows the latest version. Save copies or use immutable updates.
  • Pushing a history entry for every keystroke. Undo then removes one letter at a time. Group quick changes into one entry.
  • Letting history grow forever in a long session. Cap it and drop the oldest entries.

When to use it

Look for these clues in a problem:

  • The question involves undo, redo, back and forward, or history of states.
  • Commands arrive one by one and some of them reverse earlier ones.
  • After going back, a new action should discard the forward history.
  • You need the most recent item first, which is last in, first out.

Check yourself

Answer each one in your head first, then open it.

After commit("A"), commit("B"), undo(), commit("C"), what does redo() do?

Nothing: it returns "C". commit("C") emptied the redo stack, so "B" can't come back.

Why is a stack the right structure for past states?

Undo always goes back to the most recent state first, then the one before it. That is last in, first out, which is exactly what a stack gives.

After 3 commits and then 3 undos, how big are the two stacks?

undoStack is empty and redoStack holds 3 states. Each undo moved one state from one stack to the other.

Why does changing an object in place break the history?

The stacks store references. If every entry points to the same object, changing it changes every entry, so undo shows the newest content.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Think of the history as one line of states, oldest to newest, with a cursor on the one the user sees. The class keeps this rule: undoStack from bottom to top, then present, then redoStack from top to bottom, spells out that whole line in order. The states before the cursor are on the undo stack, nearest on top. The states after it are on the redo stack, nearest on top.

Each method keeps the rule. undo moves the cursor one step back: the nearest earlier state comes off the top of undoStack, and the old present becomes the nearest later state, on top of redoStack. redo is the same move forward. commit cuts the line right after the cursor and adds the new state: the old present joins the earlier states, and the later states are dropped by emptying redoStack.

The empty-stack checks handle the two ends of the line: with nothing before the cursor, undo can't move, and with nothing after it, redo can't. Because undo and redo are exact opposites, undoing j times and then redoing j times always returns to the same state, as long as no commit happened in between.

Going deeper

3 more ideas

Why the redo stack is cleared on a new change

Say you type a, b, c, undo twice to get a, then type x. The states ab and abc came after a in an old timeline. Redoing to ab after ax would mix two timelines. Clearing redoStack keeps one straight line of history. Some apps keep the old branches in an undo tree instead, but most editors do the simple thing.

States or commands

This version stores whole states, which is simple and works well with immutable data, like Redux state. Large documents often store commands instead: each entry knows how to apply and revert a small change, such as "insert x at position 5". Editors also merge quick typing into one entry, so one undo removes a word instead of a single letter.

How fast it is

Each operation is a push and a pop, so O(1). Memory grows with the number of saved states, O(h) for h history entries. Many apps cap the history, dropping the oldest entries, to bound memory.

Work it by hand

Every step in a table, with why

Edit a greeting, undo past the start, redo, and then make a new change that wipes out the redo stack.

new History("Hi"), then commit, commit, undo, undo, undo, redo, commit, redo, undo

StepCallundoStackpresentredoStackWhy
1new History("Hi")[]"Hi"[]Nothing to undo or redo yet.
2commit("Hi Sam")["Hi"]"Hi Sam"[]The old present is saved on the undo stack before moving on.
3commit("Hi Sam!")["Hi", "Hi Sam"]"Hi Sam!"[]The newest saved state is on top, at the right.
4undo()["Hi"]"Hi Sam"["Hi Sam!"]"Hi Sam!" goes to the redo stack and "Hi Sam" comes back.
5undo()[]"Hi"["Hi Sam!", "Hi Sam"]Back to the start. The most recently undone state, "Hi Sam", is on top of the redo stack.
6undo()[]"Hi"["Hi Sam!", "Hi Sam"]The undo stack is empty, so it returns present and changes nothing.
7redo()["Hi"]"Hi Sam"["Hi Sam!"]Redo pops "Hi Sam", the top of the redo stack, and saves "Hi" for undo.
8commit("Hi Max")["Hi", "Hi Sam"]"Hi Max"[]A new change. "Hi Sam!" belonged to the old future, so the redo stack is emptied.
9redo()["Hi", "Hi Sam"]"Hi Max"[]Nothing to redo, so nothing changes.
10undo()["Hi"]"Hi Sam"["Hi Max"]Undo still works on the new timeline: "Hi Max" can be redone.

The final present is "Hi Sam". "Hi Sam!" can never come back, because commit("Hi Max") started a new timeline after it was undone.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Undo and redo with two stacksO(1)O(h)Most editors and forms: simple, O(1) per action, and easy to prove correct.
One array and an indexO(1)O(h)You also want to jump to any point, like a history panel in a design tool.
Commands with apply and revertO(1)O(h)States are large, like long documents, so storing small changes saves a lot of memory per entry.
Undo treeO(1)O(h)Users must never lose work by undoing and then typing, as in Vim.

Extra memory: O(h) entries for h saved states. If each state is a full copy of a big document, memory is h times its size; immutable updates that share unchanged parts keep it small.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Undo and redo with two stacks and the other approaches, on a scale where each line up is 10 times more steps.
  • Undo and redo with two stacks, One array and an index, Commands with apply and revert, Undo tree O(1)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Undo and redo with two stacks111
One array and an index111
Commands with apply and revert111
Undo tree111

Inputs that need care

6 tricky inputs
undo() right after new History("Hi")
undoStack is empty, so it returns "Hi" and both stacks stay empty.
redo() right after a commit
commit emptied redoStack, so it returns present unchanged.
commit("Hi") while present is already "Hi"
The code saves a duplicate, so the next undo seems to do nothing. Skip a commit when the new state equals present.
Committing the same object after changing it in place
Every entry points to the same object, so undo shows the latest version. Commit a new object for each change, or a copy.
A session with 50,000 edits
The undo stack grows forever. Cap it and drop the oldest entry when it's full; shift on an array is O(h), so a ring buffer keeps it O(1).
Undo in a text editor where the cursor moved
Restoring only the text puts the cursor in the wrong place. Save the selection in each entry, so undo also puts the cursor back where the change was made.

Variations and follow-ups

Twists interviewers add

Store changes instead of whole states

Each entry is a command that knows how to apply and revert one small change, like "insert x at 5", or a pair of patches. Immer's produceWithPatches returns both the patches and the inverse patches. Big documents then cost memory per change, not per copy.

Grouping quick changes

Typing a word letter by letter shouldn't need one undo per letter. Editors merge changes made close together in time into one entry. ProseMirror's history does this with its newGroupDelay option.

An undo tree

Instead of dropping the redo states on a new change, keep them as a branch. Vim does this: :undolist shows the branches, and g- and g+ move through every state in time order, even ones on abandoned branches.

One array and an index

Keep all states in one array and an index for the present. Undo and redo move the index, and a new change cuts the array after it. This is how browser back and forward behave, and it makes a history panel that jumps to any step easy.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "undo", "redo", "back and forward", or a list of operations where some reverse earlier ones.
  • Explain the timeline picture: past states on one stack, future states on the other, present in the middle. Say why a new change empties the redo stack.
  • Test by hand: undo on an empty history, undo then commit then redo, and redo all the way after undoing everything.
  • Expect follow-ups: "cap the history at 100 entries" (drop the oldest, ideally with a ring buffer), "states are huge" (store commands or patches), and "don't undo one letter at a time" (group changes).

Where frontend code uses it

The same idea in real UI code
  • Text editors like CodeMirror and ProseMirror keep undo and redo stacks of changes, grouping changes made close together in time.
  • Redux's undo recipe and the redux-undo library keep past, present, and future, which are these two stacks around the present state.
  • Design tools, form builders, and drawing canvases use the same structure; the browser's back and forward buttons behave the same way, where visiting a new page clears the forward list.

Related algorithms