1.栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底,栈中的数据元素遵守 后进先出LIFO（Last In First Out） 的原则
2.栈的结构
由于栈后进先出的特点，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比小。实现类似于顺序表，结构包括一个数组指针，指向存储数据的数组，再就是一个指向栈顶的指针，因为压栈时如果栈满了需要动态开辟空间，所以这里还需要定义一个容量
//数据类型 typedef int STDataType; //栈信息结构 typedef struct Stack { STDataType* a;//数组 int top;// 初始为0，表示栈顶位置下一个位置的下标 int capacity;// 容量 }ST;
图示：
3.接口实现
3.1初始化栈
将数组指针a置空，同时开辟出起始空间容量，并将栈顶初始化为0，这里栈顶也可以初始化为-1，如果初始化为0，取栈顶就是取下标为top-1位置处的元素，如果初始化为-1，取栈顶就是取的下标为top位置处的元素
//初始化栈 void StackInit(ST* ps) { assert(ps); //开辟起始空间 ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL)//判断开辟成功 { perror("malloc fail"); exit(-1); } ps->top = 0; ps->capacity = 4;//初始容量 }
3.2判断栈是否为空
根据前面的初始化，如果top指针在下标为0的位置栈就为空，返回其布尔值即可
//判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); //返回top指针是否在下标为0的位置 return ps->top == 0; }
3.3压栈（入栈）
首先要考虑扩容问题，避免空间不够还要压栈，这里断言ps是为了防止人为不小心传空，然后将数据放入下标为top的位置，再将top++后移一个位置即可，此时栈顶的下标top代表的就是栈中数据的个数
//压栈（入栈） void StackPush(ST* ps, STDatatype x) { assert(ps); // 判断扩容 if (ps->top == ps->capacity) { STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype)); if (tmp == NULL)//判断开辟成功 { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } //先将top位置放入数据，再将top++后移 ps->a[ps->top] = x; ps->top++; }
3.4出栈
首先断言栈为空的情况，栈空不能出栈，然后出栈操作只需要将top指针减一改变栈顶位置为原栈顶的下一个元素即可，这里不需要将原栈顶置零，后面再进行压栈操作时自然会将其覆盖掉
//出栈 void StackPop(ST* ps) { assert(ps); //断言栈为空 assert(!StackEmpty(ps)); //栈顶下标后移一位 ps->top--; }
3.5查看栈顶元素
首先断言栈为空的情况，栈为空无栈顶元素，然后将下标为top-1的栈顶元素返回即可
//查看栈顶元素 STDatatype StackTop(ST* ps) { assert(ps); //断言栈为空 assert(!StackEmpty(ps)); //返回栈顶元素 return ps->a[ps->top - 1]; }
3.6统计栈内元素个数
栈顶的下标top代表的就是栈中数据的个数,将其返回即可
//统计栈内元素个数 int StackSize(ST* ps) { assert(ps); //返回栈顶下标 return ps->top; }
3.7销毁栈
销毁栈我们直接释放掉存储栈的数组，再将数组指针置空（避免野指针），最后将栈顶指针和容量置零即可
//销毁栈 void StackDestroy(ST* ps) { assert(ps); //释放数组 free(ps->a); ps->a = NULL;//置空 ps->top = ps->capacity = 0;//置零 }
栈的实现到这里就介绍结束了，期待大佬们的三连！你们的支持是我最大的动力！
文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正。
