C語言-堆疊 Stack

2026.06.10 Passau, Germany

在介紹動態記憶體配置的文章中，我們解釋了 Stack 和 Heap，他們是記憶體空間的不同區域，並且在不同的時機使用。

本文要介紹 Stack，但是本文要介紹的是資料結構當中的 Stack，它是一種我們定義出來的概念，規範了資料怎麼存放，而不是我們在動態記憶體配置中介紹的真實存在的一塊記憶體。

Stack

Stack 是一種遵循後進先出 LIFO (Last-In, First-Out) 的資料結構，有點像一罐洋芋片，我們要放資料時要從頂端放入，拿出資料時也要從最頂端拿出。一般在 C 語言實作時，我們常會定義以下幾種基本操作：

1. Push (推入)：把資料加入 Stack 的頂端
2. Pop (彈出)：移除並回傳 Stack 頂端的資料
3. Peek/Top (查看頂端)：回傳 Stack 頂端的資料，但不移除它
4. isEmpty (是否為空)：檢查 Stack 內是否還有資料

對於初學者而言，Stack 的設計可能會讓人覺得很雞肋，我為什麼要設計一種資料結構，讓我每次只能把資料放到最頂端，還只能從最上面拿資料，甚至沒辦法隨心所欲地修改中間的值? 答案是在某些場景下，這種看似綁手綁腳的設定其實是一種保護機制。

舉例來說，你在繪圖軟體設計「上一步」和「下一步」的功能時，你就會希望系統可以做「原路折返」，避免寫程式時腦袋當機，寫了一個把中間的過程抽走的程式碼。又或者瀏覽器的上一頁和下一頁，你不會想要突然跳到別的頁面去，這時 Stack 就體現了它的功能，成為了一種保護機制。

在 C 語言中，要用陣列做一個 Stack，我們需要兩樣東西：一個裝資料的陣列data，以及一個用來記住現在資料疊到哪裡的指標(索引值)top(比如說 top=2就代表現在資料從 0 疊到 2 這麼多)，當我們初始化一個 Stack 的時候，由於裡面還是空的，所以 top=-1 。我們可以把它們打包進一個 struct 裡。

#include <stdio.h>
#include <stdbool.h> // 為了使用 bool, true, false

#define MAX_SIZE 5   // 為了教學方便，我們先定義 Stack 最多只能裝 5 個元素

// 定義 Stack 的結構
typedef struct {
    int data[MAX_SIZE]; // 真正用來儲存資料的「容器」
    int top;            // 永遠指著最頂端資料的「指標」（存的是陣列的索引值）
} Stack;

你可能會注意到，我們在 struct 前面加了 typedef，並在最後大括號外面寫了 Stack。在 C 語言中，typedef 的功能是「定義一種新的資料型態」。如果我們只寫原本的 struct Stack { ... };，以後每次要產生一個 Stack 變數時，都必須寫： struct Stack myStack;

但加上了 typedef 後，我們等於告訴編譯器：「把這個結構當成一種名為 Stack 的新自訂型態」。以後我們只需要簡潔地寫： Stack myStack; 這樣可以省去每次打 struct 的麻煩，也讓程式碼看起來直觀。

另外，注意到這個型別的定義是寫在最上面的，也就在我們的主函式main之外，這是因為你會在main函式裡面寫主要的任務，然後再另外寫剛剛提到的 pop、push等函式，而這些函式也需要把 Stack 當成參數傳入，所以你必須先定義這個資料型別，這樣這個 Stack 就變成全域通用的，編譯器在遇到pop或push時才不會報錯。

接著我們來寫一些 Stack 常見的函式，注意到這些函式傳入的參數都是指向 Stack 的指標，而不是直接傳入 Stack 本身。這背後主要有兩個原因：

