C 语言指针与复杂数据结构：链表、栈与队列实现

运行结果：

学号：101，姓名：张三，成绩：92.5
学号：102，姓名：李四，成绩：88.0

[注意] 堆上的结构体必须通过 malloc 分配内存，且使用后需通过 free 释放，否则会导致内存泄漏；释放后需将指针置空，避免野指针访问。

1.2.2 typedef 简化结构体指针声明

频繁使用 struct 结构体名 * 声明指针会显得繁琐，通过 typedef 为结构体类型起别名，可极大简化代码：

// 方式 1：先定义结构体，再 typedef
struct Student {
    int id;
    char name[20];
};
typedef struct Student Student; // 别名 Student，后续可直接用 Student 代替 struct Student

// 方式 2：定义结构体时直接 typedef（推荐）
typedef struct Student {
    int id;
    char name[20];
    struct Student* next;
} Student, *PStudent; // Student 是结构体类型别名，PStudent 是结构体指针类型别名

示例 2：typedef 简化结构体指针使用

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

// 定义结构体并起别名
typedef struct Student {
    int id;
    char name[20];
    float score;
    struct Student* next;
} Student, *PStudent; // PStudent = struct Student*

// 函数：创建学生节点（返回结构体指针）
PStudent createStudent(int id, const char* name, float score) {
    PStudent pStu = (PStudent)malloc(sizeof(Student));
    if(pStu == NULL) {
        printf("[注意] 节点创建失败！\n");
        return NULL;
    }
    pStu->id = id;
    strcpy(pStu->name, name);
    pStu->score = score;
    pStu->next = NULL; // 初始化 next 指针为 NULL，避免野指针
    return pStu;
}

// 函数：打印学生信息
void printStudent(PStudent pStu) {
    if(pStu != NULL) {
        printf("学号：%d，姓名：%s，成绩：%.1f\n", pStu->id, pStu->name, pStu->score);
    }
}

int main() {
    PStudent pStu1 = createStudent(101, "王五", 95.0);
    PStudent pStu2 = createStudent(102, "赵六", 89.5);
    printStudent(pStu1);
    printStudent(pStu2);
    
    // 释放内存
    free(pStu1);
    free(pStu2);
    pStu1 = NULL;
    pStu2 = NULL;
    return 0;
}

运行结果：

学号：101，姓名：王五，成绩：95.0
学号：102，姓名：赵六，成绩：89.5

[成功] 结论：typedef 不仅简化了结构体指针的声明，还提升了代码的可读性和可维护性，是复杂数据结构开发中的必备技巧。

1.3 链表：动态数据结构的核心

链表是一种线性数据结构，其数据单元（节点）通过指针串联，节点在内存中无需连续存储——这种特性使其支持动态扩容（无需预先指定大小），插入、删除操作效率高（无需移动大量元素）。链表主要分为单链表、双向链表、循环链表，本节重点讲解最常用的单链表和双向链表。

1.3.1 单链表的实现与基础操作

单链表的每个节点包含'数据域'和'指针域'：数据域存储数据，指针域（next）指向后一个节点，最后一个节点的 next 指针为 NULL（表示链表结尾）。

单链表的核心操作

1. 链表初始化：创建头节点（或空链表）；
2. 节点插入：头插法、尾插法、指定位置插入；
3. 节点删除：按位置删除、按值删除；
4. 链表遍历：遍历所有节点并访问数据；
5. 链表查找：按值查找、按位置查找；
6. 链表销毁：释放所有节点的内存。

示例 3：单链表的完整实现

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

// 定义单链表节点结构体
typedef struct ListNode {
    int data;         // 数据域
    struct ListNode* next; // 指针域：指向后一个节点
} ListNode, *LinkList;

// 1. 链表初始化：创建空链表（头节点为 NULL）
LinkList initLinkList() {
    return NULL; // 空链表的头指针为 NULL
}

// 2. 节点插入：尾插法（在链表末尾添加节点）
int insertTail(LinkList *head, int data) {
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    if(newNode == NULL) {
        printf("[注意] 节点内存分配失败！\n");
        return -1;
    }
    newNode->data = data;
    newNode->next = NULL;
    
    // 情况 1：链表为空（头指针为 NULL），新节点作为头节点
    if(*head == NULL) {
        *head = newNode;
        return 0;
    }
    
    // 情况 2：链表非空，遍历到末尾节点
    ListNode *p = *head;
    while(p->next != NULL) {
        p = p->next; // 移动到下一个节点
    }
    p->next = newNode; // 末尾节点的 next 指向新节点
    return 0;
}

// 3. 节点插入：头插法（在链表头部添加节点）
int insertHead(LinkList *head, int data) {
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    if(newNode == NULL) {
        printf("[注意] 节点内存分配失败！\n");
        return -1;
    }
    newNode->data = data;
    // 新节点的 next 指向原头节点，头指针指向新节点
    newNode->next = *head;
    *head = newNode;
    return 0;
}

// 4. 节点插入：指定位置插入（位置从 1 开始）
int insertPos(LinkList *head, int pos, int data) {
    // 检查位置合法性（pos < 1 或 链表为空但 pos > 1）
    if(pos < 1 || (*head == NULL && pos > 1)) {
        printf("[注意] 插入位置非法！\n");
        return -1;
    }
    
    // 位置 1：等价于头插法
    if(pos == 1) {
        return insertHead(head, data);
    }
    
    // 查找第 pos-1 个节点（插入位置的前驱节点）
    ListNode *p = *head;
    int count = 1;
    while(p != NULL && count < pos - 1) {
        p = p->next;
        count++;
    }
    
    // 若 pos 超过链表长度（p 为 NULL），插入失败
    if(p == NULL) {
        printf("[注意] 插入位置超出链表长度！\n");
        return -1;
    }
    
    // 创建新节点并插入
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    if(newNode == NULL) {
        printf("[注意] 节点内存分配失败！\n");
        return -1;
    }
    newNode->data = data;
    newNode->next = p->next; // 新节点的 next 指向前驱节点的原后继
    p->next = newNode;       // 前驱节点的 next 指向新节点
    return 0;
}

// 5. 链表遍历：打印所有节点数据
void traverseLinkList(LinkList head) {
    if(head == NULL) {
        printf("[注意] 链表为空！\n");
        return;
    }
    ListNode *p = head;
    printf("链表元素：");
    while(p != NULL) {
        printf("%d ", p->data);
        p = p->next; // 移动到下一个节点
    }
    printf("\n");
}

// 6. 链表查找：按值查找（返回第一个匹配节点的位置，从 1 开始；未找到返回 0）
int findByValue(LinkList head, int data) {
    if(head == NULL) {
        printf("[注意] 链表为空！\n");
        return 0;
    }
    ListNode *p = head;
    int pos = 1;
    while(p != NULL) {
        if(p->data == data) {
            return pos; // 找到，返回位置
        }
        p = p->next;
        pos++;
    }
    return 0; // 未找到
}

// 7. 链表查找：按位置查找（返回该位置的节点指针；位置非法返回 NULL）
ListNode *findByPos(LinkList head, int pos) {
    if(head == NULL || pos < 1) {
        printf("[注意] 链表为空或位置非法！\n");
        return NULL;
    }
    ListNode *p = head;
    int count = 1;
    while(p != NULL && count < pos) {
        p = p->next;
        count++;
    }
    return p; // 若 pos 超出长度，返回 NULL
}

// 8. 节点删除：按值删除（删除第一个匹配的节点）
int deleteByValue(LinkList *head, int data) {
    if(*head == NULL) {
        printf("[注意] 链表为空，无法删除！\n");
        return -1;
    }
    ListNode *p = *head;     // 当前节点
    ListNode *prev = NULL;   // 前驱节点
    
    // 情况 1：头节点就是要删除的节点
    if(p->data == data) {
        *head = p->next; // 头指针指向头节点的后继
        free(p);         // 释放头节点内存
        p = NULL;
        return 0;
    }
    
    // 情况 2：查找要删除的节点及其前驱节点
    while(p != NULL && p->data != data) {
        prev = p;
        p = p->next;
    }
    
    // 未找到要删除的节点
    if(p == NULL) {
        printf("[注意] 未找到值为%d的节点！\n", data);
        return -1;
    }
    
    // 前驱节点的 next 指向当前节点的后继，释放当前节点内存
    prev->next = p->next;
    free(p);
    p = NULL;
    return 0;
}

