🐸一、栈的概念及结构
🍄1、栈的概念定义
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
- 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
- 出栈：栈的删除操作叫做出栈。出数据也在栈顶。
🍄2、动图演示
🌲入栈
🌲出栈
🌲整体过程
🐸二、栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小
🐸三、数组结构栈详解
🍎创建栈的结构
🥰这里先创建三个文件：
1️⃣：Stack.h文件，用于函数的声明
2️⃣：Stack.c文件，用于函数的定义
3️⃣：Test.c文件，用于测试函数
建立三个文件的目的： 将栈作为一个项目来进行编写，方便我们的学习与观察。
⭕接口1：定义结构体（ST）
🥰请看代码与注释👇
//自定义类型 typedef int STDataType; //创建栈的结构 typedef struct Stack { STDataType* a; int top; int capacity; }ST;
⭕接口2：初始化（STInit）
🥰请看代码与注释👇
//初始化 void STInit(ST* pst) { //断言传入指针不为NULL assert(pst); pst->a = NULL; pst->top = -1; //top指向栈顶数据 pst->top = 0; //top 指向栈顶数据的下一个位置 pst->capacity = 0; }
⭕接口3：销毁（STDestroy）
🥰请看代码与注释👇
//销毁 void STDestroy(ST* pst) { //断言传入指针不为NULL assert(pst); //释放 free(pst->a); pst->a = NULL; pst->capacity = pst->top = 0; }
⭕接口4：入栈（STPush）
🥰请看代码与注释👇
//入栈 void STPush(ST* pst, STDataType x) { if (pst->top == pst->capacity) { int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* temp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType)); if (temp == NULL) { perror("realloc fail"); return; } pst->a = temp; pst->capacity = newCapacity; } pst->a[pst->top] = x; pst->top++; }
⭕接口5：出栈（STPop）
🥰请看代码与注释👇
//出栈 void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; }
