欢迎拜访:雾里看山-CSDN博客
本篇主题:数据结构之栈
发布时间:2025.7.5
隶属专栏:数据结构
目录
栈的概念与结构
基本概念
栈是一种后进先出(LIFO: Last In First Out)的线性数据结构,只允许在固定的一端进行插入和删除操作。
- 压栈/入栈 (Push):将元素放入栈顶
- 出栈 (Pop):从栈顶移除元素
- 栈顶 (Top):唯一允许操作的元素位置
- 栈底 (Bottom):不允许操作的一端
核心特性
- LIFO原则:最后入栈的元素最先出栈
- 受限访问:只能访问栈顶元素
- 动态大小:大小随操作变化(除固定大小栈)
- 操作高效:所有操作时间复杂度为O(1)
栈的实现
栈有两种主要实现方式:顺序栈(基于数组)和链栈(基于链表)。
顺序栈
栈结构的定义:
typedef int STDataType;
typedef struct Stack
{
STDataType* a;// 数组的指针
int top; // 存储数据的数量
int capacity; // 栈的总容量
}ST;
基本操作的实现
// 栈的初始化
void STInit(ST* ps)
{
assert(ps);
STDataType* tmp= (STDataType*)malloc(sizeof(STDataType) * 4);
if (tmp == NULL)
{
perror("Init malloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity = 4;
ps->top = 0;
}
// 栈的销毁
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a == NULL;
ps->top = ps->capacity = 0;
}
// 入栈
void STPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->capacity == ps->top)
{
STDataType* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL)
{
perror("Push realloc fail");
exit(-2);
}
ps->a = tmp;
ps->capacity *= 2;
}
ps->a[ps->top] = x;
ps->top++;
}
// 出栈
void STPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
// 取栈顶元素
STDataType STTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
// 栈存储的数量
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
//栈是否为空
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
链栈
栈结构的定义
typedef int STDataType;
typedef struct StackNode
{
STDataType data; // 存放数据
struct StackNode* next;// 指向下一个节点
}STNode;
typedef struct Stack
{
STNode* top; // 栈顶元素
int size; // 栈内元素的数量
}Stack;
基本操作的实现
// 初始化栈
void StackInit(Stack* ps)
{
ps->top = NULL;
ps->size = 0;
}
// 创建节点
STNode* BuyNode(STDataType x)
{
STNode* tmp = (STNode *)malloc(sizeof(STNode));
if (tmp == NULL)
{
perror("malloc node fail\n");
exit(-1);
}
tmp->data = x;
tmp->next = NULL;
return tmp;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
STNode* node = BuyNode(data);
node->next = ps->top;
ps->size++;
ps->top = node;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->size > 0);
STNode* top = ps->top;
ps->top = ps->top->next;
ps->size--;
free(top);
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
return ps->top->data;
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->size;
}
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->size == 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
while (ps->top)
{
STNode* tmp = ps->top;
ps->top = ps->top->next;
free(tmp);
}
ps->size = 0;
}
两种实现的比较
特性 | 顺序栈(数组实现) | 链栈(链表实现) |
---|---|---|
内存分配 | 半静态/固定大小 | 动态分配/无固定大小 |
空间效率 | 无额外指针开销 | 每个节点额外指针开销 |
时间效率 | 所有操作O(1) | 所有操作O(1) |
扩容能力 | 有限(需重新分配) | 无限(除非内存耗尽) |
缓存友好 | 高(连续内存) | 低(非连续内存) |
实现难度 | 简单 | 中等 |
适用场景 | 元素数量可预测/固定大小 | 元素数量变化大/内存受限 |
总结与选择建议
栈的核心价值
- 简单高效:所有操作时间复杂度O(1)
- 逻辑清晰:LIFO原则简化问题处理
- 功能强大:适用于多种算法和系统功能
- 内存友好:最小化临时存储需求
实现选择建议
场景 | 推荐实现 | 理由 |
---|---|---|
元素数量固定/可预测 | 顺序栈(数组) | 内存紧凑,无额外开销 |
元素数量变化大/不可预测 | 链栈(链表) | 动态扩展,无容量限制 |
高频访问/内存敏感 | 顺序栈 | 缓存友好,访问速度快 |
需要多栈共享内存 | 顺序栈 | 可在同一数组实现多个栈 |
需要实现复杂功能 | 链栈 | 灵活性高,无扩容问题 |
应用领域总结
- 系统级开发:函数调用栈、中断处理
- 算法实现:DFS、回溯、表达式求值
- 应用软件:撤销/重做、浏览历史
- 编译器:语法分析、中间代码生成
- 嵌入式系统:有限状态机、任务调度
⚠️ 写在最后:以上内容是我在学习以后得一些总结和概括,如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流!!!