3.3 队列的主要运算

队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；3.2队列3.2.1队列的定义与运算定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。a1,a2,a3,a4,…………an-1,an队列示意图队头队尾2.队列的存储结构（1）顺序存储结构(a)线性队列(b)循环队列队列的入队和出队操作示意图3.2.2队列的顺序存储结构及其基本运算的实现假设队列的元素个数最大不超过整数MaxSize,所有的元素都具有同一数据类型ElemType,则顺序队列类型SqQueue定义如下:typedefstruct{ElemTypedata[MaxSize]；intfront,rear；/*队首和队尾指针*/}SqQueue(a)线性队列3210(a)rear=front=-1(队空）e3e4(c)(c)e1,e2出队，e4入队队满rear=4fronte1e2e3(b)rearfront(b)e1,e2,e3入队队空时，令rear=front=-1，当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置从前图中看到,图(a)为队列的初始状态,有front==rear成立,该条件可以作为队列空的条件。那么能不能用rear==MaxSize-1作为队满的条件呢？显然不能,在图(d)中,队列为空,但仍满足该条件。这时入队时出现“上溢出”,这种溢出并不是真正的溢出,在elem数组中存在可以存放元素的空位置,所以这是一种假溢出。为了能够充分地使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为循环队列。(b)循环队列rearfront0123(3)队空队满条件：(Q.rear+1)%MAX=Q.front注：实际上为了避免与队空标志冲突，还留有一个空间。将头尾连接成一个环，形成循环队列。e4e3(2)队满fronte3e40123reare5rearrear01234front(a)空队(b)a,b,c入队rear01234frontabc01234abcdfront(c)d入队,队满rear01234cdfront(d)出队2次rear01234front(e)出队2次,队空循环队的入队和出队操作示意图在循环队列中,实现队列的基本运算算法如下:(1)初始化队列InitQueue(&q)构造一个空队列q。将front和rear指针均设置成初始状态即0值。对应算法如下:voidInitQueue(SqQueue*&q){q=(SqQueue*)malloc(sizeof(SqQueue));q-front=q-rear=0;}(2)销毁队列ClearQueue(&q)释放队列q占用的存储空间。对应算法如下:voidClearQueue(SqQueue*&q){free(q);}(3)判断队列是否为空QueueEmpty(q)若队列q满足q-front==q-rear条件,则返回1；否则返回0。对应算法如下:intQueueEmpty(SqQueue*q){return(q-front==q-rear);}(4)入队列enQueue(q,e)在队列不满的条件下,先将队尾指针rear循环增1,然后将元素添加到该位置。对应算法如下:intenQueue(SqQueue*&q,ElemTypee){if((q-rear+1)%MaxSize==q-front)/*队满*/return0;q-rear=(q-rear+1)%MaxSize;q-data[q-rear]=e;return1;}循环队列中加入一个元素的算法：intEnQueue(intQ[],intx,int*pf,int*pr)Q[max]已有的循环队列将插入的值已有队列的头指针已有队列的尾指针循环队列中加入一个元素的算法：intEnQueue(intQ[],intx,int*pf,int*pr){intfront,rear;front=*pf;rear=*pr;if((rear+1)%MAX==front)return(0);else{rear=(rear+1)%MAX;Q[rear]=x;*pr=rear;return(1);}}e4e3e4e3reare4e3x循环队列中删除一个元素的算法：intDeQueue(intQ[]，int*py，int*pf，int*pr)已有的循环队列返回删除的值的地址已有队列的头指针已有队列的尾指针循环队列中删除一个元素的算法：intDeQueue(intQ[]，int*py，int*pf，int*pr){intfront,rear;front=*pf;rear=*pr;if(rear==front)return(0);else{front=(front+1)%MAX;*py=Q[front];*pf=front;return(1);}}ana2a1ana3a2Q.frontQ.rear删除一个元素添加一个元素e^a1a2anQ.frontQ.rear（2）链式存储结构Q.frontQ.rear队头队尾Q.rearQ.front例3.7对于顺序队列来说,如果知道队首元素的位置和队列中元素个数,则队尾元素所在位置显然是可以计算的。也就是说,可以用队列中元素个数代替队尾指针。编写出这种循环顺序队列的初始化、入队、出队和判空算法。解:当已知队首元素的位置front和队列中元素个数count后:队空的条件为:count==0队满的条件为:count==MaxSize计算队尾位置rear:rear=(front+count)%MaxSize对应的算法如下:typedefstruct{ElemTypedata[MaxSize];intfront;/*队首指针*/intcount;/*队列中元素个数*/}QuType;/*队列类型*/voidInitQu(QuType*&q)/*队列q初始化*/{q=(QuType*)malloc(sizeof(QuType));q-front=0;q-count=0;}intEnQu(QuType*&q,ElemTypex)/*进队*/{intrear;if(q-count==MaxSize)return0;/*队满上溢出*/else{rear=(q-front+q-count+MaxSize)%MaxSize;/*求队尾位置*/rear=(rear+1)%MaxSize;/*队尾位置进1*/q-data[rear]=x;q-count++;return1;}}intDeQu(QuType*&q,ElemType&x)/*出队*/{if(q-count==0)/*队空下溢出*/return0;else{q-front=(q-front+1)%MaxSize;x=q-data[q-front];q-count--;return1;}}intQuEmpty(QuType*q)/*判空*/{return(q-count==0);}链队组成:(1)存储队列元素的单链表(2)指向队头和队尾指针的链队头结点3.2.3队列的链式存储结构及其基本运算的实现∧∧frontrearq(a)链队初态frontrearq(b)入队3个元素ab∧cfrontrearq(c)出队1个元素b∧c链列的入队和出队操作示意图单链表中数据结点类型QNode定义如下:typedefstructqnode{ElemTypedata;/*数据元素*/structqnode*next;}QNode;链队中头结点类型LiQueue定义如下:typedefstruct{QNode*front;/*指向单链表队头结点*/QNode*rear;/*指向单链表队尾结点*/}LiQueue;在链队存储中,队列的基本运算算法如下:(1)初始化队列InitQueue(q)构造一个空队列,即只创建一个链队头结点,其front和rear域均置为NULL,不创建数据元素结点。对应算法如下:voidInitQueue(LiQueue*&q){q=(LiQueue*)malloc(sizeof(LiQueue));q-front=q-rear=NULL;}(2)销毁队列ClearQueue(q)释放队列占用的存储空间,包括链队头结点和所有数据结点的存储空间。对应算法如下:voidClearQueue(LiQueue*&q){QNode*p=q-front,*r;if(p!=NULL)/*释放数据结点占用空间*/{r=p-next;while(r!=NULL){free(p);p=r;r=p-next;/*p和r指针同步后移*/}}free(q);/*释放链队结点占用空间*/}(3)判断队列是否为空QueueEmpty(q)若链队结点的rear域值为NULL,表示队列为空,返回1；否则返回0。对应算法如下:intQueueEmpty(LiQueue*q){if(q-rear==NULL)return1;elsereturn0;}(4)入队列enQueue(q,e)创建data域为e的数据结点*s。若原队列为空,则将链队结点的两个域均指向*s结点,否则,将*s链到单链表的末尾,并让链队结点的rear域指向它。对应算法如下:voidenQueue(LiQueue*&q,ElemTypee){QNode*s;s=(QNode*)malloc(sizeof(QNode));s-data=e;s-next=NULL;if(q-rear==NULL)/*若原链队为空,新结点是队首结点又是队尾结点*/q-front=q-rear=s;else{q-rear-next=s;/*将*s结点链到队尾,rear指向它*/q-rear=s;}}(5)出队列deQueue(q,e)若原队列不为空,则将第一个数据结点的data域值赋给e,并删除之。若出队之前队列中只有一个结点,则需将链队结点的两个域均置为NULL,表示队列已为空。对应的算法如下:intdeQueue(LiQueue*&q,ElemType&e){QNode*t;if(q-rear==NULL)return0;/*队列为空*/t=q-front;/*t指向第一个数据结点*/if(q-front==q-rear)/*原链队中只有一个结点时*/q-front=q-rear=NULL;else/*原链队中有多个结点时*/q-front=q-front-next;e=t-data;free(t);return1;}3.2.4队列的应用例子采用队列求解迷宫问题使用一个队列Qu记录走过的方块,该队列的结构如下:struct{inti,j;/*方块的位置*/intpre;/*本路径中上一方块在Qu中的下标*/}Qu[MaxSize];intfront=-1,rear=-1;/*队首指针和队尾指针*/这里使用的队列Qu不是循环队列(因为要利用出队的元素找路径),因此在出队时,不会将出队元素真正从队列中删除,因为要利用它输出路径。(1)首先将(1,1)入队;(2)在队列Qu不为空时循环:出队一次(由于不是循环队列,该出队元素仍在队列中),称该出队的方块为当前方块,front为该方块在Qu中的下标。①如果当前方块是出口,则输出路径并结束。②否则,按顺时针方向找出当前方块的四个方位中可走的相邻方块(对应的mg数组值为0),将这些可走的相邻方块均插入到队列Qu中,其pre设置为本搜索路径中上一方块在Qu中的下标值,也就是当前方块的front值,并将相邻方块对应的mg数组值置为-1,以避免回过来重复搜索。(3)若队列为空仍未找到出口,即不存在路径。搜索从(1,1)到(M-2,N-2)路径实际上,本算法的思