栈和队列（数据结构初阶）

欢迎大家来到我的博客，给生活加点impetus！！！

今天我们学习栈和队列！

栈和队列

一：栈

1.1概念与结构

栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

理解后进先出法则。

1要出来的话必须先让2和3出来，2要出来的话必须先让3出来。

先进后出或者后进先出。

1.2底层逻辑

在前面我们已经介绍了线性表。
栈在逻辑结构上一定是连续的，那物理结构上呢？
这取决于栈的物理结构。

再来看链表实现。

**数组和链表的更优的方法时间复杂度都为O（1），到底是使用哪一个呢？
我们再来看所占字节大小。

栈的底层结构是数组，物理上是连续的。

注意：不是说栈只能用数组来实现，也能够使用链表来实现。

1.3栈的实现

结构定义

typedef int STDataType;
typedef struct Stack {
	STDataType* arr;
	int capacity;//容量
	int top;//指向栈顶的位置
}ST;

与单链表类似。

判空

分清栈为空，栈中的存储元素的地址为空，此处是判定后者的。
栈为空，比如ps=NULL，后者是ps结构体中的成员为空。

入栈

细节
1：存储空间不够，是对应存储数据的空间不够，realloc返回类型不要写成ST，不是开辟一个新的栈。
2:注意传过来的参数是不是NULL。

出栈

断言也可以写为assert(ps&&!STEmpty(ps)）;

取栈顶元素

获取栈中有效数据个数

弄清楚top与存储数据个数的关系。

二：队列

2.1概念与结构

概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。
⼊队列：进⾏插⼊操作的⼀端称为队尾。
出队列：进⾏删除操作的⼀端称为队头。

2.2底层逻辑

队列是线性表，在逻辑上是线性的，那物理结构上呢？他的底层逻辑是什么呢？我们来讨论一下。

两种思路时间复杂度都为O（n），且无法有较好的方法解决

接下来我们来看链表实现。

链表实现时时间复杂度也是O（n），那又该选谁呢？
时间复杂度为O（n）的原因是尾结点的位置遍历寻找，那我们就存储尾结点的位置即可，时间复杂度就会变为O（n）。

队列在物理结构上是不一定连续的。

不是说队列只能用链表实现，数组实现也可以。

2.3 队列的实现

结构定义

初始化

接下来都是传址，需要形参改变实参。

入队

细节
1：开辟空间时开辟的是结点，而非队列，注意看数据类型，分清与栈开辟的区别
2：注意开辟是否成功。
3：大多数要注意空链表与非空链表的处理。

判空

细节：传过来的pq队列可能为空，队列结点中可能为空，这里是在判断后者。

出队

空链表和非空链表的处理。

取数据

有效数据个数

三：结语

欢迎大家阅读我的博客，感谢大家支持！！出错之处欢迎大家指出。

千磨万击还坚韧，任尔东西南北风，加油！！陌生人！！