当前课程知识点：数据结构 > 第3章 栈和队列 > 3.6 队列的顺序实现——循环队列 > 讲解（上）
本节，我们来学习队列的实现
先来看第一种实现：顺序实现
也就是所谓的循环队列
大家看这里的图
图中白色的部分，是我们为队列分配的连续的存储单元
一共SIZE个元素
base
是这一段连续存储单元的首地址
我们用front和rear这两个指针(或者说下标)，来指向队头和队尾元素
那么，介于这两个指针或者下标之间的元素是属于队列的
也就是a1到an
我们来看代码实现
首先，我们定义了一个SIZE
它的容量是100
跟前面一样
我们为队列划分连续存储空间的时候
要一次性分配这么多个元素所占的字节数
紧接着，是队列当中元素的类型
定义ElemType
然后
我们写了一个结构体，结构体的第一个成员是一个指针
它代表着连续的存储空间的首地址
这样的代码
我们在前面，已经遇到很多次了
第二个和第三个成员，分别是整型的front和rear
它们代表着队头和队尾元素，在数组当中的下标
因为，将来我们会把base这个指针，当做一个数组的名字来用
大家注意到，fornt和rear
没有定义成int指针类型
而是定义成了int类型
这是因为，我们将来是直接把front和rear当做下标来用的
有些资料可能把它们定义成指针
这也是可以的
然后
我们用typedef给这样一个结构体，起了一个别名
叫SqQueue
也就是顺序的队列
另外，需要注意的是
我们这门课程做了一个约定
约定什么呢
就是rear
指向的并不是真正的队尾元素
而是队尾元素的下一个位置
比如，看这个图
rear指向的这个字节
它里面的内容并不属于队列
这时候的队尾元素是rear的
前一个位置的元素，也就是an
这只是一种约定
可能有一些资料
不是这样的
它可能约定：rear指向的元素就是队尾元素
这个和我们前面在讲栈的时候，所做的top指针的约定
是类似的
现在，我们来看几个表达式，SqQueue Q
我们声明了一个变量
Q
它是SqQueue类型
就是我们前面定义的结构体类型
它有几个成员
我们看，Q.base[Q.front]
我们把front作为
数组的下标，base作为数组名来用
这是可以的
尽管base是一个指针
front指向的就是队头元素
那么，这个表达式取出来的就是队头元素
那怎么取队尾元素呢
刚才我说了，rear并不是指向队尾
而是队尾的下一个位置，或者说，真正的队尾元素是rear前面的那个位置
也就是，rear-1才是队尾元素所在的下标
Q.rear，实际上是队尾的下一个位置
也就是即将讲到的入队的位置
我们继续来看，刚才这样定义的队列
有一些小问题，什么问题呢
假设经过多次入队、出队操作之后
可能出现rear下标越界的情况
将来，我们会讲到，入队时
rear会往后加1；出队时
front也会往后加1
无论是入队还是出队
front的rear都是加1的，指向下一个位置
假设不断地入队
rear
很有可能被加到SIZE
而我们知道，为队列分配内存的时候
一共分配了SIZE个元素
所占的空间
那么，合法的下标范围应该是0到SIZE-1
当rear
被加到SIZE的时候
rear实际上已经下标越界了，超过了范围
但这时候
可能之前经过了若干次的出队
比如，在图当中
rear虽然超过了数组的下标
但是，前面空出来了两个元素
这两个元素，实际上它里面的内容并不属于队列
也就是说，队列当中还存在未用的存储单元
一方面是rear超过了下标范围
另一方面
队列当中还有未用的单元
那我们到底是追加空间，还是不追加空间呢
现在，我们来解决这个问题
解决的方案很简单
我们把这样一个
线性的空间
把它想象成一个封闭的环
也就是认为，SIZE-1这个下标
它的下一个下标不是SIZE
而是0，就相当于把这一部分空间
左侧的空间，把它们想象成一个封闭的环
这样一来，rear到达SIZE-1的时候
这时候，rear的下一个位置不是SIZE，而是0
这就是循环队列
为此
我们需要做一些约定
我们约定：SIZE-1的下一个位置是0
而不是SIZE
当我们把这一段空间想象成一个环状结构之后
那么，这个环状结构当中，哪些元素才是属于队列的呢
毕竟，在一个环状结构当中
没有严格的先、后的区分
为此，我们也要做一些约定
我们约定：从front出发，沿着下标递增的方向，直至到达rear
这个范围内的元素，是属于队列的
另外
别忘了刚才我们做的一个约定
rear指向的，并不是队尾元素
而是队尾的下一个位置
比如
rear指向下标为0的这个单元
这里面的值并不属于队列
它的前一个位置
SIZE-1才是属于队列的
这才是队尾
按照刚才的约定
从front出发
沿着下标递增的方向，直到到达rear
并且rear指向的不是队尾
那么，图当中
绿色的部分，才是属于队列当中的元素
由于，我们认为rear指向的不是队尾
所以
这一段封闭的空间，长度为SIZE的封闭的空间
最多只能存放SIZE-1元素
这个希望大家注意
另外，还有一个问题
当rear和front这两个下标重合的时候
到底认为队列是空还是满呢
因为，这两个下标重合的时候
实际上，是一种临界的状态
你可以认为它是空的
也可以认为它是满的
比如，按照我们刚才的约定，从front出发，一直到达rear
这时候，队列是满的
SIZE-1个空间里面，所有的元素都是属于队列的
除了front和rear指向的这个空间之外
你也可以认为，从front到rear
因为它们重合
实际上，并没有经历任何的元素
而且，rear指向的并不是队尾元素
这时候，队列的长度为0
这样一种临界状态，到底是空还是满呢
所以，我们也要做一些约定
有两种方案
第一种方案
是专门设一个标志
为队列设一个flag
比如
我们设一个full标志
如果它等于1
我们认为队列是满的
如果它等于0
我们认为队列是空的
或者，设一个empty标志也可以
总之
第一种方案是专门用一个标志的
0和1，来区分队列到底是空还是满
这门课
采用的是第二种方式
我们做一个约定
认为rear和front重合的时候
队列是空
也就是按照这种理解
满的时候，front和rear呈什么相对位置关系呢
我们认为，front在rear的下一个位置，则队列是满的
我们并没有简单地说
front等于rear+1
因为，在环状的空间里面，有可能front小于rear
并且也满足
front在rear的下一个位置
待会我们会讲到
我们统一地称
front在rear的下一个位置，队列是满的
-讲解
-作业
-讨论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 归并排序
--讲解
--作业
-讨论
