【数据结构】栈——超详解！！！（包含栈的实现）

前言

往期我们的学习中讲到了顺序表以及链表
它们可以帮我们解决很多问题，而类似的数据结构还有很多
今天，我们就来聊聊——栈

一、栈是什么？

栈：
一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

注意：
本文我们讲的栈是数据结构里的栈，而不是在操作系统中提到的栈
二者同名不同理，相当与两个不同学科的概念，大家不要搞混淆了

1. 后进先出（LIFO）

那么什么是后进先出呢？

如图：

后进先出，故名思意，就是先进去的数据后出来，而后进去的数据先出来
就如同枪上的弹夹一样,先压进去的子弹后打出去，而后压进去的子弹先打出去

2. 压栈&&出栈

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶
入数据在栈顶,出数据也在栈顶

二、栈的实现

1. 用什么来实现？

栈的实现一般可以使用数组或者链表实现，而相对而言数组的结构实现更优一些。
但前面我们讲顺序表的时候提到，在顺序表中进行插入删除数据很麻烦，那为什么又要用数组呢？
这就要看到栈的定义了
栈只允许在固定的一端进行插入和删除元素操作，而在数组中避免了中间数据的插入与删除
就是因为数组在尾上插入删除数据的代价比较小，所以使用数组来实现栈

2. 实现思路

这里可以拿顺序表来做参考，往期我们详解了顺序表的实现，大家感兴趣的可以去看看
链接：【C语言】数据结构——顺序表超详解!!!（包含顺序表的实现)

与顺序表同理，栈的实现也应该有三名成员：
1.指向一个数组的指针
2.栈内的总元素
3.栈内的总容量

3.注意

但是，要十分注意一个点，这个点将贯穿我们整段代码！！！
注意：栈只允许在固定的一端进行插入和删除元素操作
当我们在写实现代码时，要注意栈只允许在固定的一端进行插入和删除元素操作
不能在两端同时进行操作，不然就不是栈了！！！
要遵循先进后出的基本原则

所以，在插入数据时我们选择尾插，而在取出数据时，我们选择头取

4. 代码实现

本文以创建一个int类型的栈为例

（1）创建头文件&源文件

之前在讲解扫雷游戏中我就提到:
在写复杂程序时要养成写多个头文件&源文件的好习惯，这样条理就很清晰也不会乱

详见【C语言】扫雷游戏详解（包含递归，变色，记录时间等）

如图:
创建了一个“ Stack.h "头文件
用于存放用来放函数的声明和一些库函数的头文件
创建了一个“ Stack.c "源文件
用于用来放函数的定义(栈的主体)
还有一个” Test.c "源文件
用于测试实现的栈的运行效果

（2）定义栈（定义）

首先我们要定义一个栈

代码演示：（内有注释）
（在头文件“ Stack.h "中写）

//重定义，方便修改类型typedefintSTDataType;//定义栈typedefstructStack{STDataType*a;//数组指针intsize;//总元素intcapacity;//容量}Stack;

在定义栈代码中，有两个需要注意的点：

1. 本文是以int类型为例，但如果以后要将顺序表修改成char类型或是其他类型一个一个修改就很麻烦
   所以我们重定义int类型为STDataType,并将接下来代码中的int类型全部写成STDataType
   这是为了方便我们以后对类型进行修改，仅需将int改为其他类型即可
2. 在定义栈的同时重定义栈变量名为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语句{//先设置新变量，增容后再赋值intnewcapacity=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 "头文件中写到：

// 获取栈顶元素STDataTypeStackTop(Stack*ps);

在“ Stack.c "源文件中写到：

// 获取栈顶元素STDataTypeStackTop(Stack*ps){assert(ps&&ps->size>0);//断言空指针//断言顺序表不能为空returnps->a[ps->size-1];}

（8）获取栈中有效元素个数

这个很简单
直接返回所对应的值

代码演示：（内有注释）
（其中 ps 是一个栈指针类型的指针，下同）

在“ Stack.h "头文件中写到：

// 获取栈中有效元素个数intStackSize(Stack*ps);

在“ Stack.c "源文件中写到：

// 获取栈中有效元素个数intStackSize(Stack*ps){assert(ps);//断言空指针returnps->size;}

（9）检测栈是否为空

这个很简单
如果栈为空返回非零结果
如果不为空返回0

代码演示：（内有注释）
（其中 ps 是一个栈指针类型的指针，下同）

在“ Stack.h "头文件中写到：

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0intStackEmpty(Stack*ps);

在“ Stack.c "源文件中写到：

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0intStackEmpty(Stack*ps){assert(ps);//断言空指针returnps->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>//重定义，方便修改类型typedefintSTDataType;//定义栈typedefstructStack{STDataType*a;//数组指针intsize;//总元素intcapacity;//容量}Stack;// 初始化栈voidStackInit(Stack*ps);// 入栈voidStackPush(Stack*ps,STDataType data);// 出栈voidStackPop(Stack*ps);// 获取栈顶元素STDataTypeStackTop(Stack*ps);// 获取栈中有效元素个数intStackSize(Stack*ps);// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0intStackEmpty(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语句{//先设置新变量，增容后再赋值intnewcapacity=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 就行//这样也不会影响到后面的 增、删、查、改}// 获取栈顶元素STDataTypeStackTop(Stack*ps){assert(ps&&ps->size>0);//断言空指针//断言顺序表不能为空returnps->a[ps->size-1];}// 获取栈中有效元素个数intStackSize(Stack*ps){assert(ps);//断言空指针returnps->size;}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0intStackEmpty(Stack*ps){assert(ps);//断言空指针returnps->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);intret1=StackTop(&S);StackPop(&S);intret2=StackTop(&S);StackPop(&S);intret3=StackTop(&S);printf("%d %d %d",ret1,ret2,ret3);printf("\n\n");StackDestroy(&S);return0;}

结语

本期资料来自于：

https://legacy.cplusplus.com/

OK，本期的栈详解到这里就结束了

若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持

本文有若有不足之处，希望各位兄弟们能给出宝贵的意见。谢谢大家！！！

新人，本期制作不易希望各位兄弟们能动动小手，三连走一走！！！

支持一下（三连必回QwQ）