队列是一种可以实现“先进先出”的存储结构。
队列通常可以分为两种类型：
一、顺序队列，采用顺序存储，当长度确定时使用。顺序队列又有两种情况：
①使用数组存储队列的称为静态顺序队列。
②使用动态分配的指针的称为动态顺序队列。
二、链式队列，采用链式存储，长度不确定时使用（由链表实现）。
由于链式队列跟链表差不多，所以在这里只针对循环(环形)队列来说明并实践。循环队列的两个参数：
①front,front指向队列的第一个元素。(front==head)
②rear,rear指向队列的最后一个有效元素的下一元素。(rear==tail)
队列的两个基本操作：出队和入队。
二、队列的结构下面是一个循环队列（基于数组实现）的结构图：
三、队列的操作入队（尾部入队）
①将值存入rear所代表的位置。
②rear=(rear+1)%数组的长度。出队（头部出队）
front=(front+1)%数组的长度。队列是否为空
front和rear的值相等，则该队列就一定为空。队列是否已满
在循环队列中,“队满”和“队空”的条件有可能是相同的，都是front==rear，这种情况下，无法区别是“队满”还是“队空”。
针对这个问题，有3种可能的处理方法：
（1）另设一个标志以区别是“队满”还是“队空”。（即入队/出队前检查是否“队满”/“队空”）
（2）设一个计数器，此时甚至还可以省去一个指针。
（3）少用一个元素空间，即约定队头指针在队尾指针的下一位置时就作为“队满”的标志，即“队满”条件为：(pQueue-rear+1)%MAX_SIZE==pQueue-front。
四、队列的一些问题以及解决办法从上图可以看出，随着入队、出队的进行，会使整个队列整体向后移动，就会出现上图中的现象：队尾指针已经移到了最后，即队尾出现溢出，无法再进行入队操作，然而实际上，此时队列中还有空闲空间，这种现象称为“假溢出”。
解决“假溢出”的三种办法：
方法一：每次删除队头元素后，把整个队列向前移动一个位置，这样可保证队头元素在存储空间的最前面。但每次删除元素时，都要把表中所有元素向前移动，效率太低。
方法二：当队尾指针出现溢出时，判断队头指针位置，如果前部有空闲空间，则把当前队列整体前移到最前方。这种方法移动元素的次数大为减少。
方法三：将队列看成头尾相接的循环结构，当队尾指针到队尾后，再从队头开始向后指，这样就不需要移动队列元素了，显然，第三种方法最经济、应用最多，这种顺序队列被称为“循环队列”或“环形队列”。
采用了这种头尾相接的循环队列后，入队的队尾指针加1操作及出队的队头指针加1操作必须做相应的修改，以确保下标范围为0~Max_Size-1。对指针进行取模运算，就能使指针到达最大下标位置后回到0，符合“循环”队列的特点。
因此入队时队尾指针加1操作改为：pQueue-tail=(pQueue-tail+1)%MAX_SIZE;
入队时队尾指针加1操作改为：pQueue-head=(pQueue-head+1)%MAX_SIZE;
五、数组实现动态顺序队列基于数组的动态顺序循环队列的具体实现：
5.1MyQueue.h#includestdio.h
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineMAXSIZE11//初始容量
typedefintStatus;
typedefintQElemType;//定义数据类型
//循环队列的顺序存储结构
typedefstruct{
QElemTypedata[MAXSIZE];
intfront;//头指针
intrear;//尾指针，队列非空时，指向队尾元素的下一个位置
}SqQueue;
Statusvisit(QElemTypeitem){
printf("%d",item);
returnOK;
}
//初始化空队列
StatusInitQueue(SqQueue*sQ){
sQ-front=0;
sQ-rear=0;
returnOK;
}
//将队列清空
StatusClearQueue(SqQueue*Q){
Q-front=Q-rear=0;
returnOK;
}
//判断队列是否为null
StatusQueueEmpty(SqQueueQ){
if(Q.front==Q.rear)
returnTRUE;
else
returnFALSE;
}
//返回队列中的元素个数
intQueueLength(SqQueueQ){
return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
//返回队头元素
StatusGetHead(SqQueueQ,QElemType*e){
if(Q.front==Q.rear)//是否为空队列
returnERROR;
*e=Q.data[Q.front];
returnOK;
}
//在队尾插入元素
StatusEnQueue(SqQueue*Q,QElemTypee){
if((Q-rear+1)%MAXSIZE==Q-front)//队列已满
returnERROR;
Q-data[Q-rear]=e;//插入队尾
Q-rear=(Q-rear+1)%MAXSIZE;//尾部指针后移，如果到最后则转到头部
returnOK;
}
//元素出队
StatusDeQueue(SqQueue*Q,QElemType*e){
if(Q-front==Q-rear)//队列空
returnERROR;
*e=Q-data[Q-front];//返回队头元素
Q-front=(Q-front+1)%MAXSIZE;//队头指针后移，如到最后转到头部
returnOK;
}
//遍历队列元素
StatusQueueTraverse(SqQueueQ){
inti=Q.front;
while((i+Q.front)!=Q.rear){
visit(Q.data);
i=(i+1)%MAXSIZE;
}
printf("\n");
returnOK;
}
intmain(){
inti=0,l;
QElemTyped;
SqQueueQ;
InitQueue(Q);
//入队１０个元素
for(inti=0;iMAXSIZE-1;i++){
EnQueue(Q,i);
}
QueueTraverse(Q);
printf("依次出队:");
for(l=1;l=MAXSIZE;l++)
{
DeQueue(Q,d);
printf("d=%d,",d);
}
return0;
}
六、链表实现动态顺序队列循环队列要事先申请好空间，整个过程都不能释放，而且要有固定的长度，如果长度事先无法估计，这种方式显然不够灵活；所以就引入了链式存储队列，其实就是线性表的单链表，只是它只能对尾进，队头出。并且规定队头指针指向链队列的头结点，对尾指针指向终端节点，当队列为空时，front和rear都指向头结点。
入队操作，就是在链表尾部插入结点；出队操作就是头结点的后继结点出队，然后将头结点的后继后移。如果最后除了头结点外，只剩一个元素了，就把rear也指向头结点。
#include"stdio.h"
#include"stdlib.h"
#include"io.h"
#include"math.h"
#include"time.h"
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineMAXSIZE20
typedefintStatus;
typedefintQElemType;
//结点结构
typedefstructQNode{
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
//队列的链表结构
typedefstruct{
QueuePtrfront;//队头
QueuePtrrear;//对尾
}LinkQueue;
Statusvisit(QElemTypee)
{
printf("%d",e);
returnOK;
}
//初始化空的队列
StatusInitQueue(LinkQueue*Q){
Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q-front)
exit(OVERFLOW);
Q-front-next=NULL;
returnOK;
}
//销毁队列
StatusDestroyQueue(LinkQueue*Q){
while(Q-front){
Q-rear=Q-front-next;//从队头开始销毁
free(Q-front);
Q-front=Q-rear;
}
returnOK;
}
//清空队列，队头指针还在
StatusClearQueue(LinkQueue*Q){
QueuePtrp,q;
Q-rear=Q-front;//跟初始状态相同，Q-rear指向头结点
p=Q-front-next;//开始销毁队头元素，队头，对尾依然保留
Q-front-next=NULL;
while(p){
q=p;
p=p-next;
free(q);
}
returnOK;
}
//队列是否空
StatusQueueEmpty(LinkQueueQ){
if(Q.front==Q.rear)
returnTRUE;
else
returnFALSE;
}
//取队列长度
intQueueLength(LinkQueueQ){
inti=0;
QueuePtrp=Q.front;
while(Q.rear!=p){
i++;
p=p-next;
}
returni;
}
//获取队头元素
StatusGetHead(LinkQueueQ,QElemType*e){
QueuePtrp;
if(Q.front==Q.rear)//队空
returnERROR;
p=Q.front-next;
*e=p-data;
returnOK;
}
//对尾插入元素
StatusEnQueue(LinkQueue*Q,QElemTypee){
QueuePtrs=(QueuePtr)malloc(sizeof(QNode));
if(!s)
exit(OVERFLOW);
s-data=e;
s-next=NULL;
Q-rear-next=s;//原来对尾的next指向新的元素
Q-rear=s;//将新元素变为对尾
returnOK;
}
//队头元素出队
StatusDeQueue(LinkQueue*Q,QElemType*e){
QueuePtrp;
if(Q-front==Q-rear)
returnERROR;
p=Q-front-next;//ｐ指向队头元素
*e=p-data;
Q-front-next=p-next;//头结点的后继指向队头的下一个元素
if(Q-rear==p){//队头等于对尾了
Q-rear=Q-front;//对尾指向头结点
}
free(p);
returnOK;
}
//遍历元素
StatusQueueTraverse(LinkQueueQ){
QueuePtrp;
p=Q.front-next;
while(p){
visit(p-data);
p=p-next;
}
printf("\n");
returnOK;
}
intmain(){
inti;
QElemTyped;
LinkQueueq;
i=InitQueue(q);
//入队１０个元素
for(intindex=0;indexMAXSIZE;index++){
EnQueue(q,index);
}
QueueTraverse(q);
DestroyQueue(q);
printf("队列已经销毁,q.front=%pq.rear=%p\n",q.front,q.rear);
return0;
}
学到这里，在学习的你理解了吗？有问题欢迎大家一起讨论！
预览时标签不可点收录于话题#个上一篇下一篇