栈的概念：只能在表尾进行插入（入栈）和删除（出栈）的数据结构（受到限制的线性表）。
表尾比较特殊，我们一般把这个表尾叫做栈顶，另一端栈底。没有数据节点，则叫做空栈
特点：先进后出（FILO）a1最先进栈，a1最后出栈。
为了更好的理解，可以想象生活中的例子：子弹弹夹
直接给出栈的结构体定义：（结构体中需要三个成员）
#define INIT_SIZE 10
typedef int ELEM_TYPE;
typedef struct Stack
{
ELEM_TYPE* base;//一个指针，用来接收malloc从堆内申请的一整块内存
int top;//栈顶指针（和书上不一致，书上是指针类型，我们这里存的是数组下标，所以用int类型，也能达到指针的作用）
int stack_size;//存储当前的最大容量
}Stack, * PStack;
这里的栈顶指针说是指针，但是这里是int类型，存放数组下标，也能达到指针的作用
栈能实现的函数功能声明：
//顺序栈可执行函数的声明
//初始化
void Init_Stack(struct Stack* ps);
//入栈（插入）
bool Push(PStack ps, ELEM_TYPE val);
//出栈（获取删除的栈顶元素值，并且删除） //用到一个输出参数
bool Pop(PStack ps, ELEM_TYPE* rtval);
//获取栈顶元素（获取栈顶元素值，但是不删除） //用到一个输出参数
bool Top(PStack ps, ELEM_TYPE* rtval);
//判空
bool IsEmpty(PStack ps);
//判满
bool IsFull(PStack ps);
//扩容
void Inc(PStack ps);
//获取有效长度
int Get_length(PStack ps);
//清空
void Clear(PStack ps);
//销毁
void Destroy(PStack ps);
//打印
void Show(PStack ps);1.初始化：
void Init_Stack(struct Stack* ps)
{
assert(ps != NULL);
ps->base = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE) * INIT_SIZE);
assert(ps->base != NULL);
if (ps->base == NULL)
{
return;
}
ps->top = 0;
ps->stack_size = INIT_SIZE;
}2.入栈
//入栈（插入）
bool Push(PStack ps, ELEM_TYPE val)
{
assert(ps != NULL);
//入栈需要判满
if(IsFull(ps))
{
Inc(ps);
}
执行到这一行 总会有额外空间去入栈
//ps->base[ps->top] = val;
warning： 插入或删除结束后，记得挪动一下栈顶指针top
//ps->top++;
ps->base[ps->top++] = val;
return true;
}3.出栈
//出栈（获取删除的栈顶元素值，并且删除） //用到一个输出参数
bool Pop(PStack ps, ELEM_TYPE *rtval)
{
assert(ps != NULL);
//出栈需要判空
if(IsEmpty(ps))
{
return false;
}
/*ps->top--;
*rtval = ps->base[ps->top];*/
*rtval = ps->base[--ps->top];
return true;
}
4.获取栈顶元素
//获取栈顶元素（获取栈顶元素值，但是不删除） //用到一个输出参数
bool Top(PStack ps, ELEM_TYPE* rtval)
{
assert(ps != NULL);
if (IsEmpty(ps))
{
return false;
}
*rtval = ps->base[ps->top - 1];
return true;
}5.判空，判满
//判空
bool IsEmpty(PStack ps)
{
assert(ps != NULL);
return ps->top == 0;
}
//判满
bool IsFull(PStack ps)
{
assert(ps != NULL);
return ps->top == ps->stack_size;
}
6.扩容
//扩容
void Inc(PStack ps)
{
assert(ps != NULL);
//当realloc前面参数为0 相当于malloc 当后边参数为0 相当于free
ps->base = (ELEM_TYPE*)realloc(ps->base, sizeof(ELEM_TYPE) * INIT_SIZE * 2);
assert(ps->base != NULL);
ps->stack_size *= 2;
}7.获取有效长度
//获取有效长度
int Get_length(PStack ps)
{
assert(ps != NULL);
return ps->top;
}8.清空（不需要释放malloc申请的空间 ?只需要将栈顶指针改为0 ? 则认为里面数据都失效（没有有效债）），销毁（需要释放malloc申请的空间），打印
//清空 //不需要释放malloc申请的空间 只需要将栈顶指针改为0 则认为里面数据都失效（没有有效债）
void Clear(PStack ps)
{
assert(ps != NULL);
ps->top = 0;
}
//销毁 //需要释放malloc申请的空间
void Destroy(PStack ps)
{
assert(ps != NULL);
free(ps->base);
ps->base = NULL;
ps->stack_size = ps->top = 0;
}
//打印
void Show(PStack ps)
{
assert(ps != NULL);
for (int i = 0; i < ps->top; ++i)
{
printf("%d ", ps->base[i]);
}
printf("\n");
}测试：
int main()
{
struct Stack ps;//建立一个栈
Init_Stack(&ps);//初始化这个栈
printf("Stack_size = %d\n", ps.stack_size);//打印栈的最大容量
for(int i=0; i<15; i++)
{
Push(&ps, i+1);//将1到15入栈
}
Show(&ps);//打印1-15
printf("length = %d\n", Get_length(&ps));//打印栈的有效长度
printf("Stack_size = %d\n", ps.stack_size);//打印栈的最大容量
//出栈顶元素，并且打印出栈后的栈
ELEM_TYPE tmp;
bool tag = false;
tag = Pop(&ps, &tmp);
if(tag)
{
printf("tmp = %d\n", tmp);
}
Show(&ps);
//获取栈顶元素，并且打印栈（没有出栈的栈）
ELEM_TYPE flg;
bool tag2 = Top(&ps, &flg);
if(tag2)
{
printf("flg = %d\n", flg);
}
Show(&ps);
Clear(&ps);//清空
printf("length = %d\n", Get_length(&ps));//清空后打印有效长度
printf("Stack_size = %d\n", ps.stack_size);//打印最大容量
Destroy(&ps); //销毁
//Destroy(&ps);
return 0;
}结果：
?没有内存泄漏。