栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的实现过程
栈可以使用两种主要的数据结构实现：数组和链表。
使用数组实现的栈称为顺序栈（或者静态栈），其基本操作的时间复杂度为 O(1)。在实现时需要预先分配一定大小的数组作为存储空间，当栈的元素个数超过数组的大小时，需要进行扩容操作。
使用链表实现的栈称为链式栈（或者动态栈），其基本操作的时间复杂度同样为 O(1)。相比顺序栈，链式栈没有固定的大小限制，可以动态添加和删除节点，因此实现上更为灵活。
除了以上两种主要的数据结构，还有一些其他的数据结构可以用于实现栈，例如双向链表等。但是在实际应用中，数组和链表是最常见的两种栈实现方式。
栈的结构体与接口的定义
1、静态栈结构
定长的静态栈结构
代码如下：
typedef int STDataType; #define N 10 typedef struct Stack { STDataType _a[N]; int _top; // 栈顶 }Stack;
2、动态栈结构
静态结构实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
代码如下：
typedef int STDataType; typedef struct Stack { STDataType* a; int top; //栈顶 int capacity;//容量 }ST;
虽然这里使用的是动态扩容
但还是用顺序结构来实现栈
以便于初学者的理解
3、栈的接口定义
代码如下：
void StackInit(ST* ps);//初始化栈 void StackPush(ST* ps, STDataType x);//入栈 void StackPop(ST* ps);// 出栈 STDataType StackTop(ST* ps);// 获取栈顶元素 int StackSize(ST* ps);// 获取栈中有效元素个数 bool StackEmpty(ST* ps);// 检测栈是否为空，如果为空返回ture，如果不为空返回false void StackDestroy(ST* ps);// 销毁栈
可以看到栈的接口函数比起之前的顺序表和链表都要简单很多
其实实现起来也是非常的简单，接下来我们实现这些接口
栈的接口实现
①初始化栈(StackInit)
代码如下：
void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; // ps->top = -1; ps->capacity = 0; }
栈的初始化先将元素置空，栈顶指向0，当然你也可以指向-1，后面的接口函数也要做相应调整，可以根据自己习惯来设定，没有固定标准，然后容量初始化为0。
②入栈(StackPush)
代码如下：
void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; }
入栈的写法有点类似顺序表的尾插，首先是一个经典的三目操作符判断容量，容量不够则进行增容，再向内存申请空间，这里的if是为了防止申请失败而找不到中断原因写的一个提示，类似断言，将元素插入，增容，再将栈顶指向新元素，栈顶++完成入栈操作。
③出栈(StackPop)
代码如下：
void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps));//判断是否为空 ps->top--; }
这里的出栈就很简单了，先进行断言，这里的StackEmpty函数在后面实现，直接将top–就完成出栈操作了。
④栈顶(StackTop)
代码如下：
STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; }
栈顶值返回只要将a[最高位下标]返回即可，如果你初始化定义的top=-1,那么这里就是
ps->a[ps->top]的值了。
⑤栈元素个数(StackSize)
代码如下：
int StackSize(ST* ps) { assert(ps); return ps->top; }
栈元素个数直接返回top值即可，如果你初始化定义的top=-1,那么这里就是top++的值了
⑥检测栈是否为空(StackEmpty)
代码如下：
bool StackEmpty(ST* ps) { assert(ps); if (ps->top == 0) { return true; } else { return false; } }
首先返回类型可以是int，这里我使用bool类型也是一样的，只不过我这返回的是逻辑值true或是false，如果为空返回ture，如果不为空返回false。这段代码还有更简洁的方式，
代码如下：
bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
同样返回的是逻辑值，更简洁高效。
⑦销毁栈(StackDestroy)
代码如下：
void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; }
实现销毁栈，先释放元素所占空间，再置空进行初始化即可。
结语
其实不管是栈还是队列，实现方式也都很简单，虽然简单，但也是同样重要的知识点，一定要好好理解和掌握，这一节就到这里了，下一节我们再讲讲队列的概念及接口实现。
制作不易，如有不正之处敬请指出，感谢大家的来访，UU们的观看是我坚持下去的动力，在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！
