算法与数据结构
今天给各位拓展的是关于算法与数据结构这门课中这周讲授的内容：循环队列的相关知识与拓展，感兴趣的同学可以一起来复习一下，同时也可以扩展一下知识点0.0！
背景
生活中有很多队列的影子，比如打饭排队，买火车票排队问题等，可以说与时间相关的问题，一般都会涉及到队列问题；从生活中，可以抽象出队列的概念，队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和静态队列；静态队列一般用数组来实现；链式队列是用链表来实现队列的。这里讲的是循环队列。
01
循环队列
循环队列的提出：为充分利用向量空间，克服"假溢出"现象
方法：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列。
实现方式：这种循环队列可以以单链表的方式来在实际编程应用中来实现，也可以使用数组实现。
特点：队列的操作特点是“先进先出”。前者主要是头指针、尾指针的使用，后者主要是理解循环队列提出的原因及其特点。两者都要掌握队列空与满的判定条件以及出队列、入队列操作的实现。
02
实现循环队列的注意事项
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有两种：
01
另设一变量，用来记录数组中当前元素的个数，以区别队列的空和满；
02
另一种方式就是数据结构常用的：
队满时：(rear+1)%n==front，n为队列长度（所用数组大小），由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。如图a情况，队已满，但是rear（5）+1=6！=front（0），对空间长度求余，作用就在此6%6=0=front（0）。（其二是少用一个元素空间，也就是最后一个存储空间不用，如图1，约定以“队列头指针在队列尾指针的下一位置（指环状的下一位置）上”作为队列呈“满”状态的标志。当（rear+1）%maxsiz=front时，队列满。）
图a
图1
图2
下面是一种实现方法：
参考资料：