堆疊記住「最近發生的事」,佇列記住「最早發生的事」。它們簡單到用陣列就能做,卻決定了 DFS 與 BFS 的行為,單調堆疊與單調佇列更是把 O(n²) 壓成 O(n) 的利器。
遇到左括號就推入,遇到右括號就彈出比對。Ctrl+Z 也是把每個操作推進堆疊,undo 就彈出來。
先送出的工作先印、先進來的訊息先處理。Kafka、RabbitMQ 這類系統的核心抽象就是佇列。
對每一天問「之後第一個更高的價格」,暴力是 O(n²)。單調堆疊只掃一遍,每個元素進出各一次。
每秒問「過去 60 秒的最大延遲」。單調佇列讓視窗滑動時,取最大值仍是 O(1)。