当前课程知识点：数据结构 > 第3章 栈和队列 > 3.6 队列的顺序实现——循环队列 > 讲解（下）
现在，我们来看循环队列的算法实现
第一个算法，初始化
初始化要做的事情，无非是为Q分配内存
并且，为Q的各个成员赋以合适的初值
现在来看算法的实现
首先
我们用malloc函数
为队列分配连续的存储单元，将malloc的返回值赋给Q.base
因为，base这个成员指向是连续存储空间的首地址
空间不够的时候，直接退出
然后，将front的rear都初始化成0
因为我们前面约定了，front和rear重合的时候，队列为空
在初始化的时候
我们将front和rear都置成0
来表示队列为空
下一个算法，得到队列的长度
这里要注意，front和rear的相对位置
比如上面这个图，front小于rear
从front开始，沿着下标递增的方向，一直到rear
也就是绿色的2个格子，是属于队列的
另外一种情况，front大于rear
属于队列的元素
应该是从front出发
沿着下标递增的方向，到rear
除了这2个白色的格子，不属于队列之外
其他的格子，都是属于队列的元素的
下面，我们来看算法的实现
依然是分两种情况
如果front小于等于rear
那么，它的长度
应该是上面这个图的情况
我们直接拿rear减去front，就可以了
注意，不需要加1
因为，这个格子里面的内容不属于队列
这是我们前面做的约定
这种情况下，队列的长度就是rear减去front；另外一种情况
当front大于rear的时候
就是下面这个图的情况
front大于rear
绿色的格子到底有多少呢
应该是总的格子数SIZE减去白色的格子，白色的格子是
front减去rear
也不需要加1
剩下的，就是绿色的格子数
实际上
这个if-else语句
可以统一地写成一个表达式
也就是：SIZE加上rear，减去front
再模除SIZE
这个表达式是怎么得来的呢
我们分析一下
当front小于rear的时候
那么，rear减去front，是一个正数
如果我们把这个正数加上SIZE
最后
再模除SIZE
这个表达式的值
实际上跟它是一样的
因为，它是一个正数
正数
加上SIZE，再模除SIZE
那么，结果依然是这个正数，也就是rear减去front
对于下面这个表达式
我们把这个减号展开
那应该是加上rear减去front
注意
因为，这时候的front是大于rear的
所以，rear减去front是一个负数
那么，SIZE加上一个负数
这个结果，是小于SIZE的
小于SIZE的数
模除SIZE，就相当于没有模除
所以，这两个表达式，也就是
这个if-else，可以合并成这样一个表达式
第三个算法，将e入队
我们需要判断队列是否已经满了
如果满了，我们就什么都不做
因为，对于循环队列来说
我们不考虑当空间不够的时候，追加空间
这样一种情况
也就是说
当队列满了
我们什么都不做
还需要注意，当rear到达边界条件的时候，需要做一些处理
也就是，rear到达了下标最大值
应该让它的下一个值回到0，满足刚才做的环状的约定
现在，我们来看这两种情况
第一种情况，rear是小于
SIZE-1的，没有到达边界条件
这时候，直接将参数e放到rear的位置
因为，我们已经约定了，rear指向的是队尾的下一个位置
也就是入队的位置
然后，将rear加1，就可以了
当rear到达临界条件
也就是SIZE-1的时候，到达下标最大值
这时候，rear不是简单地加1
而是回到0
这个希望大家注意
现在，我们来看算法实现
我们先调用了之前的一个算法，获得队列的长度
以判断队列是否为满
如果长度等于SIZE-1
因为，rear指向的不是属于队列的元素
长度为SIZE的空间，最多
只能存放
SIZE-1个元素
所以，当长度等于SIZE-1
直接return，什么都不做
如果不是满的
我们直接将第二个参数e，赋值给rear指向的位置
下标是rear
刚才我已经说了
rear就是入队位置
入队完了之后
我们只需要将rear加1
如这两个图所示
我们应该区分为两种情况
第一种
rear小于SIZE-1的时候
rear自增就可以了
当rear等于SIZE-1的时候
我们让rear回到0
而不是简单地自增
实际上
这个if-else语句，也可以写成一个表达式
就是rear加1，模除SIZE，它的思想跟我们刚才讲的是一样的
如果rear小于SIZE-1
那么，rear加1
是小于SIZE的，小于SIZE的数模除SIZE，就相当于没有模除
就是简单地加1
如果rear等于SIZE-1，也就是这里else的情况
那么，rear加1
就等于SIZE，SIZE模除SIZE，结果是0，跟这里相对应，rear是0
我们再看下一个算法
出队，将队列Q的队头元素出队
并且，把这个元素放到e里面
我们也要判断队列是否为空
如果队列为空
没有元素可出队
那么就直接返回
同时，也要注意，front到达边界情况的处理
比如，这个图
front原来指向a1
front指向的就是队头
我们只需要将front加1，就可以了
注意，原来这个位置的元素还是a1
我们没有动它
我们也不需要动
因为，我们只需要改变front
就能够改变
哪些元素属于队列
现在，front加1之后，从front出发到rear
很明显
a1不再属于队列了
尽管
这个格子的值没有变
但现在，我们只是通过front加1
就让a1不属于队列了
实际上
这个值并没有真正被删除
这个希望大家注意。另外一种是临界情况
当front等于SIZE减1的时候
如果再将front简单地加1
那么，front会等于SIZE，越界了
我们让front回到0
以对应，这一段空间是一个环状的空间
这个约定
现在，我们来看算法的实现
我们直接给出
如果
front等于rear，代表队列为空
那么，直接return
如果队列不为空
我们直接将front指向的这个下标
它里面的值，赋值给e
因为，我们用第二个参数e，来接收被删除的队头
如果front小于
SIZE-1，front直接自增
这是一般的情况
如果front等于SIZE-1
那么，应该让front回到0
与刚才类似
这个if-else也可以写成一个表达式，front加1
模除SIZE，原因很简单
front小于SIZE-1
那么，加1是小于SIZE的
小于SIZE，再模除SIZE，就相当于没有模除
也就是这种情况
front等于SIZE-1时，front加1就等于SIZE，SIZE模除SIZE
结果是0，对应这种情况
现在，我们再来看看队列的链式存储
链队列。链队列总体上，也是一个单链表
不同的是
有两个指针
一个指针，是指向头结点
另外一个指针，是指向队尾元素
这样，可以很方便地找到一个队列
它的队头和队尾
表当中的结点，跟我们前面的单链表的结点是一致的
包含两个指针
一个是指向头结点的指针
还有一个是指向队尾元素的指针
也就是图当中的front和rear
队头元素
就是这个表达式，Q的front
是指向头结点的
一般，我们都要为单链表加一个头结点，头结点的next指向的，才是真正的队头元素
再取它的data成员
那就是队头；队尾呢
直接是rear的data
因为，rear指针指向的，就是队尾元素
直接取它的data成员，就可以了
队列
这种数据结构，是具有先进先出或者后进后出特性的，新入队的元素
总是先出队
无论是循环队列，还是链队列
前面各种算法，它们的时间复杂度都是O(1)
跟表长
是无关的，原因与栈类似
因为，我们只允许在队列的
两端进行插入、删除，不涉及到中间位置的插入、删除
所以，时间复杂度就是O(1)
队列的应用
也是比较广泛的
比如，在GUI程序的事件处理当中
有队列
还有操作系统的任务调度
磁盘的I/O等等，都涉及到队列
我们就不详细展开了。本章的内容，就到此结束，下一章
我们将进入数组，同学们，加油！
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
