数据结构实战：链表、栈与队列的 C 语言实现

2.2.2 单链表的初始化

初始化的目标是创建一个空链表（仅包含头节点，无数据节点），头节点不存储实际数据，仅用于指向链表的第一个数据节点，方便操作：

// 初始化单链表：创建头节点，返回链表头指针
LinkedList initLinkedList() {
    // 分配头节点内存
    LinkedList head = (LinkedList)malloc(sizeof(Node));
    if (head == NULL) {
        // 内存分配失败检查
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE); // 终止程序
    }
    head->next = NULL; // 空链表，头节点后续无节点
    return head;
}

✅ 初始化后的链表状态：head -> NULL（仅头节点，无数据）

2.2.3 单链表的插入操作

插入操作分为三种场景：头插法（插入到链表头部）、尾插法（插入到链表尾部）、中间插入（插入到指定位置），实际开发中头插法和尾插法最常用。

1. 头插法（效率最高，O(1)）

头插法是将新节点插入到头节点和第一个数据节点之间，步骤如下： ① 创建新节点并赋值 ② 新节点的 next 指向头节点的 next（原第一个数据节点） ③ 头节点的 next 指向新节点

// 头插法：向链表头部插入数据
void insertHead(LinkedList head, int data) {
    // ① 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data; // 给新节点赋值
    // ② 新节点指向原第一个数据节点
    newNode->next = head->next;
    // ③ 头节点指向新节点，完成插入
    head->next = newNode;
}

💡 头插法的特点：插入顺序与链表存储顺序相反（如插入 1、2、3，链表中为 3->2->1），适合需要快速插入且不关心顺序的场景。

2. 尾插法（O(n)，需遍历到尾部）

尾插法是将新节点插入到链表的最后一个节点之后，步骤如下： ① 创建新节点并赋值 ② 遍历链表，找到尾节点（next 为 NULL 的节点） ③ 尾节点的 next 指向新节点 ④ 新节点的 next 设为 NULL

// 尾插法：向链表尾部插入数据
void insertTail(LinkedList head, int data) {
    // ① 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL; // 新节点作为尾节点，next 为 NULL
    // ② 遍历找到尾节点
    Node* p = head; // 遍历指针，从 head 开始
    while (p->next != NULL) {
        // 找到 next 为 NULL 的节点（尾节点）
        p = p->next;
    }
    // ③ 尾节点指向新节点
    p->next = newNode;
}

💡 尾插法的特点：插入顺序与链表存储顺序一致（插入 1、2、3，链表中为 1->2->3），适合需要保持插入顺序的场景，但遍历过程会影响效率（可通过增加尾指针优化为 O(1)）。

3. 中间插入（插入到指定位置）

中间插入是将新节点插入到第 k 个数据节点之前，步骤如下： ① 检查插入位置的合法性（k≥1，且不超过链表长度） ② 遍历找到第 k-1 个节点（插入位置的前驱节点） ③ 新节点的 next 指向第 k 个节点 ④ 第 k-1 个节点的 next 指向新节点

// 中间插入：在第 k 个数据节点前插入数据（k 从 1 开始）
int insertMiddle(LinkedList head, int k, int data) {
    // 检查 k 的合法性（k≥1）
    if (k < 1) {
        printf("插入位置不合法！\n");
        return -1; // 插入失败返回 -1
    }
    // 遍历找到第 k-1 个节点（前驱节点）
    Node* p = head;
    int i = 0;
    while (p != NULL && i < k - 1) {
        p = p->next;
        i++;
    }
    // 若 p 为 NULL，说明 k 超过链表长度
    if (p == NULL) {
        printf("插入位置超出链表范围！\n");
        return -1;
    }
    // 创建新节点并插入
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = p->next; // 新节点指向原第 k 个节点
    p->next = newNode; // 前驱节点指向新节点
    return 0; // 插入成功返回 0
}

⚠️ 中间插入的关键是找到"前驱节点"（第 k-1 个节点），若直接找第 k 个节点，会无法关联前驱节点导致插入失败。

2.2.4 单链表的删除操作

删除操作同样分为三种场景：删除头节点后的第一个数据节点、删除尾节点、删除指定数据或指定位置的节点。

1. 删除指定位置的节点

删除第 k 个数据节点的步骤： ① 检查删除位置的合法性 ② 遍历找到第 k-1 个节点（前驱节点）和第 k 个节点（待删除节点） ③ 前驱节点的 next 指向待删除节点的 next ④ 释放待删除节点的内存（避免内存泄漏）

// 删除第 k 个数据节点（k 从 1 开始）
int deleteNode(LinkedList head, int k) {
    if (k < 1) {
        printf("删除位置不合法！\n");
        return -1;
    }
    // 找到第 k-1 个节点（前驱节点）和第 k 个节点
    Node* p = head; // 前驱节点指针
    int i = 0;
    while (p->next != NULL && i < k - 1) {
        p = p->next;
        i++;
    }
    // 若 p->next 为 NULL，说明 k 超过链表长度
    if (p->next == NULL) {
        printf("删除位置超出链表范围！\n");
        return -1;
    }
    // 待删除节点
    Node* delNode = p->next;
    // 前驱节点指向待删除节点的后继节点
    p->next = delNode->next;
    // 释放内存
    free(delNode);
    delNode = NULL; // 避免野指针
    return 0;
}

