什么是栈，如何实现？
欢迎来到 Claffic 的博客 💞💞💞
“但有一枝堪比玉，何须九畹始征兰?”
前言：
栈是一种特殊的线性表，就像开盖的桶一样，从底部开始放数据，从顶部开始取数据，那么栈具体是如何实现的呢？这篇博客为你解答：
目录
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
拿走不谢~
总结：
栈也是线性表，具有后进先出的特点，在有这总需求的情况下可以应用，你学会了吗？
码文不易
如果你觉得这篇文章还不错并且对你有帮助，不妨支持一波哦 💗💗💗