演算法圖鑑
資料結構 · 4 個細項

Stack & Queue堆疊與佇列

堆疊記住「最近發生的事」,佇列記住「最早發生的事」。它們簡單到用陣列就能做,卻決定了 DFS 與 BFS 的行為,單調堆疊與單調佇列更是把 O(n²) 壓成 O(n) 的利器。

為什麼要學 Stack & Queue

現實中的應用
編輯器的括號配對與 undo

遇到左括號就推入,遇到右括號就彈出比對。Ctrl+Z 也是把每個操作推進堆疊,undo 就彈出來。

→ 對應課程:Stack
印表機與訊息佇列

先送出的工作先印、先進來的訊息先處理。Kafka、RabbitMQ 這類系統的核心抽象就是佇列。

→ 對應課程:Queue & Deque
股價「下一次比今天高是哪天」

對每一天問「之後第一個更高的價格」,暴力是 O(n²)。單調堆疊只掃一遍,每個元素進出各一次。

→ 對應課程:Monotonic Stack
監控儀表板的視窗最大值

每秒問「過去 60 秒的最大延遲」。單調佇列讓視窗滑動時,取最大值仍是 O(1)。

→ 對應課程:Monotonic Queue

細項

4