Stack for undo and redo

Many editors keep a history of recent changes so you can undo the last operation and sometimes redo it. A single stack is perfect for undo alone (LIFO: undo the most recent change first). To support redo as well, a common pattern uses two stacks: one for actions you can still undo, and one for actions you have undone and could reapply. Typing something new after an undo usually clears the redo stack, because the old “future” no longer matches the new document state.

On this page
  • Undo stack — done edits you can walk backward
  • Redo stack — undone edits you can replay
  • Rules — push, pop, clear redo on new input
  • Example in C — one character at a time

1) Two stacks

Roles of the two stacks (conceptual)
Stack Meaning
Undo Holds the sequence of edits still available to undo (top = last edit).
Redo Holds edits that were undone and can be reapplied in order (top = most recently undone).

Undo stack

Snapshot after typing hello (bottom → top)

h e l l o

The next undo pops o from the top.

Redo stack

Same moment — no undos yet

Empty

Redo fills only after you undo at least once.

Real editors store richer records (cursor ranges, delete/insert spans, command objects). This page uses single-character typing so the stacks mirror the document tail directly.

2) Rules

Operations for the tiny text model
Event Effect
Type a character c Append c to the document; push c onto the undo stack; set redo stack to empty (discard old redo branch).
Undo If undo is not empty: pop the last character from the undo stack, remove that character from the end of the document, push it onto the redo stack.
Redo If redo is not empty: pop from redo, append that character again, push it back onto undo.

3) Example in C

The program builds the word "hello" one character at a time, prints it, undoes twice (yielding "hel"), then redoes once ("hell"). Arrays implement both stacks with integer tops; doc holds the current text.

#include <stdio.h>

#define MAX 100

char undo_stack[MAX];
char redo_stack[MAX];
int undo_top = -1;
int redo_top = -1;

char doc[MAX];
int doc_len = 0;

// New keystroke: record for undo and wipe redo history
void type_char(char c) {
    redo_top = -1;
    undo_stack[++undo_top] = c;
    doc[doc_len++] = c;
}

// Pop last change from undo onto redo
void undo_edit(void) {
    if (undo_top < 0 || doc_len <= 0)
        return;
    char c = undo_stack[undo_top--];
    doc_len--;
    redo_stack[++redo_top] = c;
}

// Reapply one redo; put it back on undo
void redo_edit(void) {
    if (redo_top < 0)
        return;
    char c = redo_stack[redo_top--];
    undo_stack[++undo_top] = c;
    doc[doc_len++] = c;
}

static void print_doc(void) {
    int i;
    putchar('"');
    for (i = 0; i < doc_len; i++)
        putchar(doc[i]);
    printf("\"\n");
}

int main(void) {
    const char *word = "hello";
    int i;

    for (i = 0; word[i] != '\0'; i++)
        type_char(word[i]);
    print_doc();

    undo_edit();
    undo_edit();
    print_doc();

    redo_edit();
    print_doc();

    return 0;
}

Check bounds before every push in production; use wide characters or gap buffers for real text; group keystrokes into “words” or debounce for nicer UX. Graphical apps often wrap operations in structs instead of raw char.

Trace (abbreviated)

Undo / redo stacks show bottom → top. Only the top of each stack matters for the next undo/redo.

After typing hello, then two undos, then one redo
Step Action Document Undo (bottom → top) Redo
1–5 Type h … o hello h e l l o (empty)
6 Undo hell h e l l o
7 Undo hel h e l o l (top l)
8 Redo hell h e l l o

4) Trade-offs

  • Pros — Simple LIFO model; two stacks map cleanly to undo/redo mental models.
  • Cons — Memory grows with history; branching timelines need more design (e.g. tree or command pattern).

More stack uses: Stack applications · Stack introduction.

Key takeaway

Undo is a stack of “what to reverse next.” Redo is a second stack of “what we reversed and could put back.” A new edit after undo clears redo so the history stays consistent with the current document.

See also: Stack applications · Stack tutorial