第十七章 数据结构实战：链表、栈与队列的 C 语言实现
一、学习目标与重点
1.1 学习目标
- 掌握链表（单链表、双向链表）的核心原理与 C 语言实现，包括增删改查操作
- 理解栈和队列的逻辑特性，能够基于数组和链表两种方式实现栈与队列
- 熟练运用链表、栈、队列解决实际开发问题（如数据缓存、表达式求值、任务调度等）
- 具备数据结构性能分析能力，能根据场景选择合适的实现方案
1.2 学习重点
💡 单链表的插入、删除操作（尤其是头插法、尾插法和中间节点操作） 💡 栈的"先进后出"和队列的"先进先出"特性在代码中的体现 💡 基于链表的栈/队列实现（解决数组实现的容量限制问题） 💡 实战案例中的数据结构选型思路与代码优化技巧
二、链表基础：从原理到实现
2.1 链表的核心概念
链表是一种非线性数据结构，由若干个"节点"通过指针连接形成链式结构，每个节点包含两部分：
- 数据域：存储节点的实际数据（如 int、char、自定义结构体等）
- 指针域：存储下一个（或上一个）节点的内存地址，实现节点间的关联
💡 与数组相比，链表的优势在于：
- 无需预先分配固定大小的内存，动态扩容更灵活
- 插入、删除节点时无需移动大量元素，效率更高（时间复杂度 O(1)，数组为 O(n)） 劣势则是：
- 无法像数组那样通过下标直接访问元素，需从头遍历（时间复杂度 O(n)）
- 每个节点额外存储指针，占用更多内存空间
C 语言中实现链表的关键是自定义结构体（封装数据域和指针域）和动态内存分配（malloc/free 函数），这也是本章的核心技术点。
2.2 单链表的实现（最常用链表类型）
单链表是最简单的链表结构，每个节点仅包含一个指针域，指向其后继节点，尾节点的指针域为 NULL（表示链表结束）。
2.2.1 定义单链表节点结构体
首先定义单链表节点的结构体，以存储 int 类型数据为例：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 单链表节点结构体定义
typedef struct Node {
int data; // 数据域：存储 int 类型数据
struct Node* next; // 指针域：指向后续节点的地址
} Node, *LinkedList;
// Node 为结构体别名，LinkedList 为结构体指针别名
⚠️ 注意：结构体内部的指针必须声明为 struct Node*，不能直接用 Node*（因为 typedef 别名在结构体定义完成后才生效）
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"），适合用栈进行求值，步骤如下：
- 遍历后缀表达式的每个元素
- 若为操作数，入栈
- 若为运算符，出栈两个操作数（后出栈的为左操作数），计算结果后入栈
- 遍历结束后，栈中剩余的唯一元素即为表达式结果
实战代码实现
#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 链表、栈、队列的核心特性对比
| 数据结构 | 核心特性 | 核心操作 | 典型应用场景 |
|---|---|---|---|
| 单链表 | 动态扩容、链式存储 | 增删 O(1)（指定前驱）、查找 O(n) | 数据量不确定、频繁增删的场景 |
| 双向链表 | 双向遍历、增删高效 | 增删 O(1)、查找 O(n) | 需要双向遍历的场景（如 LRU 缓存） |
| 数组栈 | 静态容量、随机访问 | 入栈/出栈 O(1) | 数据量固定、对效率要求高的场景 |
| 链表栈 | 动态扩容、链式存储 | 入栈/出栈 O(1) | 数据量不确定、无需随机访问的场景 |
| 循环队列 | 静态容量、空间高效 | 入队/出队 O(1) | 数据量固定、需要循环复用空间的场景 |
| 链表队列 | 动态扩容、链式存储 | 入队/出队 O(1) | 数据量不确定、频繁入队出队的场景 |
5.2 实现方式选型建议
💡 若数据量固定，优先选择数组实现（栈/队列），效率更高（数组随机访问速度快，无指针开销）； 💡 若数据量不确定，优先选择链表实现（栈/队列/链表），避免溢出问题； 💡 若需要双向遍历或频繁删除指定节点，优先选择双向链表； 💡 若需要循环复用空间（如缓冲区），优先选择循环队列； 💡 若需要"先进后出"特性（如表达式求值、递归调用），选择栈； 💡 若需要"先进先出"特性（如任务调度、消息传递），选择队列。
5.3 常见问题与优化技巧
5.3.1 链表常见问题
- 内存泄漏：动态分配的节点未调用
free释放，解决方案：使用完毕后遍历链表，逐个释放节点； - 野指针：指针指向已释放的内存或未初始化的内存，解决方案：释放节点后将指针设为 NULL，初始化指针时明确指向；
- 链表为空判断：单链表需判断
head->next == NULL，双向链表需判断head->next == NULL && head->prev == NULL； - 中间插入/删除：单链表需找到前驱节点，双向链表可直接通过节点的
prev指针获取前驱，效率更高。
5.3.2 栈与队列常见问题
- 数组栈/队列溢出：数组实现的栈/队列容量固定，解决方案：使用链表实现或动态扩容数组（重新分配更大的数组，复制原数据）；
- 循环队列空满判断：必须使用
front == rear（空）和(rear+1)%size == front（满），避免混淆； - 栈的多位数处理：如后缀表达式求值中，需处理多位数（连续数字字符组合），解决方案：遍历到数字时，累积计算多位数的值；
- 队列的线程安全：多线程环境下，入队和出队操作需加锁（如 pthread_mutex_t），避免并发冲突。
六、本章总结
本章详细讲解了 C 语言中三种核心数据结构：链表、栈和队列，从原理到实现，再到实战应用，逐步深入，重点内容包括：
- 单链表的定义、初始化、增删改查操作，以及双向链表的扩展实现；
- 栈的"先进后出"特性，数组栈和链表栈的实现，以及后缀表达式求值的实战应用；
- 队列的"先进先出"特性，循环队列和链表队列的实现，以及任务调度队列的实战应用；
- 数据结构的选型原则、性能对比，以及常见问题的解决方案。
💡 数据结构是 C 语言开发的核心基础，掌握链表、栈、队列的实现与应用，能为后续学习更复杂的数据结构（如树、图、哈希表）打下坚实基础。实际开发中，应根据具体场景选择合适的数据结构，兼顾效率和空间开销。
建议读者多动手编写代码，反复调试本章的案例，重点掌握动态内存分配（malloc/free）和指针操作，这是 C 语言实现复杂数据结构的关键。同时，尝试将这些数据结构应用到自己的项目中（如实现一个简单的缓存系统、消息队列等），加深理解和记忆。