目录
一、栈的概念与结构
1.1栈的概念
1.2栈的结构
二、栈的实现
2.1开始前准备stack.h
2.2栈的初始化STInit
2.3栈的销毁STDestroy
2.4栈顶插入STPush
2.5栈顶删除STPop
2.6取栈顶元素STTop
2.7检查栈是否为空STEmpty
2.8栈的元素个数STSize
一、栈的概念与结构
1.1栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2栈的结构
二、栈的实现
栈的实现既可以用链表又可以用数组，相较而言我们选择用数组来实现。
2.1开始前准备stack.h
我们在开始前应该知道不管哪种数据结构，都要用结构体来实现，下面我们来看一下在栈的结构体中要设置哪些内容，而且为了让栈更灵活，对数据类型也进行重定义。
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 标识栈顶位置的
int capacity;
}ST;2.2栈的初始化STInit
一开始的栈是空栈，所以对栈的初始化是非常有必要的。其中pst->top标识的是栈顶元素的下一个位置（详情可以对照着上面的图看）。
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->capacity = 0;
// 表示top指向栈顶元素的下一个位置
pst->top = 0;
}2.3栈的销毁STDestroy
因为我们学习的是动态开辟空间的栈，所以销毁栈也是不可省略的。
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}2.4栈顶插入STPush
栈顶插入时，我们和顺序表一样，要根据栈顶top和栈容量capacity来选择是否需要扩容，这里我们进行二倍扩容，并用到了三目运算符防止空栈的扩容失败。
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}2.5栈顶删除STPop
栈删除时其实和顺序表一样，只需要让后续无法访问要删除的元素即可，即只需要修改top的值，而且我们的栈内至少要有值，所以我们对top也进行断言判断。
void STPop(ST* pst)
{
assert(pst);
// 不为空
assert(pst->top > 0);
pst->top--;
}2.6取栈顶元素STTop
因为我们top指向的是栈顶元素的下一个位置，所以我们要去栈顶元素的话，其下标是top-1
STDataType STTop(ST* pst)
{
assert(pst);
// 不为空
assert(pst->top > 0);
return pst->a[pst->top - 1];
}2.7检查栈是否为空STEmpty
我们不需要用 if else 进行判断，只需要把 == 0 作为返回条件即可。
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}2.8栈的元素个数STSize
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
