欢迎来到 Claffic 的博客
“但有一枝堪比玉,何须九畹始征兰” />前言:
栈是一种特殊的线性表,就像开盖的桶一样,从底部开始放数据,从顶部开始取数据,那么栈具体是如何实现的呢?这篇博客为你解答:
目录
Part1:何为栈
1.栈的概念
2.栈的结构
Part2: 栈的实现
1.前期准备
1.1创建项目
1.2栈的结构
1.3栈的初始化
2.相关功能实现
2.1入栈
2.2检测栈是否为空
2.3出栈
2.4获取栈顶元素
2.5获取栈中有效元素的个数
2.6销毁栈
Part1:何为栈
1.栈的概念
栈是一种特殊的线性表,只允许从特定的一端插入或删除元素,栈中数据的元素遵循后进先出原则(Last In First Out)。
进行数据插入和删除的一端称为栈顶,另一端称栈底。
就像个桶子一样,总是先从顶部放入或取出元素。
2.栈的结构
说完了栈的概念,大家的脑海里也许就会有栈的基本样子了,这里画图解释:
我是图示
Part2: 栈的实现
1.前期准备
1.1创建项目
老样子,三个项:
SList.h:头文件,声明所有函数;
SList.c:源文件,实现各函数;
test.c:源文件,主函数所在项,可调用各函数。
1.2栈的结构
在创建结构体之前,我们不妨要考虑一个问题:
用数组还是链表来实现栈?
数组:存储空间在物理上连续,随机访问时间复杂度O(1):
链表:存储空间在逻辑上连续,但物理上不一定连续,随机访问时间复杂度O(N).
就栈的特点来说,数组更接近。还是数组香哇。
所以我们 用数组来实现栈 :
创建一个结构体,其中的元素包含:
数组首元素的地址;
栈顶;
容量。
typedef int STDataType;typedef struct Stack{STDataType* a;int top; // 栈顶int capacity; // 容量}Stack;
1.3栈的初始化
既然创建了栈,就要进行初始化
无非就是对结构体中的元素进行初始化:
数组容量,先定义一个初始大小:4个元素大小,并且是动态的。
栈顶的话,可以是0,也可以是-1:
0时,top 的位置就是栈顶元素的下一个位置;
-1时,top 的位置就是栈顶元素的位置。
在这里我们取 top = 0;
// 初始化栈void StackInit(Stack* ps){assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;}
2.相关功能实现
2.1入栈
所谓入栈,就相当于尾部插入新的数据。
要注意插入数据前需检查是否满容,判断方法也很简单,就看 栈顶与容量 是否相等就可以。
// 入栈void StackPush(Stack* ps, STDataType data){assert(ps);if (ps->capacity == ps->top){STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = data;ps->top++;}
2.2检测栈是否为空
这里把检测栈是否为空单独封装成一个函数,是为了出栈做铺垫;
在栈为空的情况下是不能出栈的,所以出栈前要检测栈是否为空;
这里我们约定 如果为空返回非0结果,如果为不为空返回0 ;
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 int StackEmpty(Stack* ps){assert(ps);return ps->top == 0;//表达式,真为非0,假为0}
2.3出栈
出栈就相当于删除数据,但又不完全等于删除数据
它 只是改变了栈顶 ,栈顶之外的元素占有的空间不需要释放。
// 出栈void StackPop(Stack* ps){assert(ps);assert(!StackEmpty(ps));//注意逻辑反,为空就报错ps->top--;}
2.4获取栈顶元素
因为是栈,总要在栈顶取元素的
// 获取栈顶元素STDataType StackTop(Stack* ps){assert(ps);return ps->a[ps->top-1];//注意元素个数与下标差1}
2.5获取栈中有效元素的个数
其实就是栈顶啦,栈顶的数值代表了栈中有效元素的个数;
// 获取栈中有效元素个数int StackSize(Stack* ps){assert(ps);return ps->top;}
2.6销毁栈
用完了栈,要记得销毁哦。
其实就是该释放的释放,容量归0,栈顶置为-1,表示没有元素。
// 销毁栈void StackDestroy(Stack* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = -1;}
代码已上传至 我的gitee
拿走不谢~
总结:
栈也是线性表,具有后进先出的特点,在有这总需求的情况下可以应用,你学会了吗?
码文不易
如果你觉得这篇文章还不错并且对你有帮助,不妨支持一波哦