多重彈出堆疊（multipop stack）

拿一個有 Push 與 Pop 的普通堆疊，再加一個操作：Multipop(k)，在一次呼叫中彈出最上面 k 個項目（若堆疊不足 k 個就清空）。單次 Multipop 可能昂貴——彈出 k 個項目花 k 單位工作，而 k 可能大到整個堆疊。於是天真地看，一串操作顯得很慢。多重彈出堆疊正是這種恐懼結果並無根據的那個小而經典的例子。

先看逐操作最壞情況：對大小 n 的堆疊做 Multipop 花 O(n)，所以 m 個操作看起來可能花 O(n*m)。但這重複計算了。關鍵觀察是一條守恆律：每個項目最多被彈出一次，且只在它被推入恰好一次之後。所以在整條序列中，彈出的總數（無論由 Pop 還是 Multipop 造成）永遠不超過推入的總數，而後者至多 m。因此 m 個操作的總工作量至多 2m（每次推入 1 單位，每次彈出 1 單位，而彈出受推入所限），每個操作的攤還成本是 O(1)。記帳證明很生動：每次 Push 收 2——1 用於推入，1 存在那個項目上以預付它日後的彈出——於是 Pop 與 Multipop 都免費，完全由它們移除的項目上所停的存款支付。

多重彈出堆疊以縮影教你攤還的核心直覺：一個孤立看像 O(n) 的操作其實無害，只要它所做的工在項目被創造時就已「付清」。同樣的守恆模式——你移除的不可能比插入的多——在「兩個堆疊實作的佇列」、「每條邊被處理有限次的圖演算法」、以及許多掃描法中反覆出現。誠實的提醒一如往常：某一次特定的 Multipop 確實可能花 O(n) 時間；攤還界定的是總和，不是峰值。