Undo the last mutation
Updated
If mutations are mixed (push, pop, set-top), record the inverse on an undo stack: inverse of push is pop; inverse of pop is push(that value). Undo pops the inverse and applies it.
What to focus on
The data stack and the undo stack are two stacks. Do not store inverses on the data stack. After undo, a redo stack can take the inverse of the inverse.
Worked examples
undo push
data [4, 1, 9], last mut push 9- inverse pop
- data [4, 1]
Result: [4, 1]
undo pop
a = [4, 1, 9], data [4, 1], last mut pop 9- inverse push 9
- data [4, 1, 9]
Result: [4, 1, 9]
undo two pushes
a = [4, 1, 9], data [4, 1], last muts push 1 then (already applied)- undo peels 1
Result: [4]
Try it
Write undoLast(data, undos). data is the value stack. undos is the stack of inverse operations. Record inverses. Undo pops an inverse and applies it to data. Undo a push of 9 off [4, 1, 9] → [4, 1]. Undo a pop of 9 back onto [4, 1] → [4, 1, 9]. Undo the last push off [4, 1] → [4].
The undo stack is non-empty. There is a last mutation. Values are integers.