Undo the Last Thing First: Stacks

An editor has to take back its most recent change first, then the one before, after 10,000 edits as quickly as after 10. Find a structure that keeps undo instant, and learn why it does less than a list on purpose: the stack.

Apprentice · Data Structures · Updated

By

After this lesson you can

  • Explain last in, first out with push, pop and peek
  • Build a stack on a growing array, with push and pop at the end in O(1)

Key takeaways

  • A stack is last in, first out (LIFO): the last item put on is the first one taken off.
  • Push puts an item on top, pop takes the top item off and returns it, and peek reads the top without taking it.
  • Built on a growing array, with the top at the end, push, pop and peek are all O(1).
  • Every language has one: Stack<T> in C#, ArrayDeque in Java, and a list or an array used with append or push and pop in Python and JavaScript.
  • Putting the newest item at the front of a list, or searching for the newest, makes every edit or every undo O(n); a stack makes both O(1).

Before this: Why Does This Loop Take Seconds? Your Language's List and the linked lists chapter. A list lets you work anywhere in it, and some of those places are slow.

You're writing a note in a text editor, and you press Ctrl+Z. The most recent change comes undone: the words you just typed disappear. Press it again and the change before that comes undone, and so on back. To do that, the editor keeps a history of every change you've made, and a long writing session makes a long history: 10,000 edits is an afternoon's work. Ctrl+Z has to be instant at edit 10,000, the same as at edit 10.

So the job is: keep a growing history of edits, and always be able to take back the newest one. By the end of this lesson you'll have the structure every editor uses for it, the stack. First, the plain fixes.

What would you try?

Put each new edit at the front of a list. Then the newest edit is always at index 0, easy to find. But every edit inserted at index 0 moves every older edit one slot along. After 10,000 edits, that's 0 + 1 + 2 + … + 9,999 = 49,995,000 moves, about 50 million, just to record the history, and each undo, taking index 0 out, moves them all back.

Add edits in order, and search for the newest when undo is pressed. Give each edit the time it was made, and on Ctrl+Z, look through the history for the latest time. Recording is now quick. But every undo reads all 10,000 edits to find the newest one: O(n) per press, and undoing the whole afternoon is about 50 million looks again.

What we tried Record an edit Undo Where it breaks
Newest at the front of a list O(n): every older edit moves O(n): they all move back a long session
In order, search for the newest O(1) O(n): read every edit every press of Ctrl+Z

The questions that lead to it

What does the history do most? Two things: record a new edit, many times a minute, and take back the newest edit when Ctrl+Z is pressed. Both have to be fast.

Which edit does undo ever need? Only the newest. Never the 37th, never the oldest. After that one is taken back, the newest of what's left.

So where should the newest edit be? Somewhere you can always reach in one step, and where adding the next one costs nothing. You already know a place like that: the end of a growing array. Add each edit at the end, take back the edit at the end. Nothing ever moves, and nobody ever searches. All the work happens in one place: the top of the pile.

How it got its name

This idea was so useful that it got a name: a stack, like a stack of plates. In a cafeteria, clean plates go on top of a spring-loaded pile, and customers take a plate from the top. Nobody pulls one out of the middle. So the plate on top is always the one that went on last.

That rule is called last in, first out, or LIFO (said "LIE-foe"). A stack has three operations, and they all work at the top:

  • Push puts an item on top.
  • Pop takes the top item off and gives it back to you.
  • Peek reads the top item without taking it off.

A cafeteria plate dispenser: a stack of plates with a hand placing one more on top, labeled "push: on top", and another hand lifting the top plate off, labeled "pop: from the top"; the plate at the bottom is labeled "first in, last out"

There's no "get the third item" and no "insert in the middle". If you need those, you need a list. A stack's small set of operations is a promise: everyone using it knows exactly which item comes off next, and every one of them is fast.

Building one

The top of the stack is the end of a growing array, the cheap end: adding there is O(1) on average and removing the last item is O(1). This EditStack is the editor's undo history: your language's list with only the three stack operations on it, plus a count.

EditStack edits = new EditStack();
edits.Push("typed 'Dear Sam'");
edits.Push("made 'Sam' bold");
edits.Push("typed ', see you Friday'");
Console.WriteLine("Newest edit: " + edits.Peek());
Console.WriteLine("Undo: " + edits.Pop());
Console.WriteLine("Undo: " + edits.Pop());
Console.WriteLine("Edits left: " + edits.Count + ", newest: " + edits.Peek());

class EditStack
{
    private List<string> items = new List<string>();

    public int Count => items.Count;

    public void Push(string edit)
    {
        items.Add(edit);
    }

    public string Pop()
    {
        if (items.Count == 0)
        {
            throw new InvalidOperationException("Nothing to undo");
        }
        string top = items[items.Count - 1];
        items.RemoveAt(items.Count - 1);
        return top;
    }

    public string Peek()
    {
        if (items.Count == 0)
        {
            throw new InvalidOperationException("Nothing to undo");
        }
        return items[items.Count - 1];
    }
}
Newest edit: typed ', see you Friday'
Undo: typed ', see you Friday'
Undo: made 'Sam' bold
Edits left: 1, newest: typed 'Dear Sam'
class EditStack {
    private List<String> items = new ArrayList<>();

    int count() {
        return items.size();
    }

    void push(String edit) {
        items.add(edit);
    }

    String pop() {
        if (items.isEmpty()) {
            throw new IllegalStateException("Nothing to undo");
        }
        return items.remove(items.size() - 1);
    }

    String peek() {
        if (items.isEmpty()) {
            throw new IllegalStateException("Nothing to undo");
        }
        return items.get(items.size() - 1);
    }
}

