用动图详细讲解——栈

栈的概念：

---

栈：

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，是操作受到限制的线性表，遵行后进先出LIFO（Last In First Out）的原则。

简单理解就是一个一端封口，另一端没有封口的管子，你往里面放直径与管子的直径相同的球，不管你放多少球，你先取的一定是最后放的球，最里面的球要把前面的球全部取出来才能取到。这个管子里的空间就相当于栈的空间，球就相当于你所要放入栈的数据

---

栈顶和栈底

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，非空栈中的栈顶指针始终在栈顶元素的下一个位置上，空栈时，栈顶指针和栈底指针指向同一块位置。

借助管子和球的例子，简单理解就是管子封口那里就是栈底，管子中最外层的球的下一个可以存放球的空间，但还没有存放球的位置就是栈顶，不能直接理解为管口就是栈顶。

当管子中没有球时（空栈），栈顶和栈底所指向的位置相等，都指向管子最里面所能存放一个球的空间

---

压栈和出栈

栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶，栈的删除操作叫做出栈。出数据也在栈顶。

入栈gif动画

出栈gif动画

---

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾部插入数据的代价比较小，可以根据下标直接锁定尾部。
用链表(无头单向非循环链表)在尾部插入数据的代价比较大，需要先遍历一遍才能找到尾部，但也不是不可以，不过尽量用数组比较好一些。

对于栈的实现，有这几个功能，

1. 初始化栈
2. 检测栈的容量是否充足(不充足进行扩容)
3. 入栈
4. 出栈
5. 获取栈顶元素
6. 获取栈中有效元素个数
7. 检测栈是否为空(为空返回非0结果，不为空返回0）
8. 销毁栈

我们将用函数对这些功能进行封装

---

用结构体自定义一个栈的数据类型

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
   
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
1
2
3
4
5
6
7
8
9

因为我们不知道存放在栈中的数据的类型，所以将存放数据的类型用typedef重命名为STDataType，以方便随时更改。（这里我们存放数据的类型是int）

Stack就是我们定义并重命名的栈的数据类型
STDataType* a指向栈用数组存放数据的地方起始位置，即栈底
top是栈顶，也是用来访问数组尾部的下标
capacity是栈的容量，指栈所能容纳多少的数据

---

初始化栈

void StackInit(Stack* ps)
{
   
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
1
2
3
4
5
6
7

将栈的地址传过来，对其成员进行初始化

assert(ps)对传过来的地址进行空指针的判断，因为传过来的地址不能为空
ps->a = NULL将指针为空，表明栈的容量为0
ps->top = ps->capacity = 0top记录栈顶位置，capacity记录栈的容量，当容量不足时(也就是ps->top == ps->capacity)进行扩容

---

检测栈的容量是否充足(不充足进行扩容)

void CheckCapacity(Stack* ps)
{
   
	assert(ps);//传过来的指针不能为空
	
	if (ps->top == ps->capacity)//相等表明容量不足
	
1
2
3
4
5
6