1. 如果直接傳入 Stack，C 語言會把主函式main裡面的 Stack 完整複製一份傳給函式，所以函式拿到的是一個分身，它就算在分身裡面push一個資料，也會在函式結束後釋放 (參考動態記憶體配置)，導致實際上什麼都沒變。但是我們傳入指標的話，函式就能找到 Stack 的記憶體位置並把資料push進去，這樣就實際改到了值。
2. 假設把整個 Stack 而不是它的指標傳進去，也會浪費大量的效能，如果 Stack 存了一千個整數，那還不如傳一個 8Bytes 的指標來得高效。

所以在實際上，使用 push 的場景會是下面這樣。

#include <stdio.h>

// 定義 Stack 的規格
typedef struct {
    int data[10];
    int top;
} Stack;

// 這裡我們先定義 push 函式的「長相」
// 它的第一個參數是 Stack *s，代表它需要一個「門牌號碼（地址）」
void push(Stack *s, int value) {
    /* 
       看不懂 push 在幹嘛沒關係，文章下面會解釋
    */    
    s->top++;
    s->data[s->top] = value;
}

int main() {
    // 1. 在 main 裡面宣告一個區域變數 my_stack
    Stack my_stack;
    my_stack.top = -1; // 初始化

    // 2. 重點：呼叫函式時，要在變數前面加上 &
    // 這樣傳進去的才是 my_stack 的「地址」
    push(&my_stack, 10); 
    push(&my_stack, 20);

    // 驗證一下，本尊確實被修改了
    printf("現在 Stack 的頂端是: %d\n", my_stack.data[my_stack.top]);

    return 0;
}

看完大架構後就能來看每個函式的實作細節，首先是把資料放入 Stack 的push和把資料從 Stack 拿出的pop。

要用push把資料放進去，只需要兩個步驟：先移動指標，再放入資料。在下面的程式碼中 s 是指標，指向 Stack，而 -> 是 C 語言的箭頭運算子 (Arrow Operator)，它的功能是用來存取結構體內部的成員。基本上 s->top等價於 (*s).top(先解開指標，再存取成員)。

void push(Stack *s, int value) {
    // 動作前先檢查：滿了就不能再塞了！
    if (isFull(s)) {
        printf("錯誤：Stack 已滿 (Overflow)！\n");
        return;
    }

    s->top++;                // 第一步：把 top 指標往上移一格（從 -1 變成 0）
    s->data[s->top] = value; // 第二步：把新資料放進 top 現在指著的格子裡
    printf("成功推入: %d\n", value);
}

最後是把資料拿出來的 Pop 功能。這裡有一個反直覺的設計：我們其實不需要真的去「刪除」陣列裡的數字。

int pop(Stack *s) {
    // 動作前先檢查：空的就不拿
    if (isEmpty(s)) {
        printf("錯誤：Stack 是空的 (Underflow)！\n");
        return -1; // 回傳一個錯誤代碼
    }

    int poppedValue = s->data[s->top]; // 第一步：先把頂端的資料拿出來存好
    s->top--;                          // 第二步：把 top 指標往下降一格
    return poppedValue;                // 第三步：把剛剛拿出來的資料交給呼叫者
}

我們把 top 減 1 後，原本那格的數字雖然還留在記憶體裡，但對 Stack 來說已經「看不見」了。下次做 Push 的時候，新資料自然就會覆蓋過去，這樣做可以省下把陣列清零的效能。

在處理 Stack 時很常遇到的兩種錯誤就是 Stack Overflow 與 Stack Underflow。

Stack Overflow: 箱子已經滿了，但你繼續往裡面 Push 東西。它發生的原因通常是 (1). 靜態陣列大小設得太小 (2). 程式陷入無窮迴圈，不斷呼叫自己，導致 Stack 內部空間耗盡。

Stack Underflow: 箱子是空的，你卻從裡面 Pop 東西，程式就會想去抓一個根本不存在的資料，於是程式邏輯錯誤，這也是為什麼做 Pop 之前要檢查 Stack 是否為空。

再來是isEmpty和isFull，分別用來檢查 Stack 是否為空或是客滿。判斷的方式，就是看top的位置是否在最底或是最大容量。

// 檢查 Stack 是否為空
bool isEmpty(Stack *s) {
    return s->top == -1; // 如果 top 還停留在 -1，代表是空的
}

// 檢查 Stack 是否客滿
bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1; // 陣列最後一格的索引是 MAX_SIZE - 1
}

Monotonic Stack

Monotonic Stack 並不是一種新的資料型別，而是一種利用 Stack 來維持「單調性」（遞增或遞減）的處理策略。Monotonic Stack 有兩種類型：Stack 裡面的元素保持單調遞增或單調遞減。因此，它專門用來解決「找尋下一個更大/最小元素」這類問題，能夠大幅優化時間複雜度。

我們直接拿題目來舉例，假設題目給一串陣列，找出對於每個元素來說在它右邊而且又比它小的元素，否則就回傳元素自己。比如說對於 [8,4,6,2,3]，答案為 [4,2,2,2,3]。這就是一個很適合用 Monotonic Stack 的地方。

我們可以把 Monotonic Stack 想像成一個「還沒找到答案的數字待辦清單」。在這個例子中，Stack 的任務是幫每個數字尋找它的「下一個較小值」。如果還沒找到，這個數字 (或它的索引) 就得在疊棧裡排隊。一旦新來的數字比它小，它就能離開 Stack 並拿到答案。

我們準備一個空的 Stack，裡面存放索引 (Index)，因為索引能讓我們精確地在答案陣列中填入數值。

• 遇到 8 (索引 0)：疊棧是空的，8 先進去坐著。
• Stack: [0] (對應數值 8)
• 遇到 4 (索引 1)：我們發現 4 比棧頂的 8 還要小！
• 動作：8 找到了救星。我們把索引 0 踢出疊棧，記錄 ans[0] = 4。
• 現在疊棧空了，換 4 進去排隊。
• Stack: [1] (對應數值 4)
• 遇到 6 (索引 2)：6 比 4 大。這不符合我們要找「較小值」的條件。
• 動作：6 也進去排隊，疊棧維持由底到頂遞增的狀態。
• Stack: [1, 2] (對應數值 4, 6)
• 遇到 2 (索引 3)：重點來了！2 比棧頂的 6 小，也比再下一個 4 小。
• 動作 1：6 找到救星了（是 2）。索引 2 出局，記錄 ans[2] = 2。
• 動作 2：4 也找到救星了（也是 2）。索引 1 出局，記錄 ans[1] = 2。
• 現在疊棧又空了，2 進去排隊。
• Stack: [3] (對應數值 2)
• 遇到 3 (索引 4)：3 比 2 大。
• 動作：3 進去排隊。
• Stack: [3, 4] (對應數值 2, 3)

最後，疊棧裡剩下的索引 3 和 4，代表它們右邊沒有比它們更小的數字了。根據題目要求，我們讓它們的答案等於自己。

既然我們已經清楚了整個運作邏輯，接下來我們就把這段「找救星」的過程，實際轉化為 C 語言程式碼。我們會沿用前面已經寫好的 Stack 結構與 push、pop、isEmpty 函式。

Monotonic Stack 的 C 語言實作

#include <stdio.h>
#include <stdbool.h>

// 假設前面定義的 Stack 結構、push、pop、isEmpty 都已經寫好了
// ... (此處省略基礎 Stack 函式) ...

void findNextSmaller(int arr[], int size) {
    Stack my_stack;
    my_stack.top = -1; // 初始化 Stack

    int ans[size];     // 用來存放最終答案的陣列

    // 遍歷所有陣列裡的數字
    for (int i = 0; i < size; i++) {
        // 核心邏輯：當 Stack 不是空的，且「現在進來的新數字」小於「Stack 頂端索引所對應的數字」
        while (!isEmpty(&my_stack) && arr[i] < arr[my_stack.data[my_stack.top]]) {
            // 代表 Stack 頂端的數字找到救星了！
            int top_index = pop(&my_stack); // 把它踢出待辦清單
            ans[top_index] = arr[i];        // 記錄它的下一個較小值
        }
        // 處理完後，現在的數字（的索引）自己也要進去 Stack 排隊，等著找它的救星
        push(&my_stack, i);
    }

    // 陣列都跑完了，但 Stack 裡面可能還有剩下沒找到救星的索引
    while (!isEmpty(&my_stack)) {
        int leftover_index = pop(&my_stack);
        ans[leftover_index] = arr[leftover_index]; // 根據題目要求，右邊沒更小的就設為自己
    }

    // 印出最終答案驗證結果
    printf("原始陣列: ");
    for (int i = 0; i < size; i++) printf("%d ", arr[i]);

    printf("\n答案陣列: ");
    for (int i = 0; i < size; i++) printf("%d ", ans[i]);
    printf("\n");
}

int main() {
    int arr[] = {8, 4, 6, 2, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    findNextSmaller(arr, size);

    return 0;
}

為什麼要用 Monotonic Stack？

你可能會想：「我用兩個 for 迴圈，一個看現在的數字，另一個往右邊掃描找比較小的數字，不也能算出答案嗎？」

這麼思考也是正確的，但如果陣列長度是 10 萬，使用雙層 for 迴圈的最糟情況下 (例如陣列已經是從小到大排好)，時間複雜度會是 **O(N²)**，程式會需要執行高達 100 億次，絕對會發生超時錯誤 (Time Limit Exceeded)。

而使用了 Monotonic Stack，仔細觀察上面的程式碼可以發現：每一個元素(索引)最多只會被 push 進去一次，也最多只會被 pop 出來一次。因此，即使裡面包了一個 while 迴圈，整體的總操作次數依然與陣列長度成正比。它的時間複雜度被大幅降到了 O(N)，這就是 Monotonic Stack 在這個場景下的價值。

[embed]C語言-指標 Pointer 在 RAM 當中，記憶體是以位元組 (Byte) 為最小定址單位的，每一個位元組都會對應到一個唯一的記憶體地址 (Memory Address)。當我們在 C 語言中宣告一個變數時，編譯器與作業系統就會根據該變數的資料型態 (比如…medium.com

[embed]C語言-鏈結串列 Linked List 介紹完基本的指標後，在深入複雜的資料結構之前，我們必須先認識陣列。陣列是一種線性資料結構，它在電腦記憶體中佔用一塊連續的空間，用來儲存相同型別的資料。你可以把它想像成一排整齊編號的置物櫃，只要知道號碼(索引)，就能立刻拿到裡面的東西。medium.com

[embed]C語言-動態記憶體配置 Dynamic Memory Allocation 我們在前兩篇文章分別介紹了指標 (Pointer) 的使用以及鏈結串列 (Linked List)，這兩者都是寫程式的基礎。這篇文章要來解釋動態記憶體配置，這樣我們才能靈活地使用鏈結串列。medium.com

[embed]搞懂演算法的時間和空間複雜度 想像你是一個剛入職的軟體工程師，你老闆叫你寫一個功能，檢查今天的訂單裡面有沒有重複購買的客戶。於是聰明的你把第一筆訂單拿出來，和剩下的訂單比對；再把第二筆訂單拿出來，繼續和剩下的訂單比對，以此類推。你拿了100筆資料做測試，完美。於是程式碼…medium.com

[embed]C語言-雙重指標與函式指標 本文需要的先備知識為 (1). 指標 (2). 動態記憶體配置。在介紹指標的文章中我們介紹了指標最基本的知識。指標變數可以儲存變數的地址，然後我們可以再去讀這個地址當中的值，如下所示medium.com