栈
约 1979 字大约 7 分钟
2025-11-19
栈是一种遵循后进先出(LIFO)原则的线性数据结构,只允许在栈顶进行插入和删除操作。
我们可以将栈类比为桌面上的一摞盘子,规定每次只能移动一个盘子,那么想取出底部的盘子,则需要先将上面的盘子依次移走。我们将盘子替换为各种类型的元素(如整数、字符、对象等),就得到了栈这种数据结构。
核心特性
- 受限访问:只能访问栈顶元素,无法直接访问中间或底部元素
- 动态大小:栈的大小随着元素入栈出栈而动态变化
- 操作单一:所有操作都在栈顶进行,包括插入(入栈)和删除(出栈)
应用场景
- 函数调用栈管理
- 表达式求值和括号匹配
- 浏览器前进后退功能
- 撤销操作机制
栈可以使用数组和链表来实现
使用数组实现栈
数组实现栈利用连续内存空间,通过栈顶指针来管理栈的操作。
构造数组栈
设计原理
- 固定容量:预先分配固定大小的数组空间
- 栈顶指针:使用
top变量指示栈顶位置,初始值为 -1 表示空栈 - 边界控制:通过栈顶指针判断栈空和栈满条件
关键理解点
- 索引选择:
top = -1表示空栈,便于后续的递增操作 - 内存预分配:数组大小固定,需要合理估计最大容量
- 简单高效:数组实现具有缓存友好性和访问速度快的特点
CommonUseA.cpp
const int MAX_SIZE = 101;
int A[MAX_SIZE]{};
int top = -1;入栈操作
函数参数说明
x:要入栈的元素值- 无返回值,直接修改全局数组和栈顶指针
操作原理
- 栈满检查:检查栈顶指针是否达到数组最大索引
- 栈顶移动:先递增栈顶指针,再存入元素
- 元素存储:将新元素存入栈顶位置
关键理解点
- 先增后存:使用
++top先移动指针再存储,避免索引错误 - 溢出处理:必须检查栈满条件,防止数组越界
- 原子操作:入栈操作应该是原子的,保证数据一致性
PushUseA.cpp
void PushUseA(int x) {
using std::cout;
if (top == MAX_SIZE - 1) {
cout << "错误,栈溢出";
return;
}
A[++top] = x;
}出栈操作
操作原理
- 栈空检查:检查栈顶指针是否为 -1(空栈)
- 栈顶移动:递减栈顶指针,逻辑上移除栈顶元素
- 内存回收:数组实现中实际数据仍存在,但无法访问
关键理解点
- 逻辑删除:出栈只是移动指针,并不实际清除数组数据
- 下溢防护:必须检查栈空条件,避免无效操作
- 指针管理:通过指针移动实现元素的逻辑移除
PopUseA.cpp
void PopUseA() {
using std::cout;
if (top == -1) {
cout << "错误,链表为空";
return;
}
top--;
}访问栈顶元素
操作原理
- 直接访问:通过栈顶指针索引直接返回栈顶元素
- 无副作用:访问操作不改变栈的状态
关键理解点
- 只读操作:访问栈顶不会影响栈的结构
- 空栈处理:在实际应用中应考虑空栈的返回值策略
TopUseA.cpp
int TopUseA() {
return A[top];
}打印栈元素
操作原理
- 顺序遍历:从栈底到栈顶遍历数组元素
- 状态展示:显示栈中所有元素的当前状态
关键理解点
- 遍历范围:从索引 0 到
top,包含所有有效元素 - 调试工具:主要用于调试和可视化栈的状态
PrintUseA.cpp
void PrintUseA() {
using std::cout;
cout << "stack: ";
for (int i = 0; i <= top; i++) {
cout << A[i] << " ";
}
cout << "\n";
}使用链表实现栈
链表实现栈利用动态内存分配,可以灵活适应栈大小的变化。
构造栈节点
设计原理
- 节点结构:每个节点包含数据域和指向下一节点的指针
- 动态内存:节点在堆中动态分配,无固定大小限制
- 头指针:使用头指针指向栈顶节点
关键理解点
- 内存灵活性:链表栈可以动态增长,不受固定容量限制
- 额外开销:每个节点需要额外的指针空间
- 头部操作:选择链表头部作为栈顶以保证 O(1) 时间复杂度
构造栈节点
CommonUseL.cpp
struct Node {
int data;
Node* next;
};入栈操作(链表头部插入节点)
函数参数说明
top:当前栈顶节点指针x:要入栈的元素值- 返回值:新的栈顶节点指针
操作原理
- 创建节点:在堆中分配新节点内存
- 设置数据:将元素值存入新节点的数据域
- 连接节点:新节点的
next指针指向原栈顶 - 更新栈顶:栈顶指针指向新节点
关键理解点
- 头插法:在链表头部插入保证 O(1) 时间复杂度
- 指针更新:必须返回新的栈顶指针,因为栈顶已改变
- 内存分配:每次入栈都需要动态分配内存
PushUseL.cpp
Node* PushUseL(Node* top, int x) {
Node* temp = new Node();
temp->data = x;
temp->next = top;
top = temp;
return top;
}出栈操作(链表头部删除节点)
函数参数说明
top:当前栈顶节点指针- 返回值:新的栈顶节点指针
操作原理
- 栈空检查:检查栈顶指针是否为
NULL - 临时保存:保存原栈顶节点指针用于内存释放
- 更新栈顶:栈顶指针指向下一个节点
- 释放内存:删除原栈顶节点,释放内存
关键理解点
- 内存管理:必须手动释放出栈节点的内存
- 边界处理:空栈出栈应有适当的错误处理
- 指针安全:确保在释放内存前更新栈顶指针
PopUseL.cpp
Node* PopUseL(Node* top) {
Node* temp;
if (top == NULL) {
return;
}
temp = top;
top = top->next;
delete temp;
return top;
}打印栈元素
函数参数说明
top:当前栈顶节点指针
操作原理
- 临时指针:使用临时指针遍历栈,避免修改原栈顶
- 顺序遍历:从栈顶到栈底遍历所有节点
- 数据输出:输出每个节点的数据值
关键理解点
- 遍历保护:使用临时指针避免破坏栈结构
- 顺序显示:按入栈顺序的逆序显示(栈顶到栈底)
- 调试功能:主要用于验证栈的正确性
PrintUseL.cpp
void PrintUseL(Node* top) {
using std::cout;
Node* temp = top;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << "\n";
}访问栈顶元素
函数参数说明
top:当前栈顶节点指针- 返回值:栈顶元素值或错误标识
操作原理
- 直接访问:通过栈顶指针访问节点的数据域
- 空栈处理:对空栈访问返回特定值(如 -1)表示错误
关键理解点
- 只读操作:访问操作不影响栈结构
- 错误处理:应有明确的空栈处理策略
- 数据安全:确保在访问前检查指针有效性
TopUseL.cpp
int TopUseL(Node* top) {
if (top != NULL) {
return top->data;
}
return -1; // 返回-1表示栈为空
}两种实现方式对比
| 特性 | 数组实现 | 链表实现 |
|---|---|---|
| 内存分配 | 静态预分配 | 动态分配 |
| 最大容量 | 固定 | 理论上无限 |
| 内存开销 | 较小 | 每个节点有指针开销 |
| 访问速度 | 较快(缓存友好) | 相对较慢 |
| 实现复杂度 | 简单 | 较复杂 |
| 适用场景 | 大小可预估的场景 | 大小变化大的场景 |
