“但有一枝堪比玉，何须九畹始征兰?”
前言：
栈是一种特殊的线性表，就像开盖的桶一样，从底部开始放数据，从顶部开始取数据，那么栈具体是如何实现的呢？这篇博客为你解答：
目录
💩Part1：何为栈
1.栈的概念
2.栈的结构
🪲Part2: 栈的实现
1.前期准备
1.1创建项目
1.2栈的结构
1.3栈的初始化
2.相关功能实现
2.1入栈
2.2检测栈是否为空
2.3出栈
2.4获取栈顶元素
2.5获取栈中有效元素的个数
2.6销毁栈
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; }
总结：
栈也是线性表，具有后进先出的特点，在有这总需求的情况下可以应用，你学会了吗？
