Track extra state alongside values
Updated
Counts, spans, colors, previous mode — anything that must roll back with the value belongs on the pair (or a parallel stack popped in lockstep). If extra must outlive the value, it does not belong on this stack.
What to focus on
Lockstep: every push of a value pushes extra; every pop pops extra. A second min-stack that only pushes when min changes is a space trick. Then pop extra only when the value equals that min.
Worked examples
lockstep pair
a = [(a,1), (b,2)]- pop b also drops 2
Result: aligned
min-stack trick
values [4, 1, 9], mins [4, 1]- pop 9 does not pop mins
- pop 1 does
Result: pop extra only when needed
do not bury extra
a = [4, 1, 9], extra only in a side variable- pop 1 loses the extra unless you stacked it
Result: side variable is not LIFO-safe
Try it
Write lockstep(a). a is a stack of values, with extra stored on a pair or a lockstep stack. Show a pair stack staying aligned on pop. Show a min-stack that pops only when the value is the min. Show a single current-extra variable going stale after a pop. Pair stack: pop b also drops 2. Min-stack: pop 9 does not pop mins; pop 1 does. A side variable is not LIFO-safe.
Stacks of values start non-empty. Extra that must roll back is stored on the pair or a lockstep stack.