栈：一种操作受限的线性表，只允许在线性表的一端进行插入和删除操作，进行插入删除的一端称作栈顶，另一端称之为栈底
通过动态顺序表的实现，可以发现在对数组进行尾插尾删时效率很高， 因此栈可以用数组实现，将数组的尾部作为栈顶， 结构如下：
通过单链表的实现，可以发现在对链表进行头插头删时效率很高，因此也可以用链表来实现，将单链表的头结点作为栈顶，结构如下：
综合考虑：数组的实现方法更优，本篇以数组的方式介绍栈的结构和函数接口
//栈的元素类型
typedef int StackDataType;
//栈的结构
typedef struct Stack
{
StackDataType* a; //存放元素的数组
int top; //指向栈顶元素的下一个位置
int capacity; //容量
}Stack;
初始时给栈分配一些空间，并将 top置为 0，代表指向栈顶元素的下一个位置
初始化函数如下：
void StackInit(Stack* ps)
{
assert(ps);
//开辟空间
ps->a = (StackDataType*)malloc(sizeof(StackDataType) * 4);
if (ps->a == NULL)
{
perror("malloc");
exit(-1);
}
ps->top = 0;
ps->capacity = 4;
}
栈是动态开辟的，不用时需要销毁
销毁函数如下：
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
入栈：在栈顶插入元素，当空间不够时需要扩容
入栈函数如下：
void StackPush(Stack* ps, StackDataType x)
{
assert(ps);
//空间不够时，需要扩容
if (ps->top == ps->capacity)
{
StackDataType* tmp = (StackDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(StackDataType));
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->a = tmp;
ps->capacity *= 2;
}
//top 指向栈顶元素的下一个位置，因此 top 先插入数据，然后再自增
ps->a[ps->top] = x;
ps->top++;
}
出栈：删除栈顶元素
出栈函数如下：
void StackPop(Stack* ps)
{
assert(ps);
//栈为空时不能删除，这里直接调用判空函数
assert(!StackEmpty(ps));
ps->top--;
}
返回栈顶元素函数如下：
StackDataType StackTop(Stack* ps)
{
assert(ps);
//栈为空时不能取栈顶元素，这里直接调用判空函数
assert(!StackEmpty(ps));
//top 指向栈顶元素的下一个，所以需要-1
return ps->a[ps->top - 1];
}
判空函数如下：
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
元素个数函数如下：
size_t StackSize(Stack* ps)
{
assert(ps);
//top 即为元素个数
return ps->top;
}