// 9. 节点删除：按位置删除（位置从 1 开始）
int deleteByPos(LinkList *head, int pos) {
    if(*head == NULL || pos < 1) {
        printf("[注意] 链表为空或位置非法！\n");
        return -1;
    }
    ListNode *p = *head;     // 当前节点
    ListNode *prev = NULL;   // 前驱节点
    
    // 情况 1：删除头节点（pos=1）
    if(pos == 1) {
        *head = p->next;
        free(p);
        p = NULL;
        return 0;
    }
    
    // 情况 2：查找第 pos 个节点及其前驱节点
    int count = 1;
    while(p != NULL && count < pos) {
        prev = p;
        p = p->next;
        count++;
    }
    
    // 位置超出链表长度
    if(p == NULL) {
        printf("[注意] 删除位置超出链表长度！\n");
        return -1;
    }
    
    // 删除节点
    prev->next = p->next;
    free(p);
    p = NULL;
    return 0;
}

// 10. 链表销毁：释放所有节点内存
void destroyLinkList(LinkList *head) {
    ListNode *p = *head;
    while(p != NULL) {
        ListNode *temp = p; // 保存当前节点
        p = p->next;        // 移动到下一个节点
        free(temp);         // 释放当前节点
        temp = NULL;
    }
    *head = NULL; // 头指针置空，避免野指针
    printf("[成功] 链表销毁成功！\n");
}

// 11. 链表长度：返回节点个数
int getLinkListLength(LinkList head) {
    int len = 0;
    ListNode *p = head;
    while(p != NULL) {
        len++;
        p = p->next;
    }
    return len;
}

// 主函数测试
int main() {
    LinkList head = initLinkList(); // 初始化空链表
    
    // 尾插法插入节点
    insertTail(&head, 10);
    insertTail(&head, 20);
    insertTail(&head, 30);
    printf("尾插法插入后：");
    traverseLinkList(head); // 输出：10 20 30
    
    // 头插法插入节点
    insertHead(&head, 5);
    printf("头插法插入后：");
    traverseLinkList(head); // 输出：5 10 20 30
    
    // 指定位置插入
    insertPos(&head, 3, 15);
    printf("位置 3 插入 15 后：");
    traverseLinkList(head); // 输出：5 10 15 20 30
    
    // 查找节点
    int pos = findByValue(head, 20);
    if(pos != 0) {
        printf("值为 20 的节点位置：%d\n", pos); // 输出：4
    } else {
        printf("未找到值为 20 的节点\n");
    }
    
    ListNode *pNode = findByPos(head, 4);
    if(pNode != NULL) {
        printf("位置 4 的节点数据：%d\n", pNode->data); // 输出：20
    }
    
    // 删除节点
    deleteByValue(&head, 15);
    printf("删除值为 15 的节点后：");
    traverseLinkList(head); // 输出：5 10 20 30
    
    deleteByPos(&head, 2);
    printf("删除位置 2 的节点后：");
    traverseLinkList(head); // 输出：5 20 30
    
    // 链表长度
    printf("链表当前长度：%d\n", getLinkListLength(head)); // 输出：3
    
    // 销毁链表
    destroyLinkList(&head);
    traverseLinkList(head); // 输出：链表为空
    return 0;
}

运行结果：

尾插法插入后：链表元素：10 20 30
头插法插入后：链表元素：5 10 20 30
位置 3 插入 15 后：链表元素：5 10 15 20 30
值为 20 的节点位置：4
位置 4 的节点数据：20
删除值为 15 的节点后：链表元素：5 10 20 30
删除位置 2 的节点后：链表元素：5 20 30
链表当前长度：3
[成功] 链表销毁成功！
[注意] 链表为空！

[提示] 技巧：单链表操作的核心是'找到目标节点的前驱节点'——插入时需让前驱节点指向新节点，新节点指向原后继；删除时需让前驱节点指向目标节点的后继，再释放目标节点内存。

1.3.2 单链表进阶问题：反转与环检测

问题 1：单链表反转

链表反转是面试高频题，核心思路是'遍历链表，逐个改变节点的 next 指针方向'，需要三个指针（prev、curr、next）记录前驱、当前、后继节点。

示例 4：单链表反转实现

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

typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode, *LinkList;

// 辅助函数：尾插法创建链表
void createLinkList(LinkList *head, int arr[], int len) {
    *head = NULL;
    for(int i = 0; i < len; i++) {
        ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
        newNode->data = arr[i];
        newNode->next = NULL;
        if(*head == NULL) {
            *head = newNode;
        } else {
            ListNode *p = *head;
            while(p->next != NULL) p = p->next;
            p->next = newNode;
        }
    }
}

