the multipop stack

Take an ordinary stack with Push and Pop, and add one operation: Multipop(k), which pops the top k items in one call (or empties the stack if it holds fewer than k). A single Multipop can be expensive — popping k items takes k units of work, and k might be as large as the entire stack. Naively, then, a sequence of operations looks slow. The multipop stack is the small, classic example where this fear turns out to be unfounded.

Look at the per-operation worst case first: Multipop on a stack of size n costs O(n), so m operations look like they could cost O(n*m). But that double-counts. The key observation is a conservation law: every item can be popped at most once, and only after it was pushed exactly once. So across the whole sequence, the total number of pops (whether by Pop or by Multipop) can never exceed the total number of Pushes, which is at most m. Therefore the total work of all m operations is at most 2m (each push is 1 unit, each pop is 1 unit, and pops are bounded by pushes), and the amortized cost per operation is O(1). The accounting proof is vivid: charge 2 for each Push — 1 to push, 1 banked on that item to prepay its eventual pop — and then both Pop and Multipop are free, paid entirely by the credit sitting on the items they remove.

The multipop stack teaches the central amortized intuition in miniature: an operation that looks O(n) in isolation is harmless if the work it does was already 'paid for' when the items were created. The same conservation pattern — you cannot remove more than you inserted — recurs in queue-with-two-stacks, graph algorithms that each edge is processed a bounded number of times, and many sweep methods. The honest caveat is the usual one: one particular Multipop really can take O(n) time; amortization bounds the total, not the peak.