一、栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除 操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out） 的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
二、栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上 插入数据的代价比较小
// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 栈顶int _capacity; // 容量
}Stack;
三、实现栈的函数
（1）.初始化栈 void StackInit(Stack* ps);
代码执行过程：
1. 首先使用断言（ assert ）确保传入的指针 ps 非空。如果 ps 为空指针，程序会终止并输出错误信息。
2. 尝试为栈分配一块初始大小为 4 个 STDataType 类型元素的内存空间。如果分配失败，打印“ malloc fail ”并退出程序。
3. 设置栈的容量为 4 。
4. 将栈顶指针 top 初始化为 0 ，表示此时栈为空， top 指向栈顶元素的下一个位置。
//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if(ps->a==NULL){printf("malloc fail\n");exit(-1);}ps->capacity = 4;ps->top = 0;//意味着top指向栈顶元素的下一个
}（2）.入栈 void StackPush(Stack* ps, STDataType data);
代码执行过程：
1. 首先使用断言确保传入的栈指针非空。
2. 检查栈是否已满，即栈顶指针 top 是否等于栈的容量 capacity 。
- 如果栈已满，尝试使用 realloc 函数将栈的内存空间扩大一倍。如果分配失败，打印“ realloc fail ”并退出程序；如果成功，更新栈的内存指针 a 和容量 capacity 。
3. 将元素 x 存入栈顶位置，即 ps->a[ps->top] ，然后将栈顶指针 top 加一，表示栈中元素数量增加了一个。
// 入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//容量已满if (ps->top == ps->capacity){STDataType*tmp = (STDataType*)realloc(ps->a,ps->capacity*sizeof(STDataType) * 2);if (tmp== NULL){printf("realloc fail\n");exit(-1);}else{ps->a = tmp;ps->capacity *= 2;}}ps->a[ps->top] = x;ps->top++;}（3）.出栈 void StackPop(Stack* ps);
代码执行过程：
1. 首先使用断言确保传入的栈指针非空。
2. 再次使用断言确保栈非空，即栈顶指针 top 大于 0。如果栈为空时调用此函数，程序会终止并报错。
3. 将栈顶指针 top 减一，实现出栈操作，即逻辑上移除了栈顶元素。
// 出栈
void StackPop(ST* ps)
{assert(ps);//栈空了，调用Pop直接终止程序报错assert(ps->top>0);ps->top--;
}（4）. 获取栈顶元素 STDataType StackTop(Stack* ps);
代码执行过程：
1. 首先使用断言确保传入的栈指针非空。
2. 再次使用断言确保栈非空，即栈顶指针 top 大于 0。如果栈为空时调用此函数，程序会终止并报错。
3. 返回栈顶元素，通过 ps->a[ps->top - 1] 获取，因为 top 指向栈顶元素的下一个位置，所以需要减一来得到栈顶元素的索引。
//取栈顶元素的接口
STDataType StackTop(ST* ps)
{assert(ps);//栈空了，调用Top直接终止程序报错assert(ps->top > 0);return ps->a[ps->top - 1];
}（5）.获取栈中有效元素个数 int StackSize(Stack* ps);
代码执行过程：
1. 首先使用断言确保传入的栈指针非空。
2. 直接返回栈顶指针 top 的值，因为 top 指向栈顶元素的下一个位置，所以其值就代表了栈中数据的个数。
//求数据个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}（6）.检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
代码执行过程：
1. 首先使用断言确保传入的栈指针非空。
2. 通过检查栈顶指针 top 是否为 0 来判断栈是否为空。如果 top 为 0，则表示栈中没有元素，返回 true ；否则返回 false
//判断是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top==0;
}（7）.销毁栈 void StackDestroy(Stack* ps);
代码执行过程：
1. 首先使用断言确保传入的栈指针非空。
2. 使用 free 函数释放栈中存储数据的动态分配内存 ps->a 。
3. 将指针 ps->a 置为 NULL ，防止出现悬空指针。
4. 将栈顶指针 ps->top 和容量 ps->capacity 都置为 0，表示栈被完全销毁，处于初始状态。
//摧毁
void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}
