数据结构--栈

栈的定义栈是一种线性数据结构遵循后进先出LIFO原则即最后存入的元素最先被取出。我们可以把栈比作一个羽毛球桶当我们把球一个个放进去让后当我们取羽毛球的时候是不是拿的就是我们最后放进去的那个羽毛球这个就是并且只能从一端取放这里就很解答这个栈栈的增加数据删除数据的一端叫做栈顶另一端叫做栈底增加数据叫做压栈删除数据叫做出栈核心操作压栈Push将元素添加到栈顶。出栈Pop移除并返回栈顶元素。查看栈顶Peek获取栈顶元素但不移除。判空isEmpty检查栈是否为空。实现方式数组实现通过固定大小数组和栈顶指针实现。链表实现通过链表的头部作为栈顶动态调整。这里我们用数组进行实现也就是顺序表的结构来实现栈的基本功能栈的#define _CRT_SECURE_NO_WARNINGS 1 #includestack.h //我们在这里写一个打印栈中的数据函数 int main() { ST sl; STinit(sl); STpush(sl, 1); STpush(sl, 2); STpush(sl, 3); STpush(sl, 4); while ( !STempty(sl)) { printf(%d , STtop(sl)); //打印一个删一个 STpop(sl); } STpop(sl, 4); STdestory(sl); return 0; }1.1定义栈的基本结构typedef int SLtypedata; //首先我们写一下顺序表的结构 typedef struct stack { SLtypedata* a; int top;//这里我们将原来顺序表中的size换成top因为在栈中top代表栈顶元素的个数 int capacity; }ST;1.2栈的初始化//栈的初始化 void STinit(ST* pst);//栈的初始化 void STinit(ST* pst) { assert(pst); pst-a NULL; pst-capacity pst-top 0;//这里对top的初始化有两种另外一种是top-1我们最好用top0 //因为这里top0它即代表了顺序表的下标又代表了顺序表的数据个数 }1.3栈的销毁//栈的销毁 void STdestory(ST* pst);//栈的销毁 void STdestory(ST* pst) { assert(pst); free(pst-a); pst-a NULL; pst-top pst-capacity 0; }1.4栈的增添数据//栈的插入,也叫做入栈 void STpush(ST* pst, SLtypedata x);//栈的插入,也叫做入栈 void STpush(ST* pst, SLtypedata x) { if (pst-capacity pst-top) { //插入数据之前要看看栈中是否有空间如果没有需要申请空间 int newcapacity pst-capacity 0 ? 4 : 2 * pst-capacity; SLtypedata* tmp (SLtypedata*)realloc(pst-a, sizeof(SLtypedata) * newcapacity); if (tmp NULL) { perror(realloc fail); return; } pst-capacity newcapacity; pst-a tmp; } //到这里栈的空间的判断已经完成开始进行数据的插入 pst-a[pst-top] x; pst-top; }在插入数据的时候需要先对栈进行空间上的判断如果没有多余的空间就进行realloc函数对栈进行空间上的申请申请好空间之后就可以进行数据的插入了。1.4栈的删除数据//栈的删除也叫做出栈 void STpop(ST* pst);//因为栈的数据元素遵循后进先出原则//栈的删除也叫做出栈 void STpop(ST* pst)//因为栈的数据元素遵循后进先出原则 { //因为遵循后进先出原则所以只能从栈顶删除数据 //需要保证栈不为NULL assert(pst); assert(pst-top 0); pst-top--; }1.5栈的栈顶元素//栈的栈顶数据 SLtypedata STtop(ST* pst);//栈的栈顶数据 SLtypedata STtop(ST* pst) { assert(pst); assert(pst-top 0); return pst-a[pst-top - 1];//因为我们在之前将top初始化为0所以下标是top-1 }1.6栈的判空这里我们使用了bool函数的返回值需要包含头文件#includestdbool//栈的判空 bool STempty(ST* pst);//栈的判空 bool STempty(ST* pst) { //这个判空只需要看一下top的值是否为0 return pst-top 0; }1.7栈的数据元素个数//获取数据个数 int STsize(ST* pst);//获取数据个数 int STsize(ST* pst) { assert(pst); //因为我们在初始化的时候初始化top为0所以它的值既代表了下标又代表了数据个数 return pst-top; }