陣列版的堆疊和佇列會先準備一段連續空間，資料放進預留的位置。今天改用鏈結串列：每筆資料各自放在一個節點裡，再用指標把節點接起來。這種做法不必一開始決定固定容量，但每個節點都要多存一個指標，也要用 malloc 和 free 管理記憶體。

節點如何串起來？

單向鏈結串列的節點包含資料和 next 指標。next 記住下一個節點的位置；最後一個節點的 next 是 NULL：

入口 → [10 | next] → [20 | next] → [30 | NULL]

箭頭只表示「下一個是誰」，節點在記憶體裡不一定排在一起。節點可能分散在不同位置，程式靠 next 一個接一個找到它們。

鏈結式堆疊：在串列開頭 push 和 pop

堆疊的頂端可以直接當成單向串列的開頭，用 top 指向頂端節點。執行 push(20) 時，先建立新節點，再讓它接到原本的 top，最後把 top 改指向新節點：

top
 |
 v
[20 | next] → [10 | NULL]

pop 則取出 top 的資料，把 top 移到下一個節點，並用 free 釋放原本的頂端節點。peek 只讀取頂端資料，不改變 top。不管堆疊裡有幾筆資料，每次都只改一兩個指標就好。

鏈結式佇列：從 front 取出、從 rear 加入

佇列用 front 指向下一筆要取出的節點，用 rear 指向最後加入的節點。

front                         rear
  |                             |
  v                             v
[10 | next] ----------------> [20 | NULL]

enqueue 會建立新節點，接在舊 rear 後面，再更新 rear。如果佇列原本是空的，第一個節點同時是隊首和隊尾，所以 front、rear 都要指向它。

dequeue 取出並移除 front，再把 front 移到下一個節點。若取出的是最後一筆資料，新的 front 會是 NULL；這時也要把 rear 設為 NULL，讓兩個指標都表示佇列為空。否則 rear 還指著剛被 free 的節點，下次 enqueue 就會把新節點接到一個已經不存在的節點後面。

鏈結式堆疊完整程式

這段程式獨立示範 push、pop、peek 和釋放節點。pop、peek 遇到空堆疊時回傳 false；建立節點時若 malloc 失敗，push 也會回傳 false。函式的 int *value 參數是指標；main 裡的 value 是一般 int 變數，呼叫時傳入 &value，讓函式把結果寫回去。

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

// 每個節點存一筆資料，next 記住下一個節點；最後一個節點的 next 為 NULL。
typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;  // 指向堆疊頂端；空堆疊時為 NULL。
} Stack;

// 配置並初始化一個新節點；配置失敗時回傳 NULL。
static Node *createNode(int value) {
    Node *newNode = malloc(sizeof *newNode);

    if (newNode == NULL) {
        return NULL;
    }

    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

static bool stackPush(Stack *stack, int value) {
    if (stack == NULL) {
        return false;
    }

    Node *newNode = createNode(value);

    if (newNode == NULL) {
        return false;
    }

    newNode->next = stack->top;  // 先讓新節點接到原本的頂端。
    stack->top = newNode;        // 再把頂端改成新節點。
    return true;
}

static bool stackPop(Stack *stack, int *value) {
    if (stack == NULL || value == NULL || stack->top == NULL) {
        return false;
    }

    Node *removedNode = stack->top;  // 暫存要移除的頂端，稍後才能釋放它。
    *value = removedNode->data;
    stack->top = removedNode->next;  // 頂端往下一個節點移動。
    free(removedNode);
    return true;
}

static bool stackPeek(const Stack *stack, int *value) {
    if (stack == NULL || value == NULL || stack->top == NULL) {
        return false;
    }

    *value = stack->top->data;  // 只讀取資料，不改變 top，也不移除節點。
    return true;
}

static void freeStack(Stack *stack) {
    if (stack == NULL) {
        return;
    }

    while (stack->top != NULL) {
        Node *removedNode = stack->top;
        stack->top = removedNode->next;  // 先保存下一個位置，再釋放目前節點。
        free(removedNode);
    }
}

int main(void) {
    Stack stack = {NULL};  // 從空堆疊開始。
    int value;

    puts("== 鏈結式堆疊 ==");

    // 先放入 10，再放入 20；因此 20 位於堆疊頂端。
    if (!stackPush(&stack, 10) || !stackPush(&stack, 20)) {
        fprintf(stderr, "堆疊節點配置失敗。\n");
        freeStack(&stack);
        return EXIT_FAILURE;
    }

    // peek 查看頂端，但不會把 20 移出堆疊。
    if (stackPeek(&stack, &value)) {
        printf("peek: %d\n", value);
    }

    // 持續 pop，直到空堆疊讓 stackPop 回傳 false。
    while (stackPop(&stack, &value)) {
        printf("pop: %d\n", value);
    }

    if (!stackPop(&stack, &value)) {
        puts("空堆疊：pop 沒有資料可取。");
    }

    if (!stackPeek(&stack, &value)) {
        puts("空堆疊：peek 沒有資料可看。");
    }

    freeStack(&stack);  // 若還有節點未取出，程式結束前一樣會釋放。
    return EXIT_SUCCESS;
}

堆疊程式先輸出 peek: 20，接著依序取出 20、10；peek 沒有移除 20。堆疊空了之後再 pop 或 peek，都會回傳 false。

鏈結式佇列完整程式

這段程式獨立示範 enqueue、dequeue 和釋放節點。空佇列執行 dequeue，或建立節點時 malloc 失敗，都會回傳 false。

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

// 每個節點存一筆資料，next 記住下一個節點；最後一個節點的 next 為 NULL。
typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;  // 指向下一個要取出的節點。
    Node *rear;   // 指向最後加入的節點。
} Queue;

// 配置並初始化一個新節點；配置失敗時回傳 NULL。
static Node *createNode(int value) {
    Node *newNode = malloc(sizeof *newNode);

    if (newNode == NULL) {
        return NULL;
    }

    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

static bool queueEnqueue(Queue *queue, int value) {
    if (queue == NULL) {
        return false;
    }

    Node *newNode = createNode(value);

    if (newNode == NULL) {
        return false;
    }

    if (queue->rear == NULL) {
        queue->front = newNode;  // 原本是空佇列：第一個節點同時是隊首與隊尾。
    } else {
        queue->rear->next = newNode;  // 接在原本的隊尾後面。
    }

    queue->rear = newNode;  // 新節點成為隊尾。
    return true;
}

static bool queueDequeue(Queue *queue, int *value) {
    if (queue == NULL || value == NULL || queue->front == NULL) {
        return false;
    }

    Node *removedNode = queue->front;  // 暫存隊首節點，取出後才釋放。
    *value = removedNode->data;
    queue->front = removedNode->next;  // 隊首往下一個節點移動。

    if (queue->front == NULL) {
        queue->rear = NULL;  // 最後一筆也被取走，隊首和隊尾都要表示空佇列。
    }

    free(removedNode);
    return true;
}

static void freeQueue(Queue *queue) {
    if (queue == NULL) {
        return;
    }

    while (queue->front != NULL) {
        Node *removedNode = queue->front;
        queue->front = removedNode->next;  // 先保存下一個位置，再釋放目前節點。
        free(removedNode);
    }

    queue->rear = NULL;  // 所有節點都釋放後，隊尾也要清空。
}

int main(void) {
    Queue queue = {NULL, NULL};  // front、rear 都是 NULL，表示空佇列。
    int value;

    puts("== 鏈結式佇列 ==");

    // 依序加入 10、20；dequeue 時應先取出 10。
    if (!queueEnqueue(&queue, 10) || !queueEnqueue(&queue, 20)) {
        fprintf(stderr, "佇列節點配置失敗。\n");
        freeQueue(&queue);
        return EXIT_FAILURE;
    }

    // 持續 dequeue，直到空佇列讓 queueDequeue 回傳 false。
    while (queueDequeue(&queue, &value)) {
        printf("dequeue: %d\n", value);
    }

    if (!queueDequeue(&queue, &value)) {
        puts("空佇列：dequeue 沒有資料可取。");
    }

    // 前面已取空佇列；重新加入 30 可確認 front、rear 已正確重設。
    if (!queueEnqueue(&queue, 30)) {
        fprintf(stderr, "佇列節點配置失敗。\n");
        freeQueue(&queue);
        return EXIT_FAILURE;
    }

    if (queueDequeue(&queue, &value)) {
        printf("重新加入後 dequeue: %d\n", value);
    }

    freeQueue(&queue);  // 若還有節點未取出，程式結束前一樣會釋放。
    return EXIT_SUCCESS;
}

佇列程式依序輸出 dequeue: 10、dequeue: 20。取空後再加入並取出 30，能確認 front、rear 在空佇列時正確重設。

程式中的 freeStack 和 freeQueue 會逐一保存下一個節點、釋放目前節點，再繼續往後走。不能先 free 節點再讀取它的 next，因為該節點的記憶體已經不再可用。

陣列版和鏈結版的差異

以下用 n 表示目前儲存的資料筆數，用 m 表示陣列容量。表格中鏈結式佇列的 O(1) 有個前提：要保留 rear，才不必每次從頭找尾節點。

若看總儲存空間，容量為 m 的陣列會保留 O(m) 個位置，即使部分位置還沒放資料；鏈結結構目前有 n 筆資料，就需要 O(n) 個節點，而且每個節點都要多花一個指標的空間。若只看每次操作本身額外使用的空間，這些操作都只需要固定數量的暫存變數，也就是 O(1)。

鏈結版不會因預留過多陣列位置而空放容量。表格中的 O(1) 是比較資料結構操作步驟的成長情況，不代表實際耗時相同。鏈結版每次加入或取出還會呼叫 malloc 或 free，配置管理也有實際成本，因此跑起來不一定一樣快。選擇時可以看容量是否固定，以及記憶體使用方式。

小結

鏈結式堆疊把 top 放在串列開頭，鏈結式佇列則用 front 和 rear 分別掌握取出端與加入端。每次操作只需改動少量指標；同時也要仔細處理空結構、節點配置失敗，以及每個節點不再使用時的釋放。

今日重點：

• 鏈結式堆疊在串列開頭操作；push、pop、peek 的時間複雜度都是 O(1)。
• 鏈結式佇列以 front 取出、rear 加入；保留 rear 才能讓 enqueue 維持 O(1)。
• 佇列取出最後一個節點後，要同時把 front 和 rear 設為 NULL。
• 節點不用時要 free，而且要先保存 next 再釋放。
• 若 n 是資料筆數、m 是陣列容量，陣列總空間為 O(m)，鏈結版總空間為 O(n)；操作本身的額外空間為 O(1)。

下一篇將進入二元樹，從根、父子與葉節點等基本名詞開始，練習把樹畫出來。