// 辅助函数：遍历链表
void traverse(LinkList head) {
    ListNode *p = head;
    while(p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 单链表反转函数（迭代法）
LinkList reverseLinkList(LinkList head) {
    if(head == NULL || head->next == NULL) {
        return head; // 空链表或只有一个节点，无需反转
    }
    ListNode *prev = NULL; // 前驱节点
    ListNode *curr = head; // 当前节点
    ListNode *next = NULL; // 后继节点（临时保存）
    
    while(curr != NULL) {
        next = curr->next;      // 保存当前节点的后继
        curr->next = prev;      // 当前节点的 next 指向前驱
        prev = curr;            // 前驱节点后移
        curr = next;            // 当前节点后移
    }
    return prev; // 反转后，prev 成为新的头节点
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int len = sizeof(arr)/sizeof(arr[0]);
    LinkList head = NULL;
    createLinkList(&head, arr, len);
    printf("反转前链表：");
    traverse(head); // 输出：1 2 3 4 5
    
    LinkList reversedHead = reverseLinkList(head);
    printf("反转后链表：");
    traverse(reversedHead); // 输出：5 4 3 2 1
    
    // 销毁链表（略，参考示例 3）
    return 0;
}

运行结果：

反转前链表：1 2 3 4 5
反转后链表：5 4 3 2 1

问题 2：单链表环检测

链表环是指链表的尾节点 next 指针不指向 NULL，而是指向链表中的某个节点，导致遍历无法结束。检测链表环的经典算法是'快慢指针法'（Floyd 算法）：

• 定义两个指针：快指针（fast）每次走 2 步，慢指针（slow）每次走 1 步；
• 若链表无环，快指针会先到达 NULL；
• 若链表有环，快指针会追上慢指针（两者指向同一节点）。

示例 5：单链表环检测实现

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

typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode, *LinkList;

// 创建带环链表（尾节点指向第 pos 个节点，pos 从 1 开始）
void createCycleLinkList(LinkList *head, int arr[], int len, int pos) {
    *head = NULL;
    ListNode *cycleNode = NULL; // 存储环的入口节点
    ListNode *tail = NULL;      // 存储尾节点
    
    for(int i = 0; i < len; i++) {
        ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
        newNode->data = arr[i];
        newNode->next = NULL;
        
        if(*head == NULL) {
            *head = newNode;
        } else {
            tail->next = newNode;
        }
        tail = newNode; // 更新尾节点
        
        // 记录第 pos 个节点（环的入口）
        if(i + 1 == pos) {
            cycleNode = newNode;
        }
    }
    
    // 尾节点指向环的入口，创建环
    if(cycleNode != NULL) {
        tail->next = cycleNode;
    }
}

// 环检测：快慢指针法
int hasCycle(LinkList head) {
    if(head == NULL || head->next == NULL) {
        return 0; // 无环
    }
    ListNode *slow = head;      // 慢指针：每次走 1 步
    ListNode *fast = head->next;// 快指针：每次走 2 步
    
    while(slow != fast) {
        // 快指针到达 NULL，无环
        if(fast == NULL || fast->next == NULL) {
            return 0;
        }
        slow = slow->next;      // 慢指针走 1 步
        fast = fast->next->next;// 快指针走 2 步
    }
    return 1; // 快慢指针相遇，有环
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int len = sizeof(arr)/sizeof(arr[0]);
    LinkList head1 = NULL, head2 = NULL;
    
    // 创建无环链表（pos=0 表示无环）
    createCycleLinkList(&head1, arr, len, 0);
    printf("链表 1 是否有环：%s\n", hasCycle(head1) ? "是" : "否"); // 输出：否
    
    // 创建有环链表（尾节点指向第 2 个节点）
    createCycleLinkList(&head2, arr, len, 2);
    printf("链表 2 是否有环：%s\n", hasCycle(head2) ? "是" : "否"); // 输出：是
    
    // 注意：带环链表无法通过常规遍历销毁，需单独处理（略）
    return 0;
}

运行结果：

链表 1 是否有环：否
链表 2 是否有环：是

[成功] 结论：快慢指针法是链表环检测的最优解，时间复杂度 O(n)，空间复杂度 O(1)，无需额外存储节点信息。

1.3.3 双向链表的实现与优势

单链表的节点只有一个 next 指针，只能从前往后遍历；双向链表的每个节点增加了一个 prev 指针（指向前一个节点），支持双向遍历，插入、删除操作更灵活（无需遍历查找前驱节点）。

双向链表的核心操作

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

// 定义双向链表节点结构体
typedef struct DListNode {
    int data;
    struct DListNode* prev; // 指向前一个节点
    struct DListNode* next; // 指向后一个节点
} DListNode, *DLinkList;

// 1. 双向链表初始化（带头节点，简化操作）
DLinkList initDLinkList() {
    // 创建头节点（不存储数据）
    DListNode *head = (DListNode *)malloc(sizeof(DListNode));
    if(head == NULL) {
        printf("[注意] 头节点内存分配失败！\n");
        return NULL;
    }
    head->prev = NULL;
    head->next = NULL;
    return head;
}

// 2. 尾插法插入节点
int insertTail(DLinkList head, int data) {
    if(head == NULL) {
        printf("[注意] 链表未初始化！\n");
        return -1;
    }
    // 创建新节点
    DListNode *newNode = (DListNode *)malloc(sizeof(DListNode));
    if(newNode == NULL) {
        printf("[注意] 节点内存分配失败！\n");
        return -1;
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    
    // 遍历到尾节点（head->next 为 NULL 时，head 是尾节点）
    DListNode *p = head;
    while(p->next != NULL) {
        p = p->next;
    }
    
    // 插入新节点
    p->next = newNode;
    newNode->prev = p;
    return 0;
}

// 3. 头插法插入节点（在头节点之后插入）
int insertHead(DLinkList head, int data) {
    if(head == NULL) {
        printf("[注意] 链表未初始化！\n");
        return -1;
    }
    // 创建新节点
    DListNode *newNode = (DListNode *)malloc(sizeof(DListNode));
    if(newNode == NULL) {
        printf("[注意] 节点内存分配失败！\n");
        return -1;
    }
    newNode->data = data;
    
    // 插入逻辑：新节点在头节点和原第一个节点之间
    newNode->next = head->next;
    newNode->prev = head;
    
    if(head->next != NULL) {
        // 若原链表非空，更新原第一个节点的 prev
        head->next->prev = newNode;
    }
    head->next = newNode;
    return 0;
}

// 4. 双向遍历：正向遍历（头->尾）
void traverseForward(DLinkList head) {
    if(head == NULL || head->next == NULL) {
        printf("[注意] 链表为空！\n");
        return;
    }
    DListNode *p = head->next;
    printf("正向遍历：");
    while(p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 5. 双向遍历：反向遍历（尾->头）
void traverseBackward(DLinkList head) {
    if(head == NULL || head->next == NULL) {
        printf("[注意] 链表为空！\n");
        return;
    }
    // 遍历到尾节点
    DListNode *p = head;
    while(p->next != NULL) {
        p = p->next;
    }
    printf("反向遍历：");
    while(p != head) {
        printf("%d ", p->data);
        p = p->prev;
    }
    printf("\n");
}

// 6. 节点删除：按值删除（删除第一个匹配节点）
int deleteByValue(DLinkList head, int data) {
    if(head == NULL || head->next == NULL) {
        printf("[注意] 链表为空，无法删除！\n");
        return -1;
    }
    DListNode *p = head->next;
    while(p != NULL) {
        if(p->data == data) {
            // 前驱节点的 next 指向当前节点的后继
            p->prev->next = p->next;
            // 后继节点的 prev 指向当前节点的前驱（若后继存在）
            if(p->next != NULL) {
                p->next->prev = p->prev;
            }
            free(p);
            p = NULL;
            return 0;
        }
        p = p->next;
    }
    printf("[注意] 未找到值为%d的节点！\n", data);
    return -1;
}

// 7. 双向链表销毁
void destroyDLinkList(DLinkList *head) {
    if(*head == NULL) {
        return;
    }
    DListNode *p = *head;
    while(p != NULL) {
        DListNode *temp = p;
        p = p->next;
        free(temp);
        temp = NULL;
    }
    *head = NULL;
    printf("[成功] 双向链表销毁成功！\n");
}

// 主函数测试
int main() {
    DLinkList head = initDLinkList();
    
    // 尾插法插入节点
    insertTail(head, 10);
    insertTail(head, 20);
    insertTail(head, 30);
    traverseForward(head); // 输出：10 20 30
    traverseBackward(head); // 输出：30 20 10
    
    // 头插法插入节点
    insertHead(head, 5);
    traverseForward(head); // 输出：5 10 20 30
    traverseBackward(head); // 输出：30 20 10 5
    
    // 删除节点
    deleteByValue(head, 20);
    traverseForward(head); // 输出：5 10 30
    traverseBackward(head); // 输出：30 10 5
    
    // 销毁链表
    destroyDLinkList(&head);
    traverseForward(head); // 输出：链表为空
    return 0;
}

运行结果：

正向遍历：10 20 30
反向遍历：30 20 10
正向遍历：5 10 20 30
反向遍历：30 20 10 5
正向遍历：5 10 30
反向遍历：30 10 5
[成功] 双向链表销毁成功！
[注意] 链表为空！

[提示] 技巧：双向链表通常设计带头节点（不存储数据），可避免处理头节点为空的特殊情况，简化插入、删除逻辑；prev 指针使反向遍历和节点删除更高效（无需查找前驱节点）。

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

栈是一种遵循'先进后出'（Last In First Out）规则的线性数据结构，仅允许在一端（栈顶）进行插入（入栈）和删除（出栈）操作。栈的实现有两种方式：数组栈（基于数组）和链式栈（基于链表）。

1.4.1 数组栈的实现

数组栈基于固定大小的数组实现，优点是实现简单、访问速度快；缺点是容量固定，扩容不便。核心操作包括：初始化、入栈、出栈、取栈顶元素、判空、判满。

示例 6：数组栈的完整实现

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

#define MAX_SIZE 100 // 栈的最大容量

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

// 1. 栈初始化
void initArrayStack(ArrayStack *stack) {
    stack->top = -1; // 栈空状态
}

// 2. 判空：栈为空返回 1，否则返回 0
int isEmpty(ArrayStack *stack) {
    return stack->top == -1 ? 1 : 0;
}

// 3. 判满：栈为满返回 1，否则返回 0
int isFull(ArrayStack *stack) {
    return stack->top == MAX_SIZE - 1 ? 1 : 0;
}

// 4. 入栈：将元素压入栈顶
int push(ArrayStack *stack, int data) {
    if(isFull(stack)) {
        printf("[注意] 栈满，无法入栈！\n");
        return -1;
    }
    stack->top++;           // 栈顶指针上移
    stack->data[stack->top] = data; // 存入数据
    return 0;
}

// 5. 出栈：弹出栈顶元素，返回元素值（栈空返回 -1）
int pop(ArrayStack *stack) {
    if(isEmpty(stack)) {
        printf("[注意] 栈空，无法出栈！\n");
        return -1;
    }
    int data = stack->data[stack->top]; // 取出栈顶元素
    stack->top--;                     // 栈顶指针下移
    return data;
}

// 6. 取栈顶元素：返回栈顶元素值（不弹出，栈空返回 -1）
int getTop(ArrayStack *stack) {
    if(isEmpty(stack)) {
        printf("[注意] 栈空，无栈顶元素！\n");
        return -1;
    }
    return stack->data[stack->top];
}

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

// 8. 栈大小：返回栈中元素个数
int getStackSize(ArrayStack *stack) {
    return stack->top + 1;
}

// 主函数测试
int main() {
    ArrayStack stack;
    initArrayStack(&stack);
    
    // 入栈
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    push(&stack, 40);
    printf("入栈 4 个元素后：");
    traverseArrayStack(&stack); // 输出：40 30 20 10
    printf("栈当前大小：%d\n", getStackSize(&stack)); // 输出：4
    
    // 取栈顶元素
    int topVal = getTop(&stack);
    if(topVal != -1) {
        printf("当前栈顶元素：%d\n", topVal); // 输出：40
    }
    
    // 出栈
    int popVal = pop(&stack);
    if(popVal != -1) {
        printf("弹出的栈顶元素：%d\n", popVal); // 输出：40
    }
    printf("出栈 1 个元素后：");
    traverseArrayStack(&stack); // 输出：30 20 10
    printf("栈当前大小：%d\n", getStackSize(&stack)); // 输出：3
    
    // 继续入栈到满
    for(int i = 50; i <= 100; i += 10) {
        push(&stack, i);
    }
    printf("多次入栈后：");
    traverseArrayStack(&stack); // 输出：100 90 80 70 60 50 30 20 10
    printf("栈当前大小：%d\n", getStackSize(&stack)); // 输出：9
    
    // 测试栈满入栈
    push(&stack, 110); // 输出：栈满，无法入栈！
    return 0;
}

运行结果：

入栈 4 个元素后：栈元素（栈顶->栈底）：40 30 20 10
栈当前大小：4
当前栈顶元素：40
弹出的栈顶元素：40
出栈 1 个元素后：栈元素（栈顶->栈底）：30 20 10
栈当前大小：3
多次入栈后：栈元素（栈顶->栈底）：100 90 80 70 60 50 30 20 10
栈当前大小：9
[注意] 栈满，无法入栈！

[注意] 数组栈的容量由 MAX_SIZE 固定，若实际需求超过容量，需手动修改 MAX_SIZE 或实现动态扩容（通过 realloc 重新分配数组内存）。

1.4.2 链式栈的实现

链式栈基于单链表实现，优点是容量动态扩展（无需预先指定大小），缺点是插入、删除操作需额外的指针操作。链式栈通常将链表头部作为栈顶（入栈、出栈操作更高效）。

示例 7：链式栈的完整实现

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

// 定义链式栈节点结构体
typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode, *LinkStack;

// 1. 栈初始化：空栈的栈顶指针为 NULL
void initLinkStack(LinkStack *top) {
    *top = NULL;
}

// 2. 判空：栈为空返回 1，否则返回 0
int isLinkStackEmpty(LinkStack top) {
    return top == NULL ? 1 : 0;
}

// 3. 入栈：在栈顶（链表头部）插入节点
int linkStackPush(LinkStack *top, int data) {
    // 创建新节点
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    if(newNode == NULL) {
        printf("[注意] 节点内存分配失败！\n");
        return -1;
    }
    newNode->data = data;
    newNode->next = *top; // 新节点的 next 指向原栈顶
    *top = newNode;       // 栈顶指针指向新节点
    return 0;
}

// 4. 出栈：弹出栈顶节点，返回元素值（栈空返回 -1）
int linkStackPop(LinkStack *top) {
    if(isLinkStackEmpty(*top)) {
        printf("[注意] 栈空，无法出栈！\n");
        return -1;
    }
    StackNode *temp = *top;     // 保存栈顶节点
    int data = temp->data;      // 取出栈顶元素
    *top = temp->next;          // 栈顶指针下移
    free(temp);                 // 释放原栈顶节点内存
    temp = NULL;
    return data;
}

// 5. 取栈顶元素：返回栈顶元素值（不弹出，栈空返回 -1）
int linkStackGetTop(LinkStack top) {
    if(isLinkStackEmpty(top)) {
        printf("[注意] 栈空，无栈顶元素！\n");
        return -1;
    }
    return top->data;
}

// 6. 栈遍历：从栈顶到栈底打印元素
void traverseLinkStack(LinkStack top) {
    if(isLinkStackEmpty(top)) {
        printf("[注意] 栈空！\n");
        return;
    }
    StackNode *p = top;
    printf("栈元素（栈顶->栈底）：");
    while(p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 7. 栈大小：返回栈中元素个数
int getLinkStackSize(LinkStack top) {
    int size = 0;
    StackNode *p = top;
    while(p != NULL) {
        size++;
        p = p->next;
    }
    return size;
}

// 8. 链式栈销毁
void destroyLinkStack(LinkStack *top) {
    StackNode *p = *top;
    while(p != NULL) {
        StackNode *temp = p;
        p = p->next;
        free(temp);
        temp = NULL;
    }
    *top = NULL;
    printf("[成功] 链式栈销毁成功！\n");
}

// 主函数测试
int main() {
    LinkStack top;
    initLinkStack(&top);
    
    // 入栈
    linkStackPush(&top, 10);
    linkStackPush(&top, 20);
    linkStackPush(&top, 30);
    printf("入栈 3 个元素后：");
    traverseLinkStack(top); // 输出：30 20 10
    printf("栈当前大小：%d\n", getLinkStackSize(top)); // 输出：3
    
    // 取栈顶元素
    int topVal = linkStackGetTop(top);
    if(topVal != -1) {
        printf("当前栈顶元素：%d\n", topVal); // 输出：30
    }
    
    // 出栈
    int popVal = linkStackPop(&top);
    if(popVal != -1) {
        printf("弹出的栈顶元素：%d\n", popVal); // 输出：30
    }
    printf("出栈 1 个元素后：");
    traverseLinkStack(top); // 输出：20 10
    printf("栈当前大小：%d\n", getLinkStackSize(top)); // 输出：2
    
    // 继续入栈多个元素
    linkStackPush(&top, 40);
    linkStackPush(&top, 50);
    linkStackPush(&top, 60);
    printf("继续入栈 3 个元素后：");
    traverseLinkStack(top); // 输出：60 50 40 20 10
    printf("栈当前大小：%d\n", getLinkStackSize(top)); // 输出：5
    
    // 销毁栈
    destroyLinkStack(&top);
    traverseLinkStack(top); // 输出：栈空
    return 0;
}

运行结果：

入栈 3 个元素后：栈元素（栈顶->栈底）：30 20 10
栈当前大小：3
当前栈顶元素：30
弹出的栈顶元素：30
出栈 1 个元素后：栈元素（栈顶->栈底）：20 10
栈当前大小：2
继续入栈 3 个元素后：栈元素（栈顶->栈底）：60 50 40 20 10
栈当前大小：5
[成功] 链式栈销毁成功！
[注意] 栈空！

[成功] 结论：数组栈和链式栈各有优劣——数组栈适合元素数量固定、追求高效访问的场景；链式栈适合元素数量不确定、需要动态扩容的场景。

1.4.3 栈的应用场景：括号匹配

栈的'先进后出'特性使其非常适合解决括号匹配问题：

• 遍历字符串，遇到左括号（(、{、[）则入栈；
• 遇到右括号（)、}、]），弹出栈顶元素，判断是否为对应的左括号；
• 遍历结束后，若栈为空且所有右括号都找到匹配的左括号，则匹配成功；否则匹配失败。

示例 8：栈实现括号匹配

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

#define MAX_STACK_SIZE 100 // 数组栈实现（简化版）

typedef struct {
    char data[MAX_STACK_SIZE];
    int top;
} Stack;

void initStack(Stack *stack) {
    stack->top = -1;
}

int push(Stack *stack, char c) {
    if(stack->top == MAX_STACK_SIZE - 1) {
        return -1;
    }
    stack->data[++stack->top] = c;
    return 0;
}

char pop(Stack *stack) {
    if(stack->top == -1) {
        return '\0'; // 栈空标识
    }
    return stack->data[stack->top--];
}

int isEmpty(Stack *stack) {
    return stack->top == -1 ? 1 : 0;
}

// 判断左右括号是否匹配
int isMatch(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '{' && right == '}') ||
           (left == '[' && right == ']');
}

// 括号匹配函数：匹配成功返回 1，失败返回 0
int bracketMatch(const char* str) {
    Stack stack;
    initStack(&stack);
    int len = strlen(str);
    
    for(int i = 0; i < len; i++) {
        char c = str[i];
        // 遇到左括号，入栈
        if(c == '(' || c == '{' || c == '[') {
            push(&stack, c);
        }
        // 遇到右括号，判断匹配
        else if(c == ')' || c == '}' || c == ']') {
            char left = pop(&stack);
            if(left == '\0' || !isMatch(left, c)) {
                return 0; // 栈空（右括号多）或不匹配
            }
        }
        // 忽略其他字符
        else {
            continue;
        }
    }
    
    // 遍历结束后，栈为空则所有左括号都匹配
    return isEmpty(&stack) ? 1 : 0;
}

int main() {
    const char* str1 = "({[]})";
    const char* str2 = "({[)]}";
    const char* str3 = "((()))";
    const char* str4 = "(()";
    
    printf("字符串\"%s\"括号匹配：%s\n", str1, bracketMatch(str1) ? "成功" : "失败"); // 成功
    printf("字符串\"%s\"括号匹配：%s\n", str2, bracketMatch(str2) ? "成功" : "失败"); // 失败
    printf("字符串\"%s\"括号匹配：%s\n", str3, bracketMatch(str3) ? "成功" : "失败"); // 成功
    printf("字符串\"%s\"括号匹配：%s\n", str4, bracketMatch(str4) ? "成功" : "失败"); // 失败
    return 0;
}

运行结果：

字符串"({[]})"括号匹配：成功
字符串"({[)]}"括号匹配：失败
字符串"((()))"括号匹配：成功
字符串"(()"括号匹配：失败

[提示] 技巧：括号匹配是栈的经典应用，类似场景还包括表达式求值（前缀、中缀、后缀表达式转换）、函数调用栈等。

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

队列是一种遵循'先进先出'（First In First Out）规则的线性数据结构，允许在一端（队尾）插入元素（入队），在另一端（队头）删除元素（出队）。队列的实现有两种方式：循环队列（基于数组）和链式队列（基于链表）。

1.5.1 循环队列的实现

普通数组队列存在'假溢出'问题（队尾到达数组末尾，但队头前仍有空闲空间），循环队列通过'取模运算'将数组首尾相连，解决假溢出问题，提高内存利用率。

循环队列的核心设计：

• 定义队头指针 front（指向队头元素）和队尾指针 rear（指向队尾元素的下一个位置）；
• 队空条件：front == rear；
• 队满条件：(rear + 1) % MAX_SIZE == front（预留一个空闲位置区分队空和队满）；
• 元素个数：(rear - front + MAX_SIZE) % MAX_SIZE。

示例 9：循环队列的完整实现

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

#define MAX_QUEUE_SIZE 5 // 队列最大容量（实际可存储 4 个元素，预留 1 个区分队满）

// 定义循环队列结构体
typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front; // 队头指针
    int rear;  // 队尾指针
} CircularQueue;

// 1. 队列初始化
void initCircularQueue(CircularQueue *queue) {
    queue->front = 0;
    queue->rear = 0;
}

// 2. 判空：队列空返回 1，否则返回 0
int isQueueEmpty(CircularQueue *queue) {
    return queue->front == queue->rear ? 1 : 0;
}

// 3. 判满：队列满返回 1，否则返回 0
int isQueueFull(CircularQueue *queue) {
    return (queue->rear + 1) % MAX_QUEUE_SIZE == queue->front ? 1 : 0;
}

// 4. 入队：将元素插入队尾
int enQueue(CircularQueue *queue, int data) {
    if(isQueueFull(queue)) {
        printf("[注意] 队列满，无法入队！\n");
        return -1;
    }
    queue->data[queue->rear] = data; // 存入数据
    queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE; // 队尾指针后移（循环）
    return 0;
}

// 5. 出队：删除队头元素，返回元素值（队空返回 -1）
int deQueue(CircularQueue *queue) {
    if(isQueueEmpty(queue)) {
        printf("[注意] 队列为空，无法出队！\n");
        return -1;
    }
    int data = queue->data[queue->front]; // 取出队头元素
    queue->front = (queue->front + 1) % MAX_QUEUE_SIZE; // 队头指针后移（循环）
    return data;
}

// 6. 取队头元素：返回队头元素值（不删除，队空返回 -1）
int getQueueFront(CircularQueue *queue) {
    if(isQueueEmpty(queue)) {
        printf("[注意] 队列为空，无队头元素！\n");
        return -1;
    }
    return queue->data[queue->front];
}

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

// 8. 队列大小：返回队列中元素个数
int getQueueSize(CircularQueue *queue) {
    return (queue->rear - queue->front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

// 主函数测试
int main() {
    CircularQueue queue;
    initCircularQueue(&queue);
    
    // 入队
    enQueue(&queue, 10);
    enQueue(&queue, 20);
    enQueue(&queue, 30);
    enQueue(&queue, 40);
    printf("入队 4 个元素后：");
    traverseCircularQueue(&queue); // 输出：10 20 30 40
    printf("队列当前大小：%d\n", getQueueSize(&queue)); // 输出：4
    
    // 测试队满入队
    enQueue(&queue, 50); // 输出：队列满，无法入队！
    
    // 取队头元素
    int frontVal = getQueueFront(&queue);
    if(frontVal != -1) {
        printf("当前队头元素：%d\n", frontVal); // 输出：10
    }
    
    // 出队
    int deVal = deQueue(&queue);
    if(deVal != -1) {
        printf("出队的元素：%d\n", deVal); // 输出：10
    }
    printf("出队 1 个元素后：");
    traverseCircularQueue(&queue); // 输出：20 30 40
    printf("队列当前大小：%d\n", getQueueSize(&queue)); // 输出：3
    
    // 再次入队
    enQueue(&queue, 50);
    printf("入队元素 50 后：");
    traverseCircularQueue(&queue); // 输出：20 30 40 50
    printf("队列当前大小：%d\n", getQueueSize(&queue)); // 输出：4
    
    // 继续出队
    deQueue(&queue);
    deQueue(&queue);
    printf("连续出队 2 个元素后：");
    traverseCircularQueue(&queue); // 输出：40 50
    printf("队列当前大小：%d\n", getQueueSize(&queue)); // 输出：2
    return 0;
}

运行结果：

入队 4 个元素后：队列元素（队头->队尾）：10 20 30 40
队列当前大小：4
[注意] 队列满，无法入队！
当前队头元素：10
出队的元素：10
出队 1 个元素后：队列元素（队头->队尾）：20 30 40
队列当前大小：3
入队元素 50 后：队列元素（队头->队尾）：20 30 40 50
队列当前大小：4
连续出队 2 个元素后：队列元素（队头->队尾）：40 50
队列当前大小：2

[提示] 技巧：循环队列的核心是'取模运算'，通过 (index + 1) % MAX_SIZE 实现指针的循环移动，解决普通数组队列的假溢出问题。

1.5.2 链式队列的实现

链式队列基于单链表实现，队头指向链表的头节点，队尾指向链表的尾节点，入队操作在队尾添加节点，出队操作删除队头节点。链式队列无容量限制，适合元素数量不确定的场景。

示例 10：链式队列的完整实现

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

// 定义链式队列节点结构体
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

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

// 1. 队列初始化：创建头节点，队头和队尾都指向头节点
void initLinkQueue(LinkQueue *queue) {
    // 创建头节点（不存储数据）
    queue->front = (QueueNode *)malloc(sizeof(QueueNode));
    if(queue->front == NULL) {
        printf("[注意] 头节点内存分配失败！\n");
        return;
    }
    queue->front->next = NULL;
    queue->rear = queue->front; // 队尾初始指向头节点
}

// 2. 判空：队头和队尾指向同一节点（头节点），则队空
int isLinkQueueEmpty(LinkQueue *queue) {
    return queue->front == queue->rear ? 1 : 0;
}

// 3. 入队：在队尾添加节点
int linkQueueEnQueue(LinkQueue *queue, int data) {
    // 创建新节点
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    if(newNode == NULL) {
        printf("[注意] 节点内存分配失败！\n");
        return -1;
    }
    newNode->data = data;
    newNode->next = NULL;
    
    // 新节点插入队尾
    queue->rear->next = newNode;
    queue->rear = newNode; // 队尾指针指向新节点
    return 0;
}

// 4. 出队：删除队头节点（头节点的下一个节点）
int linkQueueDeQueue(LinkQueue *queue) {
    if(isLinkQueueEmpty(queue)) {
        printf("[注意] 队列为空，无法出队！\n");
        return -1;
    }
    QueueNode *temp = queue->front->next; // 保存队头元素节点
    int data = temp->data;                // 取出队头元素
    queue->front->next = temp->next;      // 头节点指向队头元素的下一个节点
    
    // 若队尾就是要删除的节点（队列只有一个元素），队尾指向头节点
    if(queue->rear == temp) {
        queue->rear = queue->front;
    }
    free(temp);
    temp = NULL;
    return data;
}

// 5. 取队头元素：返回队头元素值（不删除，队空返回 -1）
int linkQueueGetFront(LinkQueue *queue) {
    if(isLinkQueueEmpty(queue)) {
        printf("[注意] 队列为空，无队头元素！\n");
        return -1;
    }
    return queue->front->next->data;
}

// 6. 队列遍历：从队头到队尾打印元素
void traverseLinkQueue(LinkQueue *queue) {
    if(isLinkQueueEmpty(queue)) {
        printf("[注意] 队列为空！\n");
        return;
    }
    QueueNode *p = queue->front->next;
    printf("队列元素（队头->队尾）：");
    while(p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 7. 队列大小：返回队列中元素个数
int getLinkQueueSize(LinkQueue *queue) {
    int size = 0;
    QueueNode *p = queue->front->next;
    while(p != NULL) {
        size++;
        p = p->next;
    }
    return size;
}

// 8. 链式队列销毁
void destroyLinkQueue(LinkQueue *queue) {
    // 销毁所有元素节点
    QueueNode *p = queue->front->next;
    while(p != NULL) {
        QueueNode *temp = p;
        p = p->next;
        free(temp);
        temp = NULL;
    }
    // 销毁头节点
    free(queue->front);
    queue->front = NULL;
    queue->rear = NULL;
    printf("[成功] 链式队列销毁成功！\n");
}

// 主函数测试
int main() {
    LinkQueue queue;
    initLinkQueue(&queue);
    
    // 入队
    linkQueueEnQueue(&queue, 10);
    linkQueueEnQueue(&queue, 20);
    linkQueueEnQueue(&queue, 30);
    printf("入队 3 个元素后：");
    traverseLinkQueue(&queue); // 输出：10 20 30
    printf("队列当前大小：%d\n", getLinkQueueSize(&queue)); // 输出：3
    
    // 取队头元素
    int frontVal = linkQueueGetFront(&queue);
    if(frontVal != -1) {
        printf("当前队头元素：%d\n", frontVal); // 输出：10
    }
    
    // 出队
    int deVal = linkQueueDeQueue(&queue);
    if(deVal != -1) {
        printf("出队的元素：%d\n", deVal); // 输出：10
    }
    printf("出队 1 个元素后：");
    traverseLinkQueue(&queue); // 输出：20 30
    printf("队列当前大小：%d\n", getLinkQueueSize(&queue)); // 输出：2
    
    // 继续入队多个元素
    linkQueueEnQueue(&queue, 40);
    linkQueueEnQueue(&queue, 50);
    printf("继续入队 2 个元素后：");
    traverseLinkQueue(&queue); // 输出：20 30 40 50
    printf("队列当前大小：%d\n", getLinkQueueSize(&queue)); // 输出：4
    
    // 连续出队
    linkQueueDeQueue(&queue);
    linkQueueDeQueue(&queue);
    printf("连续出队 2 个元素后：");
    traverseLinkQueue(&queue); // 输出：40 50
    printf("队列当前大小：%d\n", getLinkQueueSize(&queue)); // 输出：2
    
    // 销毁队列
    destroyLinkQueue(&queue);
    traverseLinkQueue(&queue); // 输出：队列为空
    return 0;
}

运行结果：

入队 3 个元素后：队列元素（队头->队尾）：10 20 30
队列当前大小：3
当前队头元素：10
出队的元素：10
出队 1 个元素后：队列元素（队头->队尾）：20 30
队列当前大小：2
继续入队 2 个元素后：队列元素（队头->队尾）：20 30 40 50
队列当前大小：4
连续出队 2 个元素后：队列元素（队头->队尾）：40 50
队列当前大小：2
[成功] 链式队列销毁成功！
[注意] 队列为空！

[成功] 结论：循环队列适合元素数量固定、追求内存高效利用的场景；链式队列适合元素数量不确定、需要动态扩容的场景，且无需处理循环指针，实现更直观。

1.5.3 队列的应用场景：生产者 - 消费者模型

队列是'生产者 - 消费者模型'的核心数据结构——生产者线程向队列中添加数据（入队），消费者线程从队列中获取数据（出队），队列起到缓冲和同步的作用，解耦生产者和消费者。

示例 11：模拟生产者 - 消费者模型（单线程简化版）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h> // 包含 sleep 函数（Linux 系统）

#define MAX_QUEUE_SIZE 5 // 队列最大容量

// 循环队列实现（存储字符串数据）
typedef struct {
    char data[MAX_QUEUE_SIZE][20]; // 存储字符串
    int front;
    int rear;
} MsgQueue;

// 队列初始化
void initMsgQueue(MsgQueue *queue) {
    queue->front = 0;
    queue->rear = 0;
}

// 判空
int isMsgQueueEmpty(MsgQueue *queue) {
    return queue->front == queue->rear ? 1 : 0;
}

// 判满
int isMsgQueueFull(MsgQueue *queue) {
    return (queue->rear + 1) % MAX_QUEUE_SIZE == queue->front ? 1 : 0;
}

// 入队（生产者生产数据）
int produce(MsgQueue *queue, const char* msg) {
    if(isMsgQueueFull(queue)) {
        printf("[注意] 队列满，生产者等待...\n");
        return -1;
    }
    strcpy(queue->data[queue->rear], msg);
    queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
    printf("[入队] 生产者生产：%s\n", msg);
    return 0;
}

// 出队（消费者消费数据）
int consume(MsgQueue *queue, char* msg) {
    if(isMsgQueueEmpty(queue)) {
        printf("[注意] 队列空，消费者等待...\n");
        return -1;
    }
    strcpy(msg, queue->data[queue->front]);
    queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    printf("[出队] 消费者消费：%s\n", msg);
    return 0;
}

int main() {
    MsgQueue queue;
    initMsgQueue(&queue);
    char msg[20];
    
    // 模拟生产者生产数据
    produce(&queue, "任务 1");
    produce(&queue, "任务 2");
    produce(&queue, "任务 3");
    produce(&queue, "任务 4");
    sleep(1); // 生产者暂停 1 秒
    
    // 模拟消费者消费数据
    consume(&queue, msg);
    consume(&queue, msg);
    sleep(1); // 消费者暂停 1 秒
    
    // 生产者继续生产
    produce(&queue, "任务 5");
    produce(&queue, "任务 6");
    
    // 队列满，生产者等待
    sleep(1);
    
    // 消费者继续消费
    consume(&queue, msg);
    consume(&queue, msg);
    consume(&queue, msg);
    sleep(1);
    
    // 消费者尝试消费空队列
    consume(&queue, msg);
    return 0;
}

运行结果：

[入队] 生产者生产：任务 1
[入队] 生产者生产：任务 2
[入队] 生产者生产：任务 3
[入队] 生产者生产：任务 4
[出队] 消费者消费：任务 1
[出队] 消费者消费：任务 2
[入队] 生产者生产：任务 5
[注意] 队列满，生产者等待...
[出队] 消费者消费：任务 3
[出队] 消费者消费：任务 4
[出队] 消费者消费：任务 5
[注意] 队列空，消费者等待...

[提示] 技巧：在多线程环境中，生产者 - 消费者模型需要添加互斥锁（如 pthread_mutex_t）和条件变量（如 pthread_cond_t）保证线程安全，避免并发读写冲突。队列的缓冲特性使生产者和消费者可以异步工作，无需等待对方立即响应，提升系统吞吐量。

1.6 实际项目案例：基于链表的学生成绩管理系统

1.6.1 案例需求

实现一个学生成绩管理系统，支持以下功能：

1. 新增学生信息（学号、姓名、三门课程成绩）；
2. 查找学生信息（按学号查找）；
3. 修改学生成绩（按学号修改指定课程成绩）；
4. 删除学生信息（按学号删除）；
5. 统计功能（计算平均分、排序输出、统计及格人数）；
6. 遍历输出所有学生信息；
7. 销毁系统（释放所有内存）。

1.6.2 案例实现

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

// 定义学生结构体
typedef struct Student {
    char id[20];      // 学号（唯一标识）
    char name[20];    // 姓名
    float scores[3];  // 三门课程成绩：语文、数学、英语
    float avgScore;   // 平均分
    struct Student* next; // 指向后一个学生的指针（链表节点）
} Student, *StudentList;

// ==================== 工具函数 ====================
// 计算平均分
float calculateAvg(float scores[]) {
    return (scores[0] + scores[1] + scores[2]) / 3.0f;
}

// 验证成绩合法性（0-100 分）
bool isValidScore(float score) {
    return score >= 0.0f && score <= 100.0f;
}

// ==================== 链表核心操作 ====================
// 1. 初始化学生链表（带头节点）
StudentList initStudentList() {
    Student *head = (Student *)malloc(sizeof(Student));
    if(head == NULL) {
        printf("[注意] 链表初始化失败！\n");
        exit(-1);
    }
    head->next = NULL;
    return head;
}

// 2. 新增学生信息（尾插法）
int addStudent(StudentList head, const char* id, const char* name, float scores[]) {
    // 检查学号是否已存在
    Student *p = head->next;
    while(p != NULL) {
        if(strcmp(p->id, id) == 0) {
            printf("[注意] 学号%s已存在，新增失败！\n", id);
            return -1;
        }
        p = p->next;
    }
    
    // 检查成绩合法性
    for(int i = 0; i < 3; i++) {
        if(!isValidScore(scores[i])) {
            printf("[注意] 成绩%.1f 非法（需在 0-100 之间），新增失败！\n", scores[i]);
            return -1;
        }
    }
    
    // 创建新学生节点
    Student *newStudent = (Student *)malloc(sizeof(Student));
    if(newStudent == NULL) {
        printf("[注意] 节点内存分配失败！\n");
        return -1;
    }
    strcpy(newStudent->id, id);
    strcpy(newStudent->name, name);
    memcpy(newStudent->scores, scores, sizeof(scores));
    newStudent->avgScore = calculateAvg(scores);
    newStudent->next = NULL;
    
    // 插入链表尾部
    p = head;
    while(p->next != NULL) {
        p = p->next;
    }
    p->next = newStudent;
    printf("[成功] 学号%s学生信息新增成功！\n", id);
    return 0;
}

// 3. 按学号查找学生（返回学生节点指针，未找到返回 NULL）
Student *findStudentByID(StudentList head, const char* id) {
    Student *p = head->next;
    while(p != NULL) {
        if(strcmp(p->id, id) == 0) {
            return p; // 找到，返回节点指针
        }
        p = p->next;
    }
    printf("[注意] 未找到学号%s的学生！\n", id);
    return NULL;
}

// 4. 按学号修改学生成绩
int modifyStudentScore(StudentList head, const char* id, int courseIdx, float newScore) {
    // 检查课程索引合法性（0-语文，1-数学，2-英语）
    if(courseIdx < 0 || courseIdx > 2) {
        printf("[注意] 课程索引非法（0=语文，1=数学，2=英语）！\n");
        return -1;
    }
    
    // 检查成绩合法性
    if(!isValidScore(newScore)) {
        printf("[注意] 成绩%.1f 非法（需在 0-100 之间）！\n", newScore);
        return -1;
    }
    
    // 查找学生
    Student *student = findStudentByID(head, id);
    if(student == NULL) {
        return -1;
    }
    
    // 修改成绩并更新平均分
    float oldScore = student->scores[courseIdx];
    student->scores[courseIdx] = newScore;
    student->avgScore = calculateAvg(student->scores);
    
    const char* courseNames[] = {"语文", "数学", "英语"};
    printf("[成功] 学号%s学生的%s成绩修改成功：%.1f → %.1f，新平均分为%.1f\n", id, courseNames[courseIdx], oldScore, newScore, student->avgScore);
    return 0;
}

// 5. 按学号删除学生信息
int deleteStudentByID(StudentList head, const char* id) {
    Student *prev = head;     // 前驱节点
    Student *curr = head->next; // 当前节点
    
    while(curr != NULL) {
        if(strcmp(curr->id, id) == 0) {
            // 前驱节点指向当前节点的后继
            prev->next = curr->next;
            // 释放当前节点内存
            free(curr);
            curr = NULL;
            printf("[成功] 学号%s学生信息删除成功！\n", id);
            return 0;
        }
        prev = curr;
        curr = curr->next;
    }
    printf("[注意] 未找到学号%s的学生，删除失败！\n", id);
    return -1;
}

// 6. 遍历输出所有学生信息
void traverseStudentList(StudentList head) {
    Student *p = head->next;
    if(p == NULL) {
        printf("[注意] 系统中暂无学生信息！\n");
        return;
    }
    printf("\n==================== 学生成绩列表 ====================\n");
    printf("%-10s %-10s %-8s %-8s %-8s %-8s\n", "学号", "姓名", "语文", "数学", "英语", "平均分");
    printf("------------------------------------------------------\n");
    while(p != NULL) {
        printf("%-10s %-10s %-8.1f %-8.1f %-8.1f %-8.1f\n", p->id, p->name, p->scores[0], p->scores[1], p->scores[2], p->avgScore);
        p = p->next;
    }
    printf("======================================================\n\n");
}

// 7. 统计功能：按平均分降序排序
void sortStudentsByAvg(StudentList head) {
    Student *p = head->next;
    if(p == NULL || p->next == NULL) {
        printf("[注意] 学生数量不足 2 人，无需排序！\n");
        return;
    }
    
    // 冒泡排序（修改节点指针，而非数据）
    bool swapped;
    Student *ptr1;
    Student *lptr = NULL; // 标记已排序部分的尾部
    
    do {
        swapped = false;
        ptr1 = head->next;
        while(ptr1->next != lptr) {
            if(ptr1->avgScore < ptr1->next->avgScore) {
                // 交换两个节点的数据（简化实现，也可交换指针）
                Student temp = *ptr1;
                *ptr1 = *(ptr1->next);
                *(ptr1->next) = temp;
                
                // 修复交换后的指针指向（关键！）
                Student *tempNext = ptr1->next;
                ptr1->next = tempNext->next;
                tempNext->next = ptr1;
                swapped = true;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    } while(swapped);
    
    printf("[成功] 学生按平均分降序排序完成！\n");
    traverseStudentList(head);
}

// 8. 统计功能：统计各课程及格人数（≥60 分）
void countPassedStudents(StudentList head) {
    Student *p = head->next;
    if(p == NULL) {
        printf("[注意] 系统中暂无学生信息，无法统计！\n");
        return;
    }
    
    int passCount[3] = {0}; // 语文、数学、英语及格人数
    int totalCount = 0;     // 总学生数
    
    while(p != NULL) {
        totalCount++;
        for(int i = 0; i < 3; i++) {
            if(p->scores[i] >= 60.0f) {
                passCount[i]++;
            }
        }
        p = p->next;
    }
    
    const char* courseNames[] = {"语文", "数学", "英语"};
    printf("\n==================== 及格人数统计 ====================\n");
    for(int i = 0; i < 3; i++) {
        float passRate = (float)passCount[i] / totalCount * 100;
        printf("%s：及格人数%d/%d，及格率%.1f%%\n", courseNames[i], passCount[i], totalCount, passRate);
    }
    printf("======================================================\n\n");
}

// 9. 销毁学生链表（释放所有内存）
void destroyStudentList(StudentList *head) {
    Student *p = *head;
    while(p != NULL) {
        Student *temp = p;
        p = p->next;
        free(temp);
        temp = NULL;
    }
    *head = NULL;
    printf("[成功] 学生成绩管理系统销毁成功，所有内存已释放！\n");
}

// ==================== 主菜单与测试 ====================
void printMenu() {
    printf("\n===== 学生成绩管理系统 =====\n");
    printf("1. 新增学生信息\n");
    printf("2. 查找学生信息\n");
    printf("3. 修改学生成绩\n");
    printf("4. 删除学生信息\n");
    printf("5. 遍历所有学生\n");
    printf("6. 按平均分排序\n");
    printf("7. 统计及格人数\n");
    printf("0. 退出系统\n");
    printf("===========================\n");
    printf("请选择功能（0-7）：");
}

int main() {
    StudentList head = initStudentList();
    int choice;
    char id[20], name[20];
    float scores[3], newScore;
    int courseIdx;
    Student *student;
    
    while(1) {
        printMenu();
        scanf("%d", &choice);
        getchar(); // 吸收换行符
        
        switch(choice) {
            case 1: // 新增学生
                printf("请输入学号：");
                scanf("%s", id);
                printf("请输入姓名：");
                scanf("%s", name);
                printf("请输入语文、数学、英语成绩（用空格分隔）：");
                scanf("%f %f %f", &scores[0], &scores[1], &scores[2]);
                addStudent(head, id, name, scores);
                break;
            case 2: // 查找学生
                printf("请输入要查找的学号：");
                scanf("%s", id);
                student = findStudentByID(head, id);
                if(student != NULL) {
                    printf("\n找到学生信息：\n");
                    printf("学号：%s，姓名：%s\n", student->id, student->name);
                    printf("语文：%.1f，数学：%.1f，英语：%.1f，平均分：%.1f\n", student->scores[0], student->scores[1], student->scores[2], student->avgScore);
                }
                break;
            case 3: // 修改成绩
                printf("请输入要修改的学生学号：");
                scanf("%s", id);
                printf("请选择要修改的课程（0=语文，1=数学，2=英语）：");
                scanf("%d", &courseIdx);
                printf("请输入新成绩（0-100）：");
                scanf("%f", &newScore);
                modifyStudentScore(head, id, courseIdx, newScore);
                break;
            case 4: // 删除学生
                printf("请输入要删除的学生学号：");
                scanf("%s", id);
                deleteStudentByID(head, id);
                break;
            case 5: // 遍历所有学生
                traverseStudentList(head);
                break;
            case 6: // 按平均分排序
                sortStudentsByAvg(head);
                break;
            case 7: // 统计及格人数
                countPassedStudents(head);
                break;
            case 0: // 退出系统
                destroyStudentList(&head);
                printf("[再见] 感谢使用学生成绩管理系统，再见！\n");
                return 0;
            default:
                printf("[注意] 无效的功能选择，请重新输入！\n");
                break;
        }
    }
}

1.6.3 案例测试与运行结果

===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：1
请输入学号：2024001
请输入姓名：张三
请输入语文、数学、英语成绩（用空格分隔）：85 92 78
[成功] 学号 2024001 学生信息新增成功！

===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：1
请输入学号：2024002
请输入姓名：李四
请输入语文、数学、英语成绩（用空格分隔）：72 68 95
[成功] 学号 2024002 学生信息新增成功！

===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：5
==================== 学生成绩列表 ====================
学号       姓名       语文     数学     英语     平均分
------------------------------------------------------
2024001   张三      85.0     92.0     78.0     85.0
2024002   李四      72.0     68.0     95.0     78.3
======================================================

===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：3
请输入要修改的学生学号：2024002
请选择要修改的课程（0=语文，1=数学，2=英语）：1
请输入新成绩（0-100）：75
[成功] 学号 2024002 学生的数学成绩修改成功：68.0 → 75.0，新平均分为 80.7

===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：6
[成功] 学生按平均分降序排序完成！
==================== 学生成绩列表 ====================
学号       姓名       语文     数学     英语     平均分
------------------------------------------------------
2024001   张三      85.0     92.0     78.0     85.0
2024002   李四      72.0     75.0     95.0     80.7
======================================================

===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：7
==================== 及格人数统计 ====================
语文：及格人数 2/2，及格率 100.0%
数学：及格人数 2/2，及格率 100.0%
英语：及格人数 2/2，及格率 100.0%
======================================================

===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：0
[成功] 学生成绩管理系统销毁成功，所有内存已释放！
[再见] 感谢使用学生成绩管理系统，再见！

[成功] 案例总结：该系统基于单链表实现，充分利用了链表'动态扩容、插入删除高效'的特性，支持学生信息的全生命周期管理。核心亮点包括：

1. 数据校验（学号唯一、成绩合法），提升系统稳定性；
2. 模块化设计（新增、查找、修改等功能独立封装），便于维护和扩展；
3. 实用统计功能（排序、及格率统计），贴合实际应用场景；
4. 严格的内存管理（销毁时释放所有节点），避免内存泄漏。

1.7 常见问题与避坑指南

1.7.1 链表操作中的野指针与内存泄漏

野指针问题

• 错误场景 1：节点 next 指针未初始化，指向随机地址；
• 错误场景 2：释放节点后未将指针置空，后续误访问。

✅ 避坑方案：

1. 新建节点时，next 指针立即初始化为 NULL；
2. 释放节点后，将指向该节点的指针（如 curr、temp）置空；
3. 遍历链表时，判断指针非 NULL 后再访问成员。

内存泄漏问题

• 错误场景：只删除链表节点的引用，未调用 free 释放内存。

✅ 避坑方案：

1. 任何通过 malloc 分配的节点，在删除时必须调用 free；
2. 链表销毁时，需遍历所有节点逐一释放，不可只释放头节点；
3. 复杂操作（如排序、反转）后，确保所有节点都能被正常访问和释放。

1.7.2 栈与队列的边界条件处理

栈的边界问题

• 错误场景 1：栈空时执行出栈或取栈顶操作；
• 错误场景 2：数组栈满时执行入栈操作。

✅ 避坑方案：

1. 所有栈操作前先判断栈空/栈满状态；
2. 数组栈可通过 realloc 实现动态扩容，避免固定容量限制；
3. 链式栈无需判满，但需检查 malloc 节点是否成功。

队列的边界问题

• 错误场景 1：循环队列队空/队满判断混淆；
• 错误场景 2：链式队列出队时未处理'队列只有一个元素'的情况。

✅ 避坑方案：

1. 循环队列严格遵循'队空 front==rear，队满 (rear+1)%MAX_SIZE==front'；
2. 链式队列出队时，若删除的是最后一个元素，需将 rear 指针重置为头节点；
3. 入队/出队操作后，及时更新指针位置，避免指针越界。

1.7.3 数据结构选择误区

[提示] 技巧：数据结构的选择需结合'操作频率'和'数据特性'——高频插入删除选链表，高频访问选数组；按顺序存取选栈/队列，按逻辑选对应结构。

1.7.4 复杂操作中的逻辑错误

链表反转逻辑错误

• 错误场景：未保存后继节点，导致链表断裂。

✅ 避坑方案：

1. 迭代法反转时，必须用 next 指针临时保存当前节点的后继；
2. 反转完成后，更新头节点指针，确保链表入口正确。

循环队列指针移动错误

• 错误场景：指针移动时未使用取模运算，导致指针越界。

✅ 避坑方案：

1. 队头/队尾指针移动时，严格使用 (index + 1) % MAX_SIZE；
2. 计算元素个数时，使用 (rear - front + MAX_SIZE) % MAX_SIZE，避免负数。

1.8 本章总结

本章围绕'指针 + 结构体'核心，深入讲解了 C 语言中三大基础复杂数据结构——链表、栈、队列，核心要点如下：

1. 指针与结构体的结合是实现复杂数据结构的基础，typedef 可简化结构体指针声明，提升代码可读性；
2. 链表支持动态扩容，插入删除高效，单链表适合单向遍历场景，双向链表支持双向遍历，循环链表适用于环形数据存储；
3. 栈遵循 LIFO 规则，数组栈实现简单、访问高效，链式栈容量灵活，经典应用包括括号匹配、表达式求值；
4. 队列遵循 FIFO 规则，循环队列解决数组假溢出问题，链式队列无容量限制，经典应用包括生产者 - 消费者模型、任务调度；
5. 实际开发中，需根据场景选择合适的数据结构，同时注重内存管理和边界条件处理，避免野指针、内存泄漏等问题。

[提示] 学习建议：复杂数据结构的核心是'指针操作'和'逻辑建模'——建议先手动模拟链表反转、栈入栈出栈、队列入队出队等操作的内存变化过程，再通过大量案例练习巩固。后续学习中，可基于本章知识扩展到更复杂的数据结构（如二叉树、哈希表），为 C 语言进阶开发（如嵌入式编程、内核开发）打下坚实基础。