目录
一.队列的基本概念及结构
二.队列的实现
1.队列实现的相关函数接口
2.定义结构体
3.初始化队列
4.入队
5.判断队列是否为空
6.出队
7.获取队头元素
8.获取队尾元素
9.获取队列的元素个数
10.销毁队列
三.循环队列的实现
1.循环队列的概念
2.循环队列的实现方式
3.定义一个结构体
4.初始化
5.判断队列是否满了
6.入队
7.判断队列是否为空
8.出队
9.获取队头元素
10.获取队尾元素
11.销毁队列
12.链表实现循环队列代码
一.队列的基本概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列也可以使用数组和链表的结构实现，使用链表的结构实现更优一些
因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低
就像顺序表一样，头删一个数据时需要把后面的数据都往前移，此时的时间复杂度为O（n）
如上图为队列的数组结构，链式结构的示意图
今天主要是要分享链式存储结构的相关操作
用链表实现队列有两种方法，1.头插尾删2.尾插头删
再通过比对以后呢我觉得第二种方法更好一些。原因下文会分析
二.队列的实现
1.队列实现的相关函数接口
2.定义结构体
通过下图可以看到定义了两个结构体，第一个结构就是我们常用的节点，而第二结构体中的成员可以理解为head指针是用来指向队头的，tail指针是用来指向队尾的，size用来反应队列中的元素个数，看到这肯定会有一些疑问，为什么要这样定义呢，这样定义的好处是什么
1.这样定义的好处
上文我们说了实现队列要用尾插头删来实现
当入队的时候尾插需要找到队列的尾，这样就需要把队列遍历一遍，此时入队列的时间复杂度为O（n）
而我们使用tail指针指向尾，在尾插的时候就可以不用再遍历队列了，这时入队列的时间复杂度为O（1）
2.（1.头插尾删2.尾插头删）为什么第二种方法好
第一种方法 当出队列的时候需要尾删，此时还是需要遍历一遍队列找到尾节点前面的一个节点
此方法的时间复杂度为O（n)
第二种方法 因为有tail指针，此时尾插头删时间复杂度都为O（1)
因此尾插头删这种方法更好
3.初始化队列
4.入队
5.判断队列是否为空
6.出队
重要的事说三遍！当删除最后一个数时tail要置空！
当删除最后一个数时tail要置空！
当删除最后一个数时tail要置空！防止野指针！！！
7.获取队头元素
断言一下，如果队列为空就不能访问，防止非法访问
8.获取队尾元素
断言一下，如果队列为空就不能访问，防止非法访问
9.获取队列的元素个数
10.销毁队列
三.循环队列的实现
1.循环队列的概念
循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要将存储空间的第一个位置空闲，便可将元素加入到第一个位置（此时第一个位置为队尾）循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。
循环队列满足了日常中存储空间的重复使用
2.循环队列的实现方式
循环队列的实现方式有两种1.用数组实现2.用链表实现
下面我将阐述数组实现的方法
在实现循环队列时我们需要先定义Front变量表示队头 ，Rear -1变量表示队尾元素下表，
当我们定义k个容量的队列在判断空或满的情况时
队列为空时Front和Rear相等，队列满了的时候Front与Rear又相等，这样是不是就有点自相矛盾了呢，显然这样是不容易判断队列的空或满的
这是我们就需要采取另一种方法了，需要k个容量的队列时，可以申请k+1个容量的空间
这时当队列为空时Front==Rear，当队列满时Rear+1==Front（下文解释原因），这种情况就很容易判断了
下面这种情况也表示队列为空，只要Front等于Rear就表示队列为空，不局限于Front==Rear==0
当向队列插入一个数的时候，Rear就加1一次，删除一个数据的时候Front就加1一次，如下图
入队的时候我们肯定是需要判断队列是否已满，如果已满就不能再插入了，此时肯定想到了Rear+1==Front时就满了（如下图）
，但是有种特殊情况（如下图），又该怎么判断呢
向上图这种情况就需要Rear+1对k+1取模了，就如此时Rear==4，Front==0，
（Rear+1）%（k+1）==0，可以看到此时它们相等，这样就完成了队列的循环（下图示意图），取模可以让Rear重新回到0位置处
同理当只剩最后一个元素的时候，要把它删掉Front就需要加1，当Front加一就非法访问了，所以需要用上文中的方法 取模，（Front+1）%（k+1）这样它就能回到零位置处
示意图：
现在就让我们用代码来实现它吧
3.定义一个结构体
其中的k表示队列的容量，它的用处后面的代码实现就可以知道了
4.初始化
5.判断队列是否满了
6.入队
入队失败就返回false，成功就返回true
7.判断队列是否为空
8.出队
出队失败就返回false，成功就返回true
9.获取队头元素
10.获取队尾元素
11.销毁队列
销毁时它们的顺序不能反！！1
12.链表实现循环队列代码
不过多描述了
