堆疊（Stack）#

基本概念#

堆疊是一種操作受限的線性表，只允許在一端插入和刪除資料。

核心特性：後進先出（LIFO, Last In First Out）

就像一疊盤子，從上往下放，取的時候也是從上往下取。

基本操作：

• 入堆疊（push）：將資料放入堆疊頂
• 出堆疊（pop）：從堆疊頂取出資料

為什麼需要堆疊？#

陣列和鏈結串列可以替代堆疊的功能，但堆疊的「操作受限」正是它的優勢：

特定的資料結構是對特定場景的抽象。陣列/鏈結串列介面太多，使用時容易出錯。當資料集合只需要在一端插入和刪除，且滿足後進先出特性時，首選堆疊。

實作方式#

時間複雜度： 入堆疊、出堆疊都是 O(1)

空間複雜度： O(1)（存儲空間是必須的，不算額外開銷）

class ArrayStack<T>(private val n: Int) {
    private val items = arrayOfNulls<Any?>(n)  // 陣列
    private var count = 0                       // 堆疊中元素個數

    // 入堆疊
    fun push(item: T): Boolean {
        if (count == n) return false            // 堆疊滿
        items[count] = item
        count++
        return true
    }

    // 出堆疊
    @Suppress("UNCHECKED_CAST")
    fun pop(): T? {
        if (count == 0) return null             // 堆疊空
        val tmp = items[count - 1] as T?
        count--
        return tmp
    }
}

動態擴容的均攤分析#

當堆疊滿時，申請 2 倍大小的陣列，搬移 K 個資料。

• 最好情況：O(1)
• 最壞情況：O(n)
• 均攤時間複雜度：O(1)

K 次入堆疊操作中，只有 1 次需要 O(K) 的搬移，其餘 K-1 次都是 O(1)。把 K 次搬移均攤到 K 次入堆疊，每次入堆疊的均攤複雜度為 O(1)。

堆疊的應用場景#

函式呼叫堆疊#

作業系統給每個執行緒分配獨立的記憶體空間，組織成「堆疊」結構：

• 進入函式 ➡️ 臨時變數作為堆疊幀入堆疊
• 函式返回 ➡️ 堆疊幀出堆疊

fun main() {
    val a = 1
    val ret = add(3, 5)  // add 的堆疊幀入堆疊
    // add 返回後，堆疊幀出堆疊
}

表達式求值#

用兩個堆疊實作：操作數堆疊 + 運算子堆疊

計算 3+5*8-6：

1. 遇到數字 ➡️ 壓入操作數堆疊
2. 遇到運算子 ➡️ 與運算子堆疊頂比較優先順序
   • 優先順序高 ➡️ 壓入運算子堆疊
   • 優先順序低或相等 ➡️ 取出運算子和兩個操作數計算，結果壓回操作數堆疊

括號匹配 ^↗#

檢查 {[()]}、[{()}] 等表達式是否合法：

1. 遇到左括號 ➡️ 入堆疊
2. 遇到右括號 ➡️ 取出堆疊頂左括號匹配
3. 最終堆疊空 ➡️ 合法；否則不合法

瀏覽器前進後退#

用兩個堆疊 X 和 Y：

• 瀏覽新頁面 ➡️ 壓入 X
• 後退 ➡️ 從 X 彈出，壓入 Y
• 前進 ➡️ 從 Y 彈出，壓入 X
• 從中間跳轉新頁面 ➡️ 清空 Y

佇列（Queue）#

基本概念#

佇列也是一種操作受限的線性表。

核心特性：先進先出（FIFO, First In First Out）

就像排隊買票，先來的先買，後來的站末尾。

基本操作：

• 入隊（enqueue）：放資料到隊尾
• 出隊（dequeue）：從隊頭取資料

實作方式#

佇列需要兩個指標：

• head：指向隊頭
• tail：指向隊尾

陣列實作的問題#

隨著入隊出隊操作，head 和 tail 不斷後移。當 tail 到達陣列末端時，即使前面有空間也無法入隊。

解決方案：

