Pop while the top fails a condition
Updated
Pop-while means: while the stack is nonempty and top does not satisfy a predicate, pop. Stop at the first top that passes, or at empty. You never skip a buried value without popping it.
What to focus on
This is the primitive behind next-greater, histogram, and collision problems. Peek, test, pop, repeat. Do not pop a passing top.
Worked examples
pop greater
a = [1, 3, 5], x = 4, pop while top > x- 5>4 pop
- 3≤4 stop
Result: stack [1, 3], popped 5
all fail
a = [5, 6], x = 1, pop while top > x- 6 pop, 5 pop
Result: []
none fail
a = [1, 2], x = 9, pop while top > x- 2>9? no
Result: [1, 2] unchanged
Try it
Write popWhile(a, pred). a is the stack, written [bottom, ..., top]. pred is a function that takes one value and returns true or false. While the stack is nonempty and pred(top) is true, pop. Stop at the first top that fails pred, or at empty. Do not pop a top that already fails pred. From [1, 3, 5] with pred = top > 4, pop 5 and leave [1, 3]. From [5, 6] with pred = top > 1, drain to []. From [1, 2] with pred = top > 9, no pops.
The stack starts non-empty. Values are integers. pred is a function that takes one value and returns true or false. Draining to empty is a legal outcome of the loop.