一、队列与循环队列1.队列(1)队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表，
09.循环队列与链队列
。队列是一种先进先出(Fiirst In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。 从队列的定义可知，队列的入队操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)。队列的删除操作，与栈不同的是，队列元素的出列是在队头，即小标为0的位置，若要删除一个元素的话，需要移动队列的所有元素，因此事件复杂度为O(n)。(2)front/rear指针：为了避免当只有一个元素时，队尾和队头重合使处理变得麻烦，所有引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，队列为空(空队列)而不是队列还剩下一个元素。2.队列的抽象数据类型ADT 队列Data 同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。Operation InitQueue(*Q): 初始化操作，建立一个空队列Q. DestoryQueue(*Q):若队列Q存在，则销毁它。 ClearQueue(*Q):将队列Q清空 GetHead(Q,*e):若队列Q存在且非空，用e返回队列Q的队头元素。 EnQueue(*Q,e):若队列Q存在且非空，插入新元素e到队列Q中并称为队尾元素。 DeQueue(*Q,*e):删除队列Q中队头元素，并用e返回其值 QueueLength(Q)：返回队列Q的元素个数endADT3.循环队列<喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPgo8c3Ryb25nPigxKbao0uU8L3N0cm9uZz6jurbTwdDW0M23zrLP4L3TtcTLs9DytOa0or3hubmzxs6q0a27t7bTwdCjrNPD09q94r72JnF1b3Q7vNnS57P2JnF1b3Q7zsrM4qGjCjxzdHJvbmc+KDIpttPC+sz1vP48L3N0cm9uZz6jugogICAg0ruw48fpv/ajrLWxZnJvbnQ9cmVhcsqxo6y208HQv8nE3M6qv9W208HQ0rK/ydLUzqrC+rbTwdCho8v50tTO0sPHvNnJ6KOstbFmcm9udD09cmVhcsqxttPB0M6qv9Wju7WxttPB0ML6yrGjrMr91+m7udPQ0ru49r/Vz9C/1bzkoaPTydPacmVhcr/JxNyxyGZyb250tPOjrNKyv8nS1LHIZnJvbnTQoaGjztLDx9Xi0fm2qNLlo6y1sbbTwdDC+tfjzPW8/iZxdW90OyhyZWFyJiM0MzsxKSVRdWV1ZVNpemU9PWZyb250JnF1b3Q7yrGjrM7Sw8e+zcjPzqq208HQ0tHC+ihRdWV1ZVNpemXOqrbTwdDX7rTztOa0osjdwb8poaMKPHN0cm9uZz4oMym208HQs6S2yLmryr08L3N0cm9uZz4KICAgILWxcmVhciZndDtmcm9udMqxo6y208HQtcSzpLbIzqpyZWFyLWZyb250O7WxcmVhciZsdDtmcm9udMqxo6y208HQtcSzpLbIzqooUXVldWVTaXplLWZyb250KSYjNDM7KDAmIzQzO3JlYXIpo6zG5NbQZm9udKGicmVhcqGiUXVldWVTaXplvvnOqsr91+nPwrHqoaO+rbn9zca1vLXEvMbL47bTwdC5q8q9o7oKICAgIChyZWFyLWZyb250JiM0MztRdWV1ZVNpemUpJVF1ZXVlU2l6ZQo8c3Ryb25nPig0KdGtu7e208HQtcTLs9DytOa0or3hubk8L3N0cm9uZz4KdHlwZWRlZiBpbnQgUUVsZW1UeXBlCnR5cGVkZWYgc3RydWN0CnsKICAgIFFFbGVtVHlwZSBkYXRhW01BWFNJWkVdOwogICAgaW50IGZyb250OyAgICAvL7bTzbfWuNXrCiAgICBpbnQgcmVhcjsgICAgLy+2086y1rjV66OsyPS208HQsru/1aOs1rjP8rbTzrLUqsvYtcTPwtK7uPbOu9bDCn1TcVF1ZXVlOwooNSnRrbu3ttPB0LXEz+C52LLZ1/cKQS6z9cq8u6/Su7j20a27t7bTwdBRClN0YXR1cyBJbml0UXVldWUoU3FRdWV1ZSAqUSkKewogICAgUS0mZ3Q7ZnJvbnQ9MDsKICAgIFEtJmd0O3JlYXI9MDsKICAgIHJldHVybiBPSzsKfQpCLrzGy+PRrbu3ttPB0LXEs6S2yAovKre1u9hRtcTUqsvYuPbK/aOsvLS208HQtcS1scews6S2yCovCmludCBRdWV1ZUxlbmd0aChTcVF1ZXVlIFEpCnsKICAgIHJldHVybiAoUS5yZWFyLVEuZnJvbnQmIzQzO01BWFNJWkUpJU1BWFNJWkU7Cn0KQy7Rrbu3ttPB0LLlyOuy2df3Csq1z9ajusj0ttPB0M60wvqjrNTysuXI69Sqy9hlzqrQwrXEttPOstSqy9gKU3RhdHVzIEVuUXVldWUoU3FRdWV1ZSAqUSxRRWxlbVR5cGUgZSkKewogICAgaWYoKFEtJmd0O3JlYXImIzQzOzEpJU1BWFNJWkUgPT0gUS0mZ3Q7ZnJvbnQpICAgIC8vxdC2z9W7wvooKHJlYXImIzQzOzEpJVF1ZXVlU2l6ZT09ZnJvbnQpCiAgICAgICAgICAgIHJldHVybiBFUlJPUjsKICAgIFEtJmd0O2RhdGFbUS0mZ3Q7cmVhcl09ZTsKICAgIFEtJmd0O3JlYXI9KFEtJmd0O3JlYXImIzQzOzEpJU1BWFNJWkU7ICAgIC8vcmVhcta41evP8rrz0sbSu867o6zI9LW91+6689Ty16q1vcr91+nNt7K/CiAgICByZXR1cm4gT0s7Cn0KRC7Rrbu3ttPB0Mm+s/2y2df3Csq1z9ajusj0ttPB0LK7v9WjrNTyyb6z/VHW0LbTzbfUqsvYoaPTw2W3tbvYxuQmIzIwNTQwOwoKU3RhdHVzIEVuUXVldWUoU3FRdWV1ZSAqUSxRRWxlbVR5cGUgKmUpCnsKCiAgICBpZihRLSZndDtyZWFyPT1RLSZndDtmcm9udCkKICAgICAgICAgICAgcmV0dXJuIEVSUk9SOyAgICAgICAgLy+208HQzqq/1cz1vP6junJlYXI9ZnJvbnQKICAgICplPVEtJmd0O2RhdGFbUS0mZ3Q7ZnJvbnRdOyAgICAvL72rttPNt9Sqy9i4syYjMjA1NDA7uPhlCiAgICBRLSZndDtmcm9udD0oUS0mZ3Q7ZnJvbnQmIzQzOzEpJU1BWFNJWkU7ICAgIC8vZnJvbnTWuNXrz/K689LG0rvOu9bDo6zI9LW91+6689Ty16q1vcr91+nNt7K/CiAgICByZXR1cm4gT0s7CqP9CtfcveGjurWlysfLs9DytOa0oqOsyPSyu8rH0a27t7bTwdCjrMvjt6i1xMqxvOTQ1MTcyseyu7jftcSjrLWr0a27t7bTwdDT1sPmwdnXxcr91+m/ycTcu+HS57P2tcTOyszio6zL+dLUztLDx8/CvdrS/bP2ttPB0LXEwbTKvbTmtKK94bm5oaMKPHN0cm9uZz62/qGittPB0LXEwbTKvbTmtKK94bm5PC9zdHJvbmc+CjxzdHJvbmc+MS7BtLbTwdA8L3N0cm9uZz6jurbTwdC1xMG0yr205rSiveG5uaOsxuTKtb7NysfP39DUse21xLWlwbSx7aOs1ruyu7n9y/zWu8TczrK9+M23s/ajrNKys8bBtLbTwdCho86qwcu3vbHjstnX96OsttPNt9a41evWuM/ywbS208HQtcTNt73hteOjrLbTzrLWuNXr1rjP8tbVtsu94bXjoaO1sbbTzbfWuNXrZnJvbnS6zbbTzrLWuNXrcmVhcra81rjP8s23veG148qxo6y208HQzqq/1aGjCjxpbWcgc3JjPQ=="http://www.2cto.com/uploadfile/Collfiles/20150110/20150110092126102.png" alt="\">
2.链队列结构typedef int QElemType/*结点结构*/typedef struct QNode{ QElemType data; //数据域 struct QNode *next; //指针域}QNode,*Queueptr;/*队列的链表结构*/typedef struct{ Queueptr front,rear; //队头、队尾指针}LinkQueue;3.链队列的入队操作算法：实质为链表尾插入结点，尾指针指向新结点a.为新结点s开辟一段空间，并判断是否存储分配成功;b.将插入元素存到新结点s的数据域，并初始化s的指针域;c.把拥有元素e新结点s赋值给原队列结点的后继；d.把当前的s设置为队尾结点，rear指向s
实现：插入元素e为Q的新队尾元素
Status EnQueue(LinkQueue *Q,QElemType e){ QueuePtr s=(QueuePtr)malloc(sizeof(QNode)); //为新结点s开辟一段空间 if(!s) //存储分配失败 exit(OVERFLOW); s->data=e; //将元素e存储到新结点s的数据域 s->next=NULL;//初始化新结点的指针域 Q->rear->next=s; //把拥有元素e新结点s赋值给原队列结点的后继 Q->rear=s; //把当前的s设置为队尾结点，rear指向s}4.链队列的删除操作算法：实质是头结点的后继结点出队，将头结点的后继改为他后面的结点，电脑资料
《09.循环队列与链队列》(https://www.unjs.com)。若链表除头结点外，只剩下一个元素时，则需将rear指向头结点。a.定义一个QueuePtr结点p，用于暂存欲删除的结点Q->front-next;b.将欲删除结点数据域数据赋值给e;c.将欲删除结点的后继结点(p->next)赋值给头队头结点的后继(Q->front->next)d.判定若队头是队尾，则删除后将rear指向头结点，最后再释放欲删除结点p.实现：若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
Status EnQueue(LinkQueue *Q,QElemType e){ QueuePtr p; if(Q->front==Q->rear) return ERROR; //队列为空 p=Q->front->next; //将队头指针指向的头结点的后继结点(欲删除的结点)暂存给p *e=p->data; //将欲删除结点的数据域数据赋值给e Q->front->next=p->next; //将元队头结点后继p->next赋值给队头结点的后继 if(Q->rear==p) //若队头是队尾，则删除后将rear指向头结点 Q-rear=Q->front; free(p); return OK;}三、循环队列与链队列性能分析1.循环队列与链队列基本操作时间复杂度均为O(1);2.循环队列事先申请好空间，使用期间不释放;链队列，无需事先申请空间但是每次申请和释放结点会存在一些事件开销;3.循环队列必须有一个固定的长度，可能存在空间浪费；链队列需要一个指针域，会产生一些空间上的开销，所以在可以确定队列长度最大值的情况下建议用循环队列。