void main() {
    EditStack edits = new EditStack();
    edits.push("typed 'Dear Sam'");
    edits.push("made 'Sam' bold");
    edits.push("typed ', see you Friday'");
    IO.println("Newest edit: " + edits.peek());
    IO.println("Undo: " + edits.pop());
    IO.println("Undo: " + edits.pop());
    IO.println("Edits left: " + edits.count() + ", newest: " + edits.peek());
}
Newest edit: typed ', see you Friday'
Undo: typed ', see you Friday'
Undo: made 'Sam' bold
Edits left: 1, newest: typed 'Dear Sam'
class EditStack:
    def __init__(self):
        self.items = []

    def count(self):
        return len(self.items)

    def push(self, edit):
        self.items.append(edit)

    def pop(self):
        if not self.items:
            raise IndexError("Nothing to undo")
        return self.items.pop()

    def peek(self):
        if not self.items:
            raise IndexError("Nothing to undo")
        return self.items[-1]


edits = EditStack()
edits.push("typed 'Dear Sam'")
edits.push("made 'Sam' bold")
edits.push("typed ', see you Friday'")
print("Newest edit: " + edits.peek())
print("Undo: " + edits.pop())
print("Undo: " + edits.pop())
print(f"Edits left: {edits.count()}, newest: {edits.peek()}")
Newest edit: typed ', see you Friday'
Undo: typed ', see you Friday'
Undo: made 'Sam' bold
Edits left: 1, newest: typed 'Dear Sam'
class EditStack {
  items = [];

  get count() {
    return this.items.length;
  }

  push(edit) {
    this.items.push(edit);
  }

  pop() {
    if (this.items.length === 0) {
      throw new Error("Nothing to undo");
    }
    return this.items.pop();
  }

  peek() {
    if (this.items.length === 0) {
      throw new Error("Nothing to undo");
    }
    return this.items[this.items.length - 1];
  }
}

const edits = new EditStack();
edits.push("typed 'Dear Sam'");
edits.push("made 'Sam' bold");
edits.push("typed ', see you Friday'");
console.log(`Newest edit: ${edits.peek()}`);
console.log(`Undo: ${edits.pop()}`);
console.log(`Undo: ${edits.pop()}`);
console.log(`Edits left: ${edits.count}, newest: ${edits.peek()}`);
Newest edit: typed ', see you Friday'
Undo: typed ', see you Friday'
Undo: made 'Sam' bold
Edits left: 1, newest: typed 'Dear Sam'
class EditStack {
  private items: string[] = [];

  get count(): number {
    return this.items.length;
  }

  push(edit: string): void {
    this.items.push(edit);
  }

  pop(): string {
    const top = this.items.pop();
    if (top === undefined) {
      throw new Error("Nothing to undo");
    }
    return top;
  }

  peek(): string {
    if (this.items.length === 0) {
      throw new Error("Nothing to undo");
    }
    return this.items[this.items.length - 1];
  }
}

const edits = new EditStack();
edits.push("typed 'Dear Sam'");
edits.push("made 'Sam' bold");
edits.push("typed ', see you Friday'");
console.log(`Newest edit: ${edits.peek()}`);
console.log(`Undo: ${edits.pop()}`);
console.log(`Undo: ${edits.pop()}`);
console.log(`Edits left: ${edits.count}, newest: ${edits.peek()}`);
Newest edit: typed ', see you Friday'
Undo: typed ', see you Friday'
Undo: made 'Sam' bold
Edits left: 1, newest: typed 'Dear Sam'

The last edit made was the first one undone. Popping or peeking at an empty stack is a mistake in every language, so EditStack throws an error with a clear message ("Nothing to undo") instead of handing back nothing. In TypeScript, an array's pop() returns undefined when it's empty, which is why that version checks the result.

Six frames of the edit history, drawn as a vertical pile: empty; "typed 'Dear Sam'" pushed; "made 'Sam' bold" pushed on top; "typed ', see you Friday'" pushed on top; then two frames where pop takes "typed ', see you Friday'" and then "made 'Sam' bold" off the top, leaving "typed 'Dear Sam'". An arrow at the top of each pile is labeled "top"

Your language's stack

You'll rarely write a stack class at work: every language has one ready, built the same way, on a growing array with the top at the end.

Language The stack Push Pop Peek
C# Stack<T> Push(x) Pop() Peek()
Java ArrayDeque<T> push(x) pop() peek()
Python list append(x) pop() items[-1]
JavaScript, TypeScript Array push(x) pop() items[items.length - 1]

Java also has an old Stack class, which still works; Java's own documentation recommends ArrayDeque instead. Python and JavaScript have no separate stack type: a list or array used only at its end is a stack. The discipline is yours: don't reach into the middle.

A stack built on a linked list works too, with the top at the head: push and pop are the front-of-list operations from the last chapter, O(1) each, at the price of one reference per item. Either build keeps the stack's promise, which In Your Textbook: Abstract Data Types looks at more closely.

Try it. Push a fourth edit, "deleted 'Friday'", before the two pops. Which edits come off now, and which one is the newest at the end?

The stack's cost card

Operation Big-O Why, in everyday words
Push O(1) amortized Put a plate on top; moving day for the array is rare
Pop O(1) Take the top plate off; nothing else moves
Peek O(1) Look at the top plate
Find an item that isn't on top O(n) Lift plates off one by one; stacks aren't for searching

Check yourself

2 questions to try on the lesson page.

So what

A stack is a list that only lets you use its cheap end. When a job is "the most recent thing first", as undo, back buttons and nested brackets all are, a stack makes it instant at any size, and the next lesson puts it to work on the other two.

Key terms

Cheat sheets