Checkpoint and rollback a stack
Updated
A checkpoint is the size (or a copy) at a moment. Rollback pops until size returns to that checkpoint, or restores the copy. Use size if you only pushed after the checkpoint. Use a copy if you mixed pops.
What to focus on
Size-rollback is O(k) pops. Copy-rollback is O(n) space. Multiple checkpoints are themselves a stack of sizes.
Worked examples
size rollback
a = [4, 1], mark size 2, push 9, push 8, rollback- pop to size 2
Result: [4, 1]
copy rollback
a = [4, 1, 9], saved copy, pop pop, restore- back to [4, 1, 9]
Result: [4, 1, 9]
mark empty
a = [], mark, push 4, rollback- []
Result: []
Try it
Write rollback(a, mark). a is the stack, written [bottom, ..., top]. mark is a saved size or a saved copy. Rollback pops until size equals the mark, or restores the copy. Never pop below the marked size. Mark size on [4, 1], push twice, rollback → [4, 1]. Save a copy of [4, 1, 9], mutate, restore. Rollback to empty after pushing onto [].
Checkpoints are sizes or copies you took. You may start from []. Rollback never pops below the marked size.