1. 在入隊時觸發資料搬移（而非每次出隊都搬移）
2. 使用迴圈佇列

迴圈佇列#

把陣列首尾相連，形成環狀結構。

關鍵判定條件：

• 隊空：head == tail
• 隊滿：(tail + 1) % n == head

迴圈佇列會浪費一個陣列位置，因為需要區分隊空和隊滿的狀態。

class CircularQueue<T>(capacity: Int) {
    private val items = arrayOfNulls<Any?>(capacity)
    private val n = capacity
    private var head = 0
    private var tail = 0

    // 入隊
    fun enqueue(item: T): Boolean {
        if ((tail + 1) % n == head) return false   // 隊滿
        items[tail] = item
        tail = (tail + 1) % n
        return true
    }

    // 出隊
    @Suppress("UNCHECKED_CAST")
    fun dequeue(): T? {
        if (head == tail) return null              // 隊空
        val ret = items[head] as T?
        head = (head + 1) % n
        return ret
    }
}

進階佇列#

阻塞佇列#

在基本佇列上增加阻塞操作：

• 隊空時，取資料會阻塞，直到有資料
• 隊滿時，存資料會阻塞，直到有空位

這就是生產者-消費者模型的實作基礎。

並發佇列#

執行緒安全的佇列。最簡單的做法是加鎖，但並發度低。

基於迴圈佇列 + CAS 原子操作，可以實作高效的無鎖並發佇列。這也是迴圈佇列比鏈式佇列應用更廣泛的原因之一。

佇列的應用場景#

執行緒池請求排隊#

當執行緒池沒有空閒執行緒時，如何處理新請求？

1. 非阻塞方式：直接拒絕
2. 阻塞方式：請求排隊

排隊的實作方式：

• 鏈式佇列（無界）：可無限排隊，但響應時間可能過長
• 陣列佇列（有界）：超過佇列大小則拒絕，對響應時間敏感的系統更合適

對於大部分資源有限的場景，當沒有空閒資源時，都可以通過「佇列」來實作請求排隊。例如：執行緒池、資料庫連線池等。

單調堆疊與單調佇列（Monotonic Stack & Deque）#

這是堆疊與佇列最有威力的進階用法，值得獨立一節細看。

核心思想#

單調堆疊的精神是：堆疊裡只保留「有潛力成為未來答案的候選值」。當一個新元素準備放進來之前，先把堆疊頂所有「會破壞單調性」的舊值全部 pop 掉，使堆疊始終維持嚴格遞增或嚴格遞減。

為什麼可以這樣丟掉舊值？因為一旦新元素比某個舊值更大（或更小），那個舊值對「之後的元素」就再也沒有用了——新元素又新又強，永遠會先擋在它前面。

整個過程中，每個元素至多被 push 一次、pop 一次，之後不再回頭。因此即使外層有迴圈、內層有 while 不斷彈出，總操作次數仍是線性的，整體時間複雜度為 O(n)。

什麼時候該想到它？#

看到以下訊號，就該聯想單調堆疊／單調佇列：

模板：下一個更大元素（Next Greater Element ^↗）#

給定陣列，為每個元素找出右邊第一個比它大的數，沒有則填 -1。

這裡用反向掃描版本：從右往左掃，堆疊裡（由頂到底）維持遞增，存的是「目前還可能成為答案的候選」。放入當前元素前，把所有不大於它的候選彈掉。

fun nextGreaterElement(nums: IntArray): IntArray {
    val n = nums.size
    val result = IntArray(n)
    val stack = ArrayDeque<Int>()  // 存「值」，由頂到底遞增（末端即堆疊頂）

    for (i in n - 1 downTo 0) {
        // 彈掉所有不比目前元素大的候選，它們永遠輪不到了
        while (stack.isNotEmpty() && stack.last() <= nums[i]) {
            stack.removeLast()
        }
        // 此時堆疊頂就是右邊第一個更大的元素
        result[i] = if (stack.isNotEmpty()) stack.last() else -1
        stack.addLast(nums[i])
    }
    return result
}

若要的是「下一個更大元素的索引（距離）」而非數值，把堆疊改成存索引即可——這正是「每日溫度」的解法。

代表題#

• 每日溫度（Daily Temperatures） ^↗：給每天的溫度，問每天要等幾天才會遇到更暖的一天。本質就是「下一個更大元素的索引距離」，堆疊存索引。
• 柱狀圖中最大矩形（Largest Rectangle in Histogram） ^↗：對每根柱子，要找出它左右兩側「第一根比它矮」的柱子，藉此算出以它為高的最大矩形寬度。用單調遞增堆疊一次掃描即可在 O(n) 內求解。

變體：單調佇列（Deque）#

滑動視窗最大值 ^↗的難處在於：視窗右移時，右端要加入新元素、左端要移除過期元素——兩端都要動，純堆疊辦不到，得改用雙端佇列（deque）。

做法（deque 內存的是索引，對應的值由隊頭到隊尾遞減）：

1. 右端維持單調：新元素進來前，從右端彈掉所有比它小的索引（那些值已不可能再當最大值）。
2. 左端移除過期：若隊頭索引已經滑出視窗範圍，從左端彈出。
3. 處理完後，隊頭索引對應的就是當前視窗的最大值。

fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
    val n = nums.size
    val result = IntArray(n - k + 1)
    val dq = ArrayDeque<Int>()  // 存索引，對應值由隊頭到隊尾遞減

    for (i in 0 until n) {
        // 右端：彈掉所有比目前元素小的索引
        while (dq.isNotEmpty() && nums[dq.last()] <= nums[i]) {
            dq.removeLast()
        }
        dq.addLast(i)

        // 左端：移除滑出視窗的過期索引
        if (dq.first() <= i - k) {
            dq.removeFirst()
        }

        // 視窗形成後，隊頭即為最大值
        if (i >= k - 1) {
            result[i - k + 1] = nums[dq.first()]
        }
    }
    return result
}

延伸閱讀可參考 滑動視窗，那裡有視窗類問題更完整的處理框架。

堆疊與遞迴的本質連結#

函式呼叫之所以能「層層深入、再層層返回」，靠的就是呼叫堆疊（call stack）——而它正是一個 LIFO 結構。

以漢諾塔為例：要把 n 個盤子搬到目標柱，得先「把上面 n-1 個盤子移開」，這個子任務又會再拆出更小的子任務……拆解時，最先壓入堆疊的是最大的問題，但它必須等所有子問題都解完才輪到執行。

拆解的順序與合併執行的順序恰好相反：先壓入的後執行、後壓入的先執行。這種「相反」天生就是 LIFO，所以遞迴與堆疊在本質上是同一件事——任何遞迴都能用一個顯式堆疊改寫成迭代。

關於遞迴的拆解與合併、以及如何用堆疊改寫遞迴，詳見 遞迴與分治。

用堆疊做表達式求值的常見陷阱#

初學者常見的錯誤是：把整個算式全部壓入堆疊，最後才開始計算。這對減法、除法這種不滿足結合律的運算會直接出錯。

以 5-4-3 為例，正確答案是 (5-4)-3 = -2。但若把所有數字與運算子先全壓入堆疊，計算時會從堆疊頂開始取，等於先算 4-3 = 1，再算 5-1 = 4——得到完全錯誤的結果。

減法、除法不符合結合律，運算順序必須由左到右。把全部內容壓堆疊後再從頂端往下算，相當於把順序反了過來，自然算錯。

正解是邊讀邊根據運算子優先級決定是否先計算，用雙堆疊協作：

• 操作數堆疊：放數字。
• 運算子堆疊：放運算子。
• 讀到新運算子時，與運算子堆疊頂比較優先級：頂端優先級高於或等於新運算子，就先取出運算子與兩個操作數計算，結果壓回操作數堆疊；否則把新運算子壓入。
• 讀完後，把運算子堆疊剩下的依序結算完畢。

這樣既保證了「先乘除後加減」，又保證了同級運算「由左到右」的順序。本頁前面 表達式求值 一節也用到了相同的雙堆疊思路。

小結#