栈（数据结构）

点击表格内对应链接跳转对应内容⬇️⬇️⬇️作者主页吃透C语言专栏数据结构Gitee仓库文章目录一栈二栈的实现方式1 顺序栈2 链式栈三 顺序栈和链式栈的选择四 顺序栈的实现1 Test.c2 Stack.h3 Stack.c五 顺序栈的解析1 Test.c解析2 Stack.h解析3 Stack.c解析1 栈初始化2 栈销毁3 入栈4 出栈5 取栈顶6 栈元素个数7 判断空栈一栈栈一种特殊的线性表操作受限的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则总结栈就是一个线性表元素的逻辑顺序是连续的每一个元素都只有唯一的前置节点和后置节点但是物理上不一定连续所以依然可以用数组或者链式这两种存储数据的方式来实现栈但是栈是操作受限的线性表没有正常线性表所谓的头插删尾插删pos节点的插删栈只能对一端进行操作操作的这一端被称为栈顶在栈插入操作被称为入栈压栈栈删除操作称为出栈线性表逻辑结构大类按「操作约束」划分按「存储方式」划分普通线性表任意位置增删查改受限线性表栈仅栈顶操作后进先出队列仅两端操作先进先出顺序存储 → 顺序表链式存储 → 链表总结线性表只规定了逻辑上节点前后只有唯一节点所以数据存储空间方式有产生了顺序存储顺序表和链式存储链表而普通的线性表是可以在任意位置操作数据的也就是普通线性表但是有些线性表却只能在一端操作或者只能在两端这种就是受限线性表也就是栈和队列,受限的线性表依然是线性表只规定了逻辑上节点前后只能有唯一节点但是物理上依然有数组存储数据连续和链式存储数据不连续两种存储数据的模式二栈的实现方式栈是线性表只要逻辑上线性即可物理上不管所以实现栈可以用数组和链式的两种物理上存储数据的模式数组和链式来实现顺序栈和链式栈1 顺序栈定义顺序栈采用一段连续的内存空间数组存储栈中元素同时搭配一个栈顶指针整型变量记录当前栈顶元素的位置是最经典、最常用的栈实现形式。对比项约定一top 指向栈顶元素的下标约定二top 指向栈顶元素的下一个空位下标空栈状态top -1top 0入栈操作先top再向数组对应位置写入元素先向对应位置写入元素再top出栈操作先取出元素再top--先top--再取出元素栈满判定top maxSize - 1top maxSize约定一top指向栈顶元素的下标所以空栈状态的时候top为-1代表非数组起始下标所以为空栈所以top对应的位置就是元素的位置所以入栈的时候要先top,让top走到下一个空位置才能存放数据。所以top代表的下标1就是元素的存储个数约定二top指向栈顶元素的下一个空位的下标所以当top为0的时候存数据的位置在下标为-1的位置-1下标为无效的所以top为0代表空栈存两个元素个数是2如果下标对应元素位置那下标为1但是约定二中的top指的是元素下一个位置所以下标为2所以top就和顺序表中的size很像top就等于栈中元素的总数对比维度静态顺序栈动态顺序栈容量规则数组容量预先固定不可动态变更初始容量固定栈满时自动扩容通常扩容为原容量的 2 倍栈满处理栈满后无法继续入栈强制入栈触发「上溢overflow」异常申请更大的新数组复制全部原栈元素并释放旧空间逻辑上消除固定容量限制静态顺序栈存储空间的数组容量是固定好的不可改变元素存储个数锁死但是动态顺序栈的数组本质上就是realloc开辟的连续的内存空间当空间不够可以随意扩容2 链式栈定义链式栈是基于单链表实现的栈结构行业标准做法是将栈顶设置在链表头部所有插入、删除操作都在链表头部完成无需遍历链表。总结受限线性表栈在物理上的存储数据的方式如果采用链式结构就叫做链式栈而链式结构的特点就是空间不连续以节点的方式链接存储数据但是链式结构分多种有带头不带头循环不循环双向不双向的链式结构而最常见的链式栈就是基于单链表这种链式结构实现的链式栈链式栈几乎统一采用单链表实现核心原因是栈的操作特性与单链表的能力完全匹配其他链表的额外功能对栈而言全是冗余只会增加空间开销和实现复杂度没有任何收益。项目内容说明核心前提栈是仅在栈顶一端操作的受限线性表所有核心操作都只针对栈顶元素行业标准做法是将栈顶设置在单链表的头部此时所有操作都可以在 O(1) 时间内完成入栈push采用头插法创建新节点将新节点指针指向原栈顶节点再更新栈顶指针指向新节点全程无需遍历出栈pop采用头删法保存栈顶节点数据将栈顶指针后移至下一节点释放原栈顶节点全程无需遍历取栈顶/判空直接读取头指针指向的节点数据或判断头指针是否为空最终结论单链表的能力刚好覆盖栈的全部操作需求时间复杂度已经达到理论最优没有进一步优化的空间总结单链表可以进行头删头插和尾删尾插但是链式栈规定了只能在一端也就是栈顶进行插入删除操作那我们要选择单链表的头插头删还是尾删尾插呢我们选择的是头删和头插因为如果选择尾删和尾插由于单链表是单向的每一次进行尾插和尾删的操作都需要从头节点遍历到尾节点这样时间复杂度就变成了O(n),但是如果把栈顶定义在单链表头部那只需要进行头删头插不需要遍历链表因为链表的起点就是头部时间复杂度就变成了O(1)。单链表的能力刚好覆盖栈的全部操作需求时间复杂度已经达到理论最优没有进一步优化的空间也就是说功能更多的链式结构比如循环双向等链表不能对单链式结构的栈进一步优化虽然多了功能但是对于实现栈而言单链表就能满足栈的所有需求了以及复杂度最优其他更复杂的链式结构并不能优化栈的需求所以最优的选择就是基于单链表实现栈维度具体描述整体结论单链表的实现与维护成本最低节点结构结构最简单仅包含数据域 一个后继指针内存占用最小指针维护维护指针最少仅需一个栈顶指针头指针不需要尾指针、前驱指针操作逻辑逻辑最简洁入栈出栈仅需修改 1~2 个指针边界条件少调试和出错概率低三 顺序栈和链式栈的选择不存在绝对的 “谁更优”二者是不同设计取舍下的产物但在绝大多数工程实践和刷题场景中顺序栈是更主流、综合表现更好的选择。二者的核心差异本质是「连续数组 vs 离散链表」的底层差异在栈结构上的体现。对比维度顺序栈动态数组实现链式栈单链表实现运行性能综合性能更优。内存连续空间局部性好CPU 缓存命中率高仅扩容时存在一次性 O(n) 开销平摊时间复杂度仍为 O(1)绝对速度更慢。节点离散分布缓存命中率低入栈伴随内存申请、出栈伴随内存释放优势是性能稳定无扩容抖动单次操作耗时恒为 O(1)空间效率低负载时存在预分配闲置空间浪费元素装满后无额外开销单位元素内存占用更低无闲置空间浪费但每个节点固定携带指针开销元素总量越大额外空间成本越高实现与维护成本极低。仅需数组 一个整型栈顶下标变量边界条件少调试简单偏高。在手动内存管理语言中需处理节点申请与释放指针操作多易出现野指针、内存泄漏带 GC 的语言中该风险显著降低容量特性依赖连续大块内存内存碎片化严重时扩容可能失败最终受系统总内存限制仅需离散小块内存碎片化场景下分配成功率更高最终同样受系统总内存限制不存在真正的无限容量四 顺序栈的实现1 Test.c#define_CRT_SECURE_NO_WARNINGS1#includeStack.hintmain(){ST s;STInit(s);STPush(s,1);STPush(s,2);STPush(s,3);STPush(s,4);STPush(s,5);ST*pss;while(!STEmpty(s)){inttopSTTop(s);printf(%d ,top);STPop(s);}STDesTroy(s);return0;}2 Stack.h#define_CRT_SECURE_NO_WARNINGS1#includestdio.h#includeassert.h#includestdlib.h#includestdbool.htypedefintSTDataType;typedefstructstack{STDataType*a;inttop;//栈顶下标同时等于栈有效元素个数intcapacity;//栈的空间大小}ST;//栈初始化voidSTInit(ST*ps);//栈销毁voidSTDesTroy(ST*ps);//入栈voidSTPush(ST*ps,STDataType x);//出栈voidSTPop(ST*ps);//取栈顶元素STDataTypeSTTop(ST*ps);//栈元素个数intSTSize(ST*ps);//判断空栈boolSTEmpty(ST*ps);3 Stack.c#define_CRT_SECURE_NO_WARNINGS1#includeStack.h//栈初始化voidSTInit(ST*ps){assert(ps);ps-aNULL;ps-top0;ps-capacity0;}//栈销毁voidSTDesTroy(ST*ps){assert(ps);free(ps-a);ps-aNULL;ps-topps-capacity0;}//入栈voidSTPush(ST*ps,STDataType x){assert(ps);if(ps-topps-capacity){intnewcapacityps-capacity0?4:2*ps-capacity;STDataType*tmp(STDataType*)realloc(ps-a,newcapacity*sizeof(STDataType));if(tmpNULL){perror(realloc:);return0;}ps-atmp;ps-capacitynewcapacity;}ps-a[ps-top]x;}//出栈voidSTPop(ST*ps){assert(ps);assert(!STEmpty(ps));ps-top--;}//取栈顶STDataTypeSTTop(ST*ps){assert(ps);assert(!STEmpty(ps));returnps-a[ps-top-1];}//栈元素个数intSTSize(ST*ps){assert(ps);returnps-top;}//判断空栈boolSTEmpty(ST*ps){assert(ps);returnps-top0;}五 顺序栈的解析1 Test.c解析#define_CRT_SECURE_NO_WARNINGS1#includeStack.hintmain(){ST s;STInit(s);STPush(s,1);STPush(s,2);STPush(s,3);STPush(s,4);STPush(s,5);ST*pss;while(!STEmpty(s)){inttopSTTop(s);printf(%d ,top);STPop(s);}STDesTroy(s);return0;}解析用栈的结构体类型创建一个结构体变量ST s然后在主函数中使用栈初始化函数先给栈结构体初始化再对栈进行操作如果需要打印栈元素的话使用while循环打印栈元素while循环的判断条件为栈是否为为空栈一旦为空栈说明栈内元素已经全部打印完成循环体中先拿出栈顶元素打印完成以后去除栈顶元素因为栈是后进先出所以我们打印的顺序是从栈顶开始。最后一步要对栈进行销毁2 Stack.h解析#define_CRT_SECURE_NO_WARNINGS1#includestdio.h#includeassert.h#includestdlib.h#includestdbool.h//栈初始化voidSTInit(ST*ps);//栈销毁voidSTDesTroy(ST*ps);//入栈voidSTPush(ST*ps,STDataType x);//出栈voidSTPop(ST*ps);//取栈顶元素STDataTypeSTTop(ST*ps);//栈元素个数intSTSize(ST*ps);//判断空栈boolSTEmpty(ST*ps);解析写入所以栈操作函数和需要用到的库函数最后Test.c包含Stack.h就能拿到所以栈操作函数对栈进行操作了Stack.c函数包含Stack.h就能拿到栈结构体类型就可以在操作函数就能识别栈结构体类型typedefintSTDataType;typedefstructstack{STDataType*a;inttop;//栈顶下标同时等于栈有效元素个数intcapacity;//栈的空间大小}ST;解析创建栈结构体类型a为栈元素存放的内存空间的起始地址也就是realloc开辟的动态内存空间的起始地址用a这个指针变量接收而栈的元素类型重命名为STDataType方便使用然后设置int top 作为栈顶下标a[top-1]就可以用下标引用操作符通过栈顶元素下一个位置下标找到栈顶元素同时设置的top初始化为0也就是指向栈元素的下一个元素位置这时候top的值等于栈有效的元素个数最后设置capacity记录栈空间的大小如果栈空间不够则进行扩容3 Stack.c解析1 栈初始化//栈初始化voidSTInit(ST*ps){assert(ps);ps-aNULL;ps-top0;ps-capacity0;}解析断言ps传入的必须是栈结构体地址不能为NULL将a初始化为NULLtop和capacity初始化为0这时候的top既代表了栈顶元素的下一个位置的下标也代表了栈内有效元素的个数2 栈销毁//栈销毁voidSTDesTroy(ST*ps){assert(ps);free(ps-a);ps-aNULL;ps-topps-capacity0;}解析断言栈地址是否有效不能为NULL是否ps-a中的动态开辟的地址然后把a置为NULL然后把top和capacity置为03 入栈//入栈voidSTPush(ST*ps,STDataType x){assert(ps);if(ps-topps-capacity){intnewcapacityps-capacity0?4:2*ps-capacity;STDataType*tmp(STDataType*)realloc(ps-a,newcapacity*sizeof(STDataType));if(tmpNULL){perror(realloc:);return0;}ps-atmp;ps-capacitynewcapacity;}ps-a[ps-top]x;}解析入栈就是在栈顶插入元素就是在数组中按下标顺序放置栈元素即可在顺序表中就是尾插操作只对尾部进行操作先判断ps是否为NULL然后判断栈内空间是否够如果不够则进行扩容这段扩容操作不需要独立封装成一个扩容函数因为栈操作中需要插入元素的操作只有入栈插入元素就需要判断栈空间的大小是否够如果空间不够则要进行栈空间的扩容再进行插入操作。满栈的判断条件就是top capacity ,当栈内有效元素个数等于栈空间大小则代表满栈这时候就要进行扩容操作capacity是记录栈空间大小的整形扩容我们选用一次两倍扩容的方法但是我们初始化的时候capacity为0a为NULL也就是说当栈仅仅被初始化没有进行任何入栈操作的时候栈此时为NULL没有任何栈元素capacity为0如果对0进行2倍扩容结果依然是0所以我们要使用三目操作符进行判断当ps-capacity为0的时候说明这时候栈是仅仅被初始化的没有入栈栈为空我们就先给栈分配四个栈元素的空间如果ps-capacity!0则说明栈不为NULL可以直接进行二倍扩容操作这时候我们通过了三目操作符就拿到了整形newcapacity这时候通过newcapacity作为栈元素的个数和sizeof(STDataType)相乘的大小作为realloc的第二个参数就是realloc需要开辟的栈空间的字节数大小而第一个参数就是动态内存空间的起始地址也就是a当栈为空栈的时候a 为 NULL这时候的realloc就相当于malloc的作用直接开辟动态内存空间然后返回开辟的动态内存空间的起始地址此时的起始地址是void*类型我们需要强制类型转化为栈元素类型的地址用tmp接收开辟好的空间的起始地址判断是否为NULL,为NULL则代表开辟失败perror打印错误信息不为NULL则代表开辟成功我们将开辟成功的栈空间的起始地址tmp赋给a将newcapacity赋给capacity到了这一步栈内存空间扩容的问题已经解决需要进行入栈操作将x放入下标为top的位置进行插入插入完以后top4 出栈//出栈voidSTPop(ST*ps){assert(ps);assert(!STEmpty(ps));ps-top--;}解析之前就解析过我们打印操作和读取操作都是通过top作为下标来进行top作为下标指向的位置为栈顶元素的下一个位置那么则代表top位置是没有有效元素的所以只要top的位置发生变化就可以修改可以访问栈元素的范围所以出栈直接进行top–即可5 取栈顶//取栈顶STDataTypeSTTop(ST*ps){assert(ps);assert(!STEmpty(ps));returnps-a[ps-top-1];}解析取栈顶的返回值类型是STDataType类型判断ps是否为NULL再判断栈是否为NULL,top是栈顶元素的下一个位置那么top-1就是栈顶元素的下标通过下标引用操作符找到top-1下标对应位置的元素返回即可6 栈元素个数//栈元素个数intSTSize(ST*ps){assert(ps);returnps-top;}解析:top等于栈有效元素个数直接返回即可7 判断空栈//判断空栈boolSTEmpty(ST*ps){assert(ps);returnps-top0;}解析判断是否为空栈返回判断表达式的结果即可如果top 0则代表栈中有效的元素个数为0表达式为真返回true,如果top 0 则代表栈中有效元素个数不为0表达式为假返回falsetrue和false都是bool类型的值所以返回值类型为bool类型点击表格内对应链接跳转对应内容⬇️⬇️⬇️作者主页吃透C语言专栏数据结构Gitee仓库