江苏省交通运输厅门户网站建设管理,网站首页制作教程,交互设计和ui设计区别,wordpress 克隆页面欢迎来到 Claffic 的博客 #x1f49e;#x1f49e;#x1f49e; “但有一枝堪比玉#xff0c;何须九畹始征兰?” 前言#xff1a; 栈是一种特殊的线性表#xff0c;就像开盖的桶一样#xff0c;从底部开始放数据#xff0c;从顶部开始取数据#xff0c;那么栈具体是… 欢迎来到 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
拿走不谢~ 总结 栈也是线性表具有后进先出的特点在有这总需求的情况下可以应用你学会了吗 码文不易
如果你觉得这篇文章还不错并且对你有帮助不妨支持一波哦
