【数据结构】栈——超详解！！！（包含栈的实现）
【数据结构】栈——超详解！！！（包含栈的实现）
前言
往期我们的学习中讲到了顺序表以及链表
它们可以帮我们解决很多问题，而类似的数据结构还有很多
今天，我们就来聊聊——栈
一、栈是什么？
栈：
一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
注意：
本文我们讲的栈是数据结构里的栈，而不是在操作系统中提到的栈
二者同名不同理，相当与两个不同学科的概念，大家不要搞混淆了
1. 后进先出（LIFO）
那么什么是后进先出呢？
如图：
后进先出，故名思意，就是先进去的数据后出来，而后进去的数据先出来
就如同枪上的弹夹一样,先压进去的子弹后打出去，而后压进去的子弹先打出去
2. 压栈&&出栈
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶
入数据在栈顶,出数据也在栈顶
二、栈的实现
1. 用什么来实现？
栈的实现一般可以使用数组或者链表实现，而相对而言数组的结构实现更优一些。
但前面我们讲顺序表的时候提到，在顺序表中进行插入删除数据很麻烦，那为什么又要用数组呢？
这就要看到栈的定义了
栈只允许在固定的一端进行插入和删除元素操作，而在数组中避免了中间数据的插入与删除
就是因为数组在尾上插入删除数据的代价比较小，所以使用数组来实现栈
2. 实现思路
这里可以拿顺序表来做参考，往期我们详解了顺序表的实现，大家感兴趣的可以去看看
链接：【C语言】数据结构——顺序表超详解!!!（包含顺序表的实现)
与顺序表同理，栈的实现也应该有三名成员：
1.指向一个数组的指针
2.栈内的总元素
3.栈内的总容量
3.注意
但是，要十分注意一个点，这个点将贯穿我们整段代码！！！
注意：栈只允许在固定的一端进行插入和删除元素操作
当我们在写实现代码时，要注意栈只允许在固定的一端进行插入和删除元素操作
不能在两端同时进行操作，不然就不是栈了！！！
要遵循先进后出的基本原则
所以，在插入数据时我们选择尾插，而在取出数据时，我们选择头取
4. 代码实现
本文以创建一个 int 类型的栈为例
（1）创建头文件&源文件
之前在讲解扫雷游戏中我就提到:
在写复杂程序时要养成写多个头文件&源文件的好习惯，这样条理就很清晰也不会乱
如图:
创建了一个 “ Stack.h "头文件
用于存放用来放函数的声明和一些库函数的头文件
创建了一个 “ Stack.c "源文件
用于用来放函数的定义(栈的主体)
还有一个 ” Test.c "源文件
用于测试实现的栈的运行效果
（2）定义栈（定义）
首先我们要定义一个栈
代码演示：（内有注释）
（在头文件“ Stack.h "中写）
//重定义，方便修改类型typedefint STDataType;//定义栈typedefstructStack{ STDataType* a;//数组指针int size;//总元素int capacity;//容量 }Stack;在定义栈代码中，有两个需要注意的点：本文是以int类型为例，但如果以后要将顺序表修改成char类型或是其他类型一个一个修改就很麻烦
所以我们重定义int类型为STDataType,并将接下来代码中的int类型全部写成STDataType
这是为了方便我们以后对类型进行修改，仅需将int改为其他类型即可在定义栈的同时重定义栈变量名为Stack方便以后使用
（3）栈的初始化（初始化）
定义完栈后，肯定要对栈进行初始化，内容全部置 0 / NULL代码演示：（内有注释）
（其中 ps 是一个栈指针类型的指针，下同）
在“ Stack.h "头文件中写到：
// 初始化栈 voidStackInit(Stack* ps);在“ Stack.c "源文件中写到：
// 初始化栈 voidStackInit(Stack* ps){//断言空指针assert(ps); ps->a =NULL; ps->capacity =0; ps->size =0;//全部初始化置 0 / NULL}在写栈代码中，有一个很重要的点：
当我们函数在进行传参时，可能会传入空指针，而我们知道空指针是不能进行解引用的
故为了我们的代码更加健壮，可以加入assert 断言来判断是否符合条件，在之后的代码中也都有
关于更加详细的assert 断言介绍可参见下文：
【C语言】带你层层深入指针——指针详解3（野指针、assert等）
（4）栈的销毁（销毁）
在我们的程序运行完毕后，当然要对栈进行销毁，以免占用内存
代码演示：（内有注释）
（其中 ps 是一个栈指针类型的指针，下同）
在“ Stack.h "头文件中写到：
// 销毁栈voidStackDestroy(Stack* ps);在“ Stack.c "源文件中写到：
//栈的销毁voidStackDestroy(Stack* ps){assert(ps);//断言空指针free(ps->a);//释放内存 ps->a =NULL; ps->capacity =0; ps->size =0;//全部初始化置 0 / NULL}（5）插入数据（入栈）
- 怎么插入？
在入栈时，由于栈只允许在固定的一端进行插入和删除元素操作
所以在插入时一定是尾插数据
- 空间不够时咋办？
栈的空间是动态管理的，故当栈的空间不足时，可再开辟一些空间使用（动态增容）
但是存在一个问题：
我们到底要开辟多大的空间来使用呢？1. 若一次性开辟的空间过大，可能会造成空间的浪费
2. 若一次性开辟的空间过小，就可能会导频繁的开辟空间，这样运行的效率就会大大降低
经过科学研究，发现每次增容 2 倍 & 3 倍 空间最为合适
当原空间为 100 的空间不足时，就增容到 200 空间
（本文选择的是每次增容 2 倍 ）
代码演示：（内有注释）
（其中 ps 是一个栈指针类型的指针，下同）
在“ Stack.h "头文件中写到：
// 入栈 voidStackPush(Stack* ps, STDataType data);在“ Stack.c "源文件中写到：
// 入栈 voidStackPush(Stack* ps, STDataType data){assert(ps);//断言空指针if(ps->size == ps->capacity)//当size=capacity时就表示空间不足，此时需要增容，故进入if语句{//先设置新变量，增容后再赋值int newcapacity = ps->capacity ==0?4:2* ps->capacity;//设置一个三目操作符判断原空间是否为 0//当原空间为0时给空间开辟 4 字节；当原空间不为0时给空间增容 2倍 STDataType* tmp =(STDataType*)realloc(ps->a, newcapacity *sizeof(STDataType));//由于是在原空间的基础上给空间增容，故我们这里使用 realloc函数 增容//增容大小为上面的 newcapacity *（类型大小）if(tmp ==NULL)//加一个 if语句 防止增容失败{perror("realloc");return;}//没有问题后就赋值 ps->a = tmp; ps->capacity = newcapacity;} ps->a[ps->size]= data; ps->size++;}（6）删除数据（出栈）
这个很简单，直接用下标进行删除数据
再对size–即可
但要注意：
栈只允许在固定的一端进行插入和删除元素操作
我们在尾端进行插入数据，就也要在尾端进行删除数据
代码演示：（内有注释）
（其中 ps 是一个栈指针类型的指针，下同）
在“ Stack.h "头文件中写到：
// 出栈 voidStackPop(Stack* ps);在“ Stack.c "源文件中写到：
// 出栈 voidStackPop(Stack* ps){assert(ps && ps->size >0);//断言空指针//断言顺序表不能为空 ps->size--;//将元素个数进行 -1 就行//这样也不会影响到后面的 增、删、查、改}（7）获取栈顶元素
这个很简单，直接用下标进行访问数据
再返回所对应的值
但要注意：
栈只允许在固定的一端进行插入和删除元素操作
之前在尾端进行插入删除数据，就也要在尾端获取栈顶元素
代码演示：（内有注释）
（其中 ps 是一个栈指针类型的指针，下同）
在“ Stack.h "头文件中写到：
// 获取栈顶元素 STDataType StackTop(Stack* ps);在“ Stack.c "源文件中写到：
// 获取栈顶元素 STDataType StackTop(Stack* ps){assert(ps && ps->size >0);//断言空指针//断言顺序表不能为空return ps->a[ps->size -1];}（8）获取栈中有效元素个数
这个很简单
直接返回所对应的值
代码演示：（内有注释）
（其中 ps 是一个栈指针类型的指针，下同）
在“ Stack.h "头文件中写到：
// 获取栈中有效元素个数 intStackSize(Stack* ps);在“ Stack.c "源文件中写到：
// 获取栈中有效元素个数 intStackSize(Stack* ps){assert(ps);//断言空指针return ps->size;}（9）检测栈是否为空
这个很简单
如果栈为空返回非零结果
如果不为空返回0
代码演示：（内有注释）
（其中 ps 是一个栈指针类型的指针，下同）
在“ Stack.h "头文件中写到：
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intStackEmpty(Stack* ps);在“ Stack.c "源文件中写到：
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intStackEmpty(Stack* ps){assert(ps);//断言空指针return ps->size ==0;}三、完整代码实现
1. Stack.h
用于存放用来放函数的声明和一些库函数的头文件
#pragmaonce#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>#include<sperror.h>//重定义，方便修改类型typedefint STDataType;//定义栈typedefstructStack{ STDataType* a;//数组指针int size;//总元素int capacity;//容量 }Stack;// 初始化栈 voidStackInit(Stack* ps);// 入栈 voidStackPush(Stack* ps, STDataType data);// 出栈 voidStackPop(Stack* ps);// 获取栈顶元素 STDataType StackTop(Stack* ps);// 获取栈中有效元素个数 intStackSize(Stack* ps);// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intStackEmpty(Stack* ps);// 销毁栈voidStackDestroy(Stack* ps);2. Stack.c
用于用来放函数的定义(栈的主体)
#include"Stack.h"// 初始化栈 voidStackInit(Stack* ps){//断言空指针assert(ps); ps->a =NULL; ps->capacity =0; ps->size =0;//全部初始化置 0 / NULL}// 入栈 voidStackPush(Stack* ps, STDataType data){assert(ps);//断言空指针if(ps->size == ps->capacity)//当size=capacity时就表示空间不足，此时需要增容，故进入if语句{//先设置新变量，增容后再赋值int newcapacity = ps->capacity ==0?4:2* ps->capacity;//设置一个三目操作符判断原空间是否为 0//当原空间为0时给空间开辟 4 字节；当原空间不为0时给空间增容 2倍 STDataType* tmp =(STDataType*)realloc(ps->a, newcapacity *sizeof(STDataType));//由于是在原空间的基础上给空间增容，故我们这里使用 realloc函数 增容//增容大小为上面的 newcapacity *（类型大小）if(tmp ==NULL)//加一个 if语句 防止增容失败{perror("realloc");return;}//没有问题后就赋值 ps->a = tmp; ps->capacity = newcapacity;} ps->a[ps->size]= data; ps->size++;}// 出栈 voidStackPop(Stack* ps){assert(ps && ps->size >0);//断言空指针//断言顺序表不能为空 ps->size--;//将元素个数进行 -1 就行//这样也不会影响到后面的 增、删、查、改}// 获取栈顶元素 STDataType StackTop(Stack* ps){assert(ps && ps->size >0);//断言空指针//断言顺序表不能为空return ps->a[ps->size -1];}// 获取栈中有效元素个数 intStackSize(Stack* ps){assert(ps);//断言空指针return ps->size;}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intStackEmpty(Stack* ps){assert(ps);//断言空指针return ps->size ==0;}// 销毁栈 voidStackDestroy(Stack* ps){assert(ps);//断言空指针free(ps->a);//释放内存 ps->a =NULL; ps->capacity =0; ps->size =0;//全部初始化置 0 / NULL}3. Test.c
用于测试实现的栈的运行效果
（这里是小编在写代码时写的测试用例）
#include"Stack.h"intmain(){ Stack S;StackInit(&S);StackPush(&S,1);StackPush(&S,2);StackPush(&S,3);StackPush(&S,4);StackPush(&S,5);StackPush(&S,6);StackPop(&S);int ret1 =StackTop(&S);StackPop(&S);int ret2 =StackTop(&S);StackPop(&S);int ret3 =StackTop(&S);printf("%d %d %d", ret1, ret2, ret3);printf("\n\n");StackDestroy(&S);return0;}结语
本期资料来自于：
OK，本期的栈详解到这里就结束了
若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持
本文有若有不足之处，希望各位兄弟们能给出宝贵的意见。谢谢大家！！！
新人，本期制作不易希望各位兄弟们能动动小手，三连走一走！！！
支持一下（三连必回QwQ）