⚠️ 必须调用 free(delNode) 释放内存，否则会造成内存泄漏（动态分配的内存不会自动回收）；同时将 delNode 设为 NULL，避免野指针（指向已释放内存的指针）。

2. 删除指定数据的节点

删除第一个值为 data 的节点，步骤与指定位置删除类似，只需增加数据匹配判断：

// 删除第一个值为 data 的节点
int deleteByData(LinkedList head, int data) {
    Node* p = head; // 前驱节点指针
    // 遍历查找数据为 data 的节点的前驱
    while (p->next != NULL) {
        if (p->next->data == data) {
            break; // 找到，退出循环
        }
        p = p->next;
    }
    // 若 p->next 为 NULL，说明未找到该数据
    if (p->next == NULL) {
        printf("未找到值为%d的节点！\n", data);
        return -1;
    }
    // 删除节点（同指定位置删除逻辑）
    Node* delNode = p->next;
    p->next = delNode->next;
    free(delNode);
    delNode = NULL;
    return 0;
}

2.2.5 单链表的查找与遍历

1. 遍历链表（输出所有数据）

遍历是链表操作的基础，通过指针移动依次访问每个节点：

// 遍历链表并输出所有数据
void traverseLinkedList(LinkedList head) {
    if (head->next == NULL) {
        // 空链表
        printf("链表为空！\n");
        return;
    }
    Node* p = head->next; // 从第一个数据节点开始
    printf("链表数据：");
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next; // 指针移动到下一个节点
    }
    printf("\n");
}

2. 查找指定数据的节点

返回第一个值为 data 的节点的位置（从 1 开始），未找到返回 -1：

// 查找值为 data 的节点，返回位置（从 1 开始），未找到返回 -1
int findNode(LinkedList head, int data) {
    if (head->next == NULL) {
        return -1;
    }
    Node* p = head->next;
    int index = 1;
    while (p != NULL) {
        if (p->data == data) {
            return index; // 找到，返回位置
        }
        p = p->next;
        index++;
    }
    return -1; // 未找到
}

2.2.6 单链表的销毁

链表使用完毕后，需要释放所有节点的内存（包括头节点），避免内存泄漏：

// 销毁链表，释放所有节点内存
void destroyLinkedList(LinkedList* head) {
    Node* p = *head; // 遍历指针
    Node* temp = NULL;
    while (p != NULL) {
        temp = p; // 保存当前节点
        p = p->next; // 指针移动到下一个节点
        free(temp); // 释放当前节点
    }
    *head = NULL; // 头指针设为 NULL，避免野指针
}

⚠️ 销毁函数的参数是 LinkedList*（结构体指针的指针），因为需要修改头指针本身（将其设为 NULL），若使用 LinkedList head（值传递），修改不会影响外部头指针。

2.2.7 单链表完整测试案例

将上述操作整合，编写测试代码验证功能：

int main() {
    // 1. 初始化链表
    LinkedList head = initLinkedList();
    printf("初始化后：");
    traverseLinkedList(head); // 输出：链表为空！
    
    // 2. 尾插法插入数据
    insertTail(head, 10);
    insertTail(head, 20);
    insertTail(head, 30);
    printf("尾插 10、20、30 后：");
    traverseLinkedList(head); // 输出：10 20 30
    
    // 3. 头插法插入数据
    insertHead(head, 5);
    insertHead(head, 3);
    printf("头插 5、3 后：");
    traverseLinkedList(head); // 输出：3 5 10 20 30
    
    // 4. 中间插入：在第 3 个位置插入 15
    insertMiddle(head, 3, 15);
    printf("第 3 个位置插入 15 后：");
    traverseLinkedList(head); // 输出：3 5 15 10 20 30
    
    // 5. 查找数据
    int pos = findNode(head, 10);
    if (pos != -1) {
        printf("数据 10 的位置：第%d个\n", pos); // 输出：第 4 个
    } else {
        printf("未找到数据 10\n");
    }
    
    // 6. 删除操作：删除第 4 个节点（数据 10）
    deleteNode(head, 4);
    printf("删除第 4 个节点后：");
    traverseLinkedList(head); // 输出：3 5 15 20 30
    
    // 7. 删除指定数据：删除 20
    deleteByData(head, 20);
    printf("删除数据 20 后：");
    traverseLinkedList(head); // 输出：3 5 15 30
    
    // 8. 销毁链表
    destroyLinkedList(&head);
    printf("销毁后：");
    traverseLinkedList(head); // 输出：链表为空！（此时 head 为 NULL，函数内部处理）
    
    return 0;
}

✅ 运行结果与预期一致，说明单链表的实现正确。

2.3 双向链表的实现（扩展知识）

双向链表的每个节点包含两个指针域：一个指向后继节点（next），一个指向前驱节点（prev），相比单链表，双向链表支持双向遍历，删除节点时无需查找前驱节点（效率更高），但结构更复杂，占用内存更多。

2.3.1 双向链表节点结构体定义

// 双向链表节点结构体
typedef struct DNode {
    int data; // 数据域
    struct DNode* prev; // 前驱指针
    struct DNode* next; // 后继指针
} DNode, *DLinkedList;

2.3.2 双向链表的初始化

// 初始化双向链表（带头节点）
DLinkedList initDLinkedList() {
    DLinkedList head = (DLinkedList)malloc(sizeof(DNode));
    if (head == NULL) {
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    head->prev = NULL; // 头节点无前驱
    head->next = NULL; // 头节点无后继
    return head;
}

2.3.3 双向链表的尾插法（核心操作）

// 双向链表尾插法
void insertDTail(DLinkedList head, int data) {
    // 创建新节点
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    // 找到尾节点
    DNode* p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    // 插入逻辑（双向关联）
    p->next = newNode; // 原尾节点的 next 指向新节点
    newNode->prev = p; // 新节点的 prev 指向原尾节点
}

2.3.4 双向链表的删除操作（无需查找前驱）

// 双向链表删除指定数据的节点
int deleteDByData(DLinkedList head, int data) {
    DNode* p = head->next; // 从第一个数据节点开始查找
    while (p != NULL) {
        if (p->data == data) {
            break;
        }
        p = p->next;
    }
    if (p == NULL) {
        printf("未找到值为%d的节点！\n", data);
        return -1;
    }
    // 双向关联修改（无需前驱节点指针）
    p->prev->next = p->next; // 前驱节点的 next 指向后继节点
    if (p->next != NULL) { // 若不是尾节点，后继节点的 prev 指向前驱节点
        p->next->prev = p->prev;
    }
    free(p);
    p = NULL;
    return 0;
}

💡 双向链表删除的优势：找到待删除节点后，通过 p->prev 直接获取前驱节点，无需像单链表那样提前遍历查找，效率更高（O(1) vs O(n)）。

三、栈：先进后出（LIFO）的数据结构

3.1 栈的核心概念

栈是一种受限的线性数据结构，仅允许在一端（栈顶）进行插入和删除操作，另一端（栈底）固定不动，遵循"先进后出"（Last In First Out，LIFO）原则。

栈的核心操作：

• 入栈（Push）：向栈顶添加元素
• 出栈（Pop）：从栈顶移除元素
• 取栈顶元素（Top）：获取栈顶元素但不删除
• 判空（IsEmpty）：判断栈是否为空
• 判满（IsFull）：判断栈是否已满（仅数组实现需要）

💡 生活中的栈示例：叠盘子（只能从最上面拿盘子，新盘子也只能放在最上面）、浏览器的前进/后退功能（最新打开的页面先关闭）。

3.2 栈的两种实现方式

3.2.1 基于数组的栈实现（静态栈）

数组实现的栈结构简单、效率高，但容量固定（需预先指定最大大小），适合已知数据量的场景。

1. 定义栈结构体

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 栈的最大容量

// 数组栈结构体
typedef struct {
    int data[MAX_SIZE]; // 存储栈元素的数组
    int top; // 栈顶指针（-1 表示栈空，top==MAX_SIZE-1 表示栈满）
} ArrayStack;

2. 栈的初始化

// 初始化栈（栈空）
void initArrayStack(ArrayStack* stack) {
    stack->top = -1; // 栈顶指针设为 -1，表示无元素
}

3. 入栈操作

// 入栈：向栈顶添加元素
int pushArrayStack(ArrayStack* stack, int data) {
    // 判满
    if (stack->top == MAX_SIZE - 1) {
        printf("栈满，无法入栈！\n");
        return -1;
    }
    stack->top++; // 栈顶指针上移
    stack->data[stack->top] = data; // 存入数据
    return 0;
}

4. 出栈操作

// 出栈：从栈顶移除元素，返回移除的元素
int popArrayStack(ArrayStack* stack) {
    // 判空
    if (stack->top == -1) {
        printf("栈空，无法出栈！\n");
        return -1; // 用 -1 表示出栈失败（假设数据不包含 -1）
    }
    int data = stack->data[stack->top]; // 取出栈顶元素
    stack->top--; // 栈顶指针下移
    return data;
}

5. 取栈顶元素

// 取栈顶元素（不删除）
int getTopArrayStack(ArrayStack* stack) {
    if (stack->top == -1) {
        printf("栈空，无栈顶元素！\n");
        return -1;
    }
    return stack->data[stack->top];
}

6. 判空与遍历

// 判断栈是否为空（空返回 1，非空返回 0）
int isEmptyArrayStack(ArrayStack* stack) {
    return stack->top == -1 ? 1 : 0;
}

// 遍历栈（从栈顶到栈底）
void traverseArrayStack(ArrayStack* stack) {
    if (isEmptyArrayStack(stack)) {
        printf("栈空！\n");
        return;
    }
    printf("栈元素（栈顶->栈底）：");
    for (int i = stack->top; i >= 0; i--) {
        printf("%d ", stack->data[i]);
    }
    printf("\n");
}

7. 数组栈测试案例

int main() {
    ArrayStack stack;
    initArrayStack(&stack);
    
    // 入栈
    pushArrayStack(&stack, 10);
    pushArrayStack(&stack, 20);
    pushArrayStack(&stack, 30);
    pushArrayStack(&stack, 40);
    printf("入栈 10、20、30、40 后：");
    traverseArrayStack(&stack); // 输出：40 30 20 10
    
    // 取栈顶元素
    int top = getTopArrayStack(&stack);
    printf("当前栈顶元素：%d\n", top); // 输出：40
    
    // 出栈
    int popData = popArrayStack(&stack);
    printf("出栈元素：%d\n", popData); // 输出：40
    printf("出栈后：");
    traverseArrayStack(&stack); // 输出：30 20 10
    
    // 继续入栈到满
    for (int i = 50; i <= 100; i += 10) {
        pushArrayStack(&stack, i);
    }
    printf("多次入栈后：");
    traverseArrayStack(&stack); // 输出：100 90 80 70 60 50 30 20 10（共 9 个元素，MAX_SIZE=100，未装满）
    
    // 测试栈满
    for (int i = 110; i <= 200; i += 10) {
        pushArrayStack(&stack, i);
    }
    printf("栈满后尝试入栈 200：");
    pushArrayStack(&stack, 200); // 输出：栈满，无法入栈！
    
    return 0;
}

3.2.2 基于链表的栈实现（动态栈）

链表实现的栈无需预先指定容量，可动态扩容，适合数据量不确定的场景，核心是利用单链表的头插法（入栈）和头删法（出栈），效率均为 O(1)。

1. 定义链表栈节点结构体

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

// 链表栈节点结构体
typedef struct StackNode {
    int data; // 数据域
    struct StackNode* next; // 指针域（指向栈底方向的节点）
} StackNode, *LinkedStack;

2. 栈的初始化

// 初始化栈（栈空，头指针为 NULL）
void initLinkedStack(LinkedStack* stack) {
    *stack = NULL; // 栈顶指针为 NULL，表示栈空
}

3. 入栈操作（头插法）

// 入栈：向栈顶添加节点（头插法）
int pushLinkedStack(LinkedStack* stack, int data) {
    // 创建新节点
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = *stack; // 新节点指向原栈顶节点
    *stack = newNode; // 栈顶指针指向新节点
    return 0;
}

4. 出栈操作（头删法）

// 出栈：移除栈顶节点，返回数据
int popLinkedStack(LinkedStack* stack) {
    // 判空
    if (*stack == NULL) {
        printf("栈空，无法出栈！\n");
        return -1;
    }
    StackNode* temp = *stack; // 保存栈顶节点
    int data = temp->data; // 取出数据
    *stack = temp->next; // 栈顶指针指向栈底方向的下一个节点
    free(temp); // 释放栈顶节点内存
    temp = NULL;
    return data;
}

5. 取栈顶元素与遍历

// 取栈顶元素（不删除）
int getTopLinkedStack(LinkedStack* stack) {
    if (*stack == NULL) {
        printf("栈空，无栈顶元素！\n");
        return -1;
    }
    return (*stack)->data;
}

// 遍历栈（从栈顶到栈底）
void traverseLinkedStack(LinkedStack* stack) {
    if (*stack == NULL) {
        printf("栈空！\n");
        return;
    }
    StackNode* p = *stack;
    printf("栈元素（栈顶->栈底）：");
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

6. 链表栈的销毁

// 销毁链表栈，释放所有节点内存
void destroyLinkedStack(LinkedStack* stack) {
    StackNode* p = *stack;
    StackNode* temp = NULL;
    while (p != NULL) {
        temp = p;
        p = p->next;
        free(temp);
    }
    *stack = NULL;
}

7. 链表栈测试案例

int main() {
    LinkedStack stack;
    initLinkedStack(&stack);
    
    // 入栈
    pushLinkedStack(&stack, 5);
    pushLinkedStack(&stack, 15);
    pushLinkedStack(&stack, 25);
    pushLinkedStack(&stack, 35);
    printf("入栈 5、15、25、35 后：");
    traverseLinkedStack(&stack); // 输出：35 25 15 5
    
    // 取栈顶
    int top = getTopLinkedStack(&stack);
    printf("栈顶元素：%d\n", top); // 输出：35
    
    // 出栈
    int pop1 = popLinkedStack(&stack);
    int pop2 = popLinkedStack(&stack);
    printf("出栈两次，元素分别为：%d、%d\n", pop1, pop2); // 输出：35、25
    printf("出栈后：");
    traverseLinkedStack(&stack); // 输出：15 5
    
    // 继续入栈（动态扩容）
    for (int i = 45; i <= 105; i += 10) {
        pushLinkedStack(&stack, i);
    }
    printf("动态入栈后：");
    traverseLinkedStack(&stack); // 输出：105 95 85 75 65 55 45 15 5（无容量限制）
    
    // 销毁栈
    destroyLinkedStack(&stack);
    printf("销毁后：");
    traverseLinkedStack(&stack); // 输出：栈空！
    
    return 0;
}

3.3 栈的应用场景实战：后缀表达式求值

后缀表达式（逆波兰表达式）是一种不依赖括号的数学表达式表示法，运算符在操作数之后（如"3 4 + 5 *"等价于"(3+4)*5"），适合用栈进行求值，步骤如下：

1. 遍历后缀表达式的每个元素
2. 若为操作数，入栈
3. 若为运算符，出栈两个操作数（后出栈的为左操作数），计算结果后入栈
4. 遍历结束后，栈中剩余的唯一元素即为表达式结果

实战代码实现

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h> // 包含 isdigit 函数（判断是否为数字）
#define MAX_EXPR_LEN 100 // 表达式最大长度
#define STACK_SIZE 50 // 栈容量

// 栈结构体（简化版数组栈）
typedef struct {
    int data[STACK_SIZE];
    int top;
} CalcStack;

// 初始化栈
void initCalcStack(CalcStack* stack) {
    stack->top = -1;
}

// 入栈
int pushCalc(CalcStack* stack, int data) {
    if (stack->top == STACK_SIZE - 1) {
        printf("栈满！\n");
        return -1;
    }
    stack->data[++stack->top] = data;
    return 0;
}

// 出栈
int popCalc(CalcStack* stack) {
    if (stack->top == -1) {
        printf("栈空！\n");
        return -1;
    }
    return stack->data[stack->top--];
}

// 后缀表达式求值（表达式以空格分隔，如"3 4 + 5 *"）
int evaluatePostfix(char* expr) {
    CalcStack stack;
    initCalcStack(&stack);
    int i = 0;
    while (expr[i] != '\0') {
        // 跳过空格
        if (expr[i] == ' ') {
            i++;
            continue;
        }
        // 若为数字（可能是多位数）
        if (isdigit(expr[i])) {
            int num = 0; // 处理多位数
            while (isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            pushCalc(&stack, num);
        } else {
            // 若为运算符，出栈两个操作数
            int op2 = popCalc(&stack); // 右操作数（后入栈，先出栈）
            int op1 = popCalc(&stack); // 左操作数（先入栈，后出栈）
            int result = 0;
            // 根据运算符计算
            switch (expr[i]) {
                case '+': result = op1 + op2; break;
                case '-': result = op1 - op2; break;
                case '*': result = op1 * op2; break;
                case '/':
                    if (op2 == 0) {
                        printf("除数不能为 0！\n");
                        exit(EXIT_FAILURE);
                    }
                    result = op1 / op2; break;
                default: printf("非法运算符：%c\n", expr[i]); exit(EXIT_FAILURE);
            }
            pushCalc(&stack, result); // 结果入栈
            i++;
        }
    }
    // 最终栈中只剩一个元素，即为结果
    return popCalc(&stack);
}

int main() {
    char expr[MAX_EXPR_LEN];
    printf("请输入后缀表达式（操作数和运算符以空格分隔）：");
    fgets(expr, MAX_EXPR_LEN, stdin); // 读取表达式（包含空格）
    
    // 移除 fgets 读取的换行符
    int len = strlen(expr);
    if (expr[len - 1] == '\n') {
        expr[len - 1] = '\0';
    }
    
    int result = evaluatePostfix(expr);
    printf("表达式结果：%d\n", result);
    return 0;
}

测试输入：3 4 + 5 *，输出结果：35（正确，(3+4)*5=35）； 测试输入：10 5 2 / - 3 *，输出结果：24（正确，(10 - 5/2)*3= (10-2)*3=24，整数除法 5/2=2）。

✅ 该案例充分体现了栈"先进后出"的特性，是栈在实际开发中的典型应用（如编译器的表达式解析、计算器功能等）。

四、队列：先进先出（FIFO）的数据结构

4.1 队列的核心概念

队列是另一种受限的线性数据结构，允许在一端（队尾）进行插入操作，在另一端（队头）进行删除操作，遵循"先进先出"（First In First Out，FIFO）原则。

队列的核心操作：

• 入队（Enqueue）：向队尾添加元素
• 出队（Dequeue）：从队头移除元素
• 取队头元素（Front）：获取队头元素但不删除
• 判空（IsEmpty）：判断队列是否为空
• 判满（IsFull）：判断队列是否已满（仅数组实现需要）

💡 生活中的队列示例：排队买票（先排队的先买票）、打印机的打印任务队列（先提交的任务先打印）、消息队列（先发送的消息先处理）。

4.2 队列的两种实现方式

4.2.1 基于数组的队列实现（循环队列）

普通数组队列存在"假溢出"问题（队尾已到数组末尾，但队头前仍有空闲空间），因此实际开发中通常使用循环队列（数组首尾相连），充分利用数组空间。

1. 循环队列结构体定义

#include <stdio.h>
#include <stdlib.h>
#define QUEUE_SIZE 10 // 队列最大容量（实际可用容量为 QUEUE_SIZE-1，用于区分空和满）

typedef struct {
    int data[QUEUE_SIZE]; // 存储队列元素的数组
    int front; // 队头指针（指向队头元素）
    int rear; // 队尾指针（指向队尾元素的下一个位置）
} CircularQueue;

⚠️ 循环队列的关键设计：用(rear + 1) % QUEUE_SIZE == front表示队列满，用front == rear表示队列空，因此数组实际可用容量为QUEUE_SIZE - 1（牺牲一个位置避免空满混淆）。

2. 循环队列的初始化

// 初始化循环队列（空队列）
void initCircularQueue(CircularQueue* queue) {
    queue->front = 0;
    queue->rear = 0;
}

3. 判空与判满

// 判断队列是否为空（空返回 1，非空返回 0）
int isEmptyCircularQueue(CircularQueue* queue) {
    return queue->front == queue->rear ? 1 : 0;
}

// 判断队列是否已满（满返回 1，未满返回 0）
int isFullCircularQueue(CircularQueue* queue) {
    return (queue->rear + 1) % QUEUE_SIZE == queue->front ? 1 : 0;
}

4. 入队操作

// 入队：向队尾添加元素
int enqueueCircular(CircularQueue* queue, int data) {
    if (isFullCircularQueue(queue)) {
        printf("队列满，无法入队！\n");
        return -1;
    }
    queue->data[queue->rear] = data; // 存入队尾位置
    queue->rear = (queue->rear + 1) % QUEUE_SIZE; // 队尾指针循环后移
    return 0;
}

5. 出队操作

// 出队：从队头移除元素，返回元素值
int dequeueCircular(CircularQueue* queue) {
    if (isEmptyCircularQueue(queue)) {
        printf("队列为空，无法出队！\n");
        return -1;
    }
    int data = queue->data[queue->front]; // 取出队头元素
    queue->front = (queue->front + 1) % QUEUE_SIZE; // 队头指针循环后移
    return data;
}

6. 取队头元素与遍历

// 取队头元素（不删除）
int getFrontCircular(CircularQueue* queue) {
    if (isEmptyCircularQueue(queue)) {
        printf("队列为空，无队头元素！\n");
        return -1;
    }
    return queue->data[queue->front];
}

// 遍历队列（从队头到队尾）
void traverseCircularQueue(CircularQueue* queue) {
    if (isEmptyCircularQueue(queue)) {
        printf("队列为空！\n");
        return;
    }
    int i = queue->front;
    printf("队列元素（队头->队尾）：");
    while (i != queue->rear) {
        printf("%d ", queue->data[i]);
        i = (i + 1) % QUEUE_SIZE; // 循环移动
    }
    printf("\n");
}

7. 循环队列测试案例

int main() {
    CircularQueue queue;
    initCircularQueue(&queue);
    
    // 入队
    enqueueCircular(&queue, 10);
    enqueueCircular(&queue, 20);
    enqueueCircular(&queue, 30);
    enqueueCircular(&queue, 40);
    printf("入队 10、20、30、40 后：");
    traverseCircularQueue(&queue); // 输出：10 20 30 40
    
    // 取队头
    int front = getFrontCircular(&queue);
    printf("当前队头元素：%d\n", front); // 输出：10
    
    // 出队
    int deq1 = dequeueCircular(&queue);
    int deq2 = dequeueCircular(&queue);
    printf("出队两次，元素分别为：%d、%d\n", deq1, deq2); // 输出：10、20
    printf("出队后：");
    traverseCircularQueue(&queue); // 输出：30 40
    
    // 继续入队（测试循环复用空间）
    enqueueCircular(&queue, 50);
    enqueueCircular(&queue, 60);
    enqueueCircular(&queue, 70);
    enqueueCircular(&queue, 80);
    printf("入队 50、60、70、80 后：");
    traverseCircularQueue(&queue); // 输出：30 40 50 60 70 80（QUEUE_SIZE=10，可用 9 个位置，当前 6 个元素）
    
    // 测试队列满
    enqueueCircular(&queue, 90);
    enqueueCircular(&queue, 100);
    printf("入队 90、100 后（队列满）：");
    traverseCircularQueue(&queue); // 输出：30 40 50 60 70 80 90 100（8 个元素，剩余 1 个位置为空闲但标记为满）
    enqueueCircular(&queue, 110); // 输出：队列满，无法入队！
    
    return 0;
}

4.2.2 基于链表的队列实现（动态队列）

链表实现的队列无需考虑容量限制，动态扩容，队头和队尾分别用指针指向，入队操作在队尾，出队操作在队头，效率均为 O(1)。

1. 链表队列节点与队列结构体定义

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

// 队列节点结构体
typedef struct QueueNode {
    int data; // 数据域
    struct QueueNode* next; // 指针域（指向队尾方向的下一个节点）
} QueueNode;

// 队列结构体（包含队头和队尾指针）
typedef struct {
    QueueNode* front; // 队头指针（指向队头节点）
    QueueNode* rear; // 队尾指针（指向队尾节点）
} LinkedQueue;

2. 链表队列的初始化

// 初始化队列（空队列，队头和队尾均为 NULL）
void initLinkedQueue(LinkedQueue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

3. 入队操作（队尾插入）

// 入队：向队尾添加节点
int enqueueLinked(LinkedQueue* queue, int data) {
    // 创建新节点
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL; // 队尾节点的 next 为 NULL
    
    // 若队列为空，队头和队尾都指向新节点
    if (queue->front == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        // 队尾节点的 next 指向新节点，队尾指针后移
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    return 0;
}

4. 出队操作（队头删除）

// 出队：从队头移除节点，返回数据
int dequeueLinked(LinkedQueue* queue) {
    // 判空
    if (queue->front == NULL) {
        printf("队列为空，无法出队！\n");
        return -1;
    }
    QueueNode* temp = queue->front; // 保存队头节点
    int data = temp->data; // 取出数据
    
    // 若队列中只有一个节点，出队后队头和队尾均为 NULL
    if (queue->front == queue->rear) {
        queue->front = NULL;
        queue->rear = NULL;
    } else {
        queue->front = temp->next; // 队头指针后移
    }
    free(temp); // 释放队头节点内存
    temp = NULL;
    return data;
}

5. 取队头元素与遍历

// 取队头元素（不删除）
int getFrontLinked(LinkedQueue* queue) {
    if (queue->front == NULL) {
        printf("队列为空，无队头元素！\n");
        return -1;
    }
    return queue->front->data;
}

// 遍历队列（从队头到队尾）
void traverseLinkedQueue(LinkedQueue* queue) {
    if (queue->front == NULL) {
        printf("队列为空！\n");
        return;
    }
    QueueNode* p = queue->front;
    printf("队列元素（队头->队尾）：");
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

6. 链表队列的销毁

// 销毁链表队列，释放所有节点内存
void destroyLinkedQueue(LinkedQueue* queue) {
    QueueNode* p = queue->front;
    QueueNode* temp = NULL;
    while (p != NULL) {
        temp = p;
        p = p->next;
        free(temp);
    }
    queue->front = NULL;
    queue->rear = NULL;
}

7. 链表队列测试案例

int main() {
    LinkedQueue queue;
    initLinkedQueue(&queue);
    
    // 入队
    enqueueLinked(&queue, 1);
    enqueueLinked(&queue, 2);
    enqueueLinked(&queue, 3);
    enqueueLinked(&queue, 4);
    printf("入队 1、2、3、4 后：");
    traverseLinkedQueue(&queue); // 输出：1 2 3 4
    
    // 取队头
    int front = getFrontLinked(&queue);
    printf("当前队头元素：%d\n", front); // 输出：1
    
    // 出队
    int deq1 = dequeueLinked(&queue);
    int deq2 = dequeueLinked(&queue);
    printf("出队两次，元素分别为：%d、%d\n", deq1, deq2); // 输出：1、2
    printf("出队后：");
    traverseLinkedQueue(&queue); // 输出：3 4
    
    // 继续入队（动态扩容）
    for (int i = 5; i <= 10; i++) {
        enqueueLinked(&queue, i);
    }
    printf("入队 5-10 后：");
    traverseLinkedQueue(&queue); // 输出：3 4 5 6 7 8 9 10（无容量限制）
    
    // 销毁队列
    destroyLinkedQueue(&queue);
    printf("销毁后：");
    traverseLinkedQueue(&queue); // 输出：队列为空！
    
    return 0;
}

4.3 队列的应用场景实战：任务调度队列

在嵌入式系统、服务器开发中，任务调度是常见场景，多个任务按提交顺序依次执行，适合用队列实现。以下是一个简化的任务调度队列案例：

实战代码实现

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

// 任务结构体（存储任务 ID 和任务描述）
typedef struct Task {
    int taskId; // 任务 ID
    char taskName[50]; // 任务名称
} Task;

// 队列节点结构体（存储任务数据）
typedef struct TaskNode {
    Task task; // 任务数据
    struct TaskNode* next; // 指针域
} TaskNode;

// 任务队列结构体
typedef struct {
    TaskNode* front; // 队头指针
    TaskNode* rear; // 队尾指针
} TaskQueue;

// 初始化任务队列
void initTaskQueue(TaskQueue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

// 任务入队
int enqueueTask(TaskQueue* queue, int taskId, const char* taskName) {
    TaskNode* newNode = (TaskNode*)malloc(sizeof(TaskNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    // 赋值任务数据
    newNode->task.taskId = taskId;
    strncpy(newNode->task.taskName, taskName, sizeof(newNode->task.taskName) - 1);
    newNode->task.taskName[sizeof(newNode->task.taskName) - 1] = '\0'; // 确保字符串结束
    newNode->next = NULL;
    
    if (queue->front == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    printf("任务入队：ID=%d, 名称=%s\n", taskId, taskName);
    return 0;
}

// 任务出队（执行任务）
int dequeueTask(TaskQueue* queue) {
    if (queue->front == NULL) {
        printf("无待执行任务！\n");
        return -1;
    }
    TaskNode* temp = queue->front;
    Task task = temp->task; // 执行任务（简化为打印任务信息）
    printf("执行任务：ID=%d, 名称=%s\n", task.taskId, task.taskName);
    
    // 更新队列
    if (queue->front == queue->rear) {
        queue->front = NULL;
        queue->rear = NULL;
    } else {
        queue->front = temp->next;
    }
    free(temp);
    temp = NULL;
    return 0;
}

// 遍历待执行任务
void traverseTaskQueue(TaskQueue* queue) {
    if (queue->front == NULL) {
        printf("待执行任务为空！\n");
        return;
    }
    TaskNode* p = queue->front;
    printf("待执行任务列表：");
    while (p != NULL) {
        printf("[ID=%d, 名称=%s] ", p->task.taskId, p->task.taskName);
        p = p->next;
    }
    printf("\n");
}

// 销毁任务队列
void destroyTaskQueue(TaskQueue* queue) {
    TaskNode* p = queue->front;
    TaskNode* temp = NULL;
    while (p != NULL) {
        temp = p;
        p = p->next;
        free(temp);
    }
    queue->front = NULL;
    queue->rear = NULL;
    printf("任务队列已销毁！\n");
}

int main() {
    TaskQueue taskQueue;
    initTaskQueue(&taskQueue);
    
    // 提交任务（入队）
    enqueueTask(&taskQueue, 1, "系统初始化");
    enqueueTask(&taskQueue, 2, "读取配置文件");
    enqueueTask(&taskQueue, 3, "连接数据库");
    enqueueTask(&taskQueue, 4, "处理用户请求");
    enqueueTask(&taskQueue, 5, "生成日志文件");
    
    // 查看待执行任务
    traverseTaskQueue(&taskQueue);
    
    // 执行任务（出队）
    printf("\n开始执行任务：\n");
    dequeueTask(&taskQueue);
    dequeueTask(&taskQueue);
    dequeueTask(&taskQueue);
    
    // 查看剩余任务
    printf("\n剩余待执行任务：\n");
    traverseTaskQueue(&taskQueue);
    
    // 继续执行剩余任务
    printf("\n继续执行任务：\n");
    dequeueTask(&taskQueue);
    dequeueTask(&taskQueue);
    
    // 尝试执行无任务
    dequeueTask(&taskQueue);
    
    // 销毁队列
    destroyTaskQueue(&taskQueue);
    
    return 0;
}

运行结果：

任务入队：ID=1, 名称=系统初始化 任务入队：ID=2, 名称=读取配置文件 任务入队：ID=3, 名称=连接数据库 任务入队：ID=4, 名称=处理用户请求 任务入队：ID=5, 名称=生成日志文件 待执行任务列表：[ID=1, 名称=系统初始化] [ID=2, 名称=读取配置文件] [ID=3, 名称=连接数据库] [ID=4, 名称=处理用户请求] [ID=5, 名称=生成日志文件] 开始执行任务： 执行任务：ID=1, 名称=系统初始化 执行任务：ID=2, 名称=读取配置文件 执行任务：ID=3, 名称=连接数据库 剩余待执行任务： 待执行任务列表：[ID=4, 名称=处理用户请求] [ID=5, 名称=生成日志文件] 继续执行任务： 执行任务：ID=4, 名称=处理用户请求 执行任务：ID=5, 名称=生成日志文件 无待执行任务！ 任务队列已销毁！ 

✅ 该案例模拟了真实的任务调度场景，任务按提交顺序依次执行，充分体现了队列"先进先出"的特性，类似的实现可用于服务器的请求处理、嵌入式系统的任务调度等场景。

五、数据结构选型与性能对比

5.1 链表、栈、队列的核心特性对比

5.2 实现方式选型建议

💡 若数据量固定，优先选择数组实现（栈/队列），效率更高（数组随机访问速度快，无指针开销）； 💡 若数据量不确定，优先选择链表实现（栈/队列/链表），避免溢出问题； 💡 若需要双向遍历或频繁删除指定节点，优先选择双向链表； 💡 若需要循环复用空间（如缓冲区），优先选择循环队列； 💡 若需要"先进后出"特性（如表达式求值、递归调用），选择栈； 💡 若需要"先进先出"特性（如任务调度、消息传递），选择队列。

5.3 常见问题与优化技巧

5.3.1 链表常见问题

1. 内存泄漏：动态分配的节点未调用 free 释放，解决方案：使用完毕后遍历链表，逐个释放节点；
2. 野指针：指针指向已释放的内存或未初始化的内存，解决方案：释放节点后将指针设为 NULL，初始化指针时明确指向；
3. 链表为空判断：单链表需判断 head->next == NULL，双向链表需判断 head->next == NULL && head->prev == NULL；
4. 中间插入/删除：单链表需找到前驱节点，双向链表可直接通过节点的 prev 指针获取前驱，效率更高。

5.3.2 栈与队列常见问题

1. 数组栈/队列溢出：数组实现的栈/队列容量固定，解决方案：使用链表实现或动态扩容数组（重新分配更大的数组，复制原数据）；
2. 循环队列空满判断：必须使用 front == rear（空）和 (rear+1)%size == front（满），避免混淆；
3. 栈的多位数处理：如后缀表达式求值中，需处理多位数（连续数字字符组合），解决方案：遍历到数字时，累积计算多位数的值；
4. 队列的线程安全：多线程环境下，入队和出队操作需加锁（如 pthread_mutex_t），避免并发冲突。

六、本章总结

本章详细讲解了 C 语言中三种核心数据结构：链表、栈和队列，从原理到实现，再到实战应用，逐步深入，重点内容包括：

1. 单链表的定义、初始化、增删改查操作，以及双向链表的扩展实现；
2. 栈的"先进后出"特性，数组栈和链表栈的实现，以及后缀表达式求值的实战应用；
3. 队列的"先进先出"特性，循环队列和链表队列的实现，以及任务调度队列的实战应用；
4. 数据结构的选型原则、性能对比，以及常见问题的解决方案。

💡 数据结构是 C 语言开发的核心基础，掌握链表、栈、队列的实现与应用，能为后续学习更复杂的数据结构（如树、图、哈希表）打下坚实基础。实际开发中，应根据具体场景选择合适的数据结构，兼顾效率和空间开销。

建议读者多动手编写代码，反复调试本章的案例，重点掌握动态内存分配（malloc/free）和指针操作，这是 C 语言实现复杂数据结构的关键。同时，尝试将这些数据结构应用到自己的项目中（如实现一个简单的缓存系统、消息队列等），加深理解和记忆。