队列的定义表示实现.

13.1栈（Stack）3.2队列（Queue)第三章栈和队列1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式23.2队列只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。1.定义一、概念：例如：队列Q=(a1,a2,a3,…，an)在队尾插入元素称为入队；在队首删除元素称为出队。队头元素队尾元素允许插入的一端为队尾，允许删除的一端为队头。3与线性表相同，仍为一对一关系。顺序队或链队，以循环顺序队更常见。只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。3.存储结构：4.运算规则：5.实现方式：2.逻辑结构：队列链队列：队列的链式表示和实现循环队列：队列的顺序表示和实现4（1）初始化队列InitQueue(&Q)（2）入队EnQueue(&Q,e)（3）出队DeQueue(&Q,&e)（4）获取队头元素内容GetHead(Q,&e)（5）判断队列是否为空QueueEmpty(Q)二、基本操作:建队列、判断队列是否为空、入队、出队、读队头元素值，等等。5链队列类型定义：typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;结点类型定义：typedefstructQNode{QElemTypedata;//元素structQNode*next;//指向下一结点的指针}Qnode,*QueuePtr;关于整个链队的总体描述链队中任一结点的结构三、队列的表示和实现1.单链队列//-----队列的链式存储结构-----和单链表唯一的区别是多了一个队尾指针为什么要使用队首指针和队尾？？？如果固定队头，那么每次出队后，后面若干条数据都会往前挪。增加了开销量和浪费。为此，将买票窗口活动起来（即增加一个队首指针），出队后，后面的队列不需要移动。队列可以看成：“很窄的单向胡同”。“多台电脑共用一台打印机设备（优先级相等）”头指针和尾指针避免了删除时的挪动。7a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列为了操作方便，添加一个头结点，令头指针指向头结点。Q.front==Q.rear队空的条件：Q.front=Q.rear;(有头结点）Q.front=NULL;(无头结点)8StatusInitQueue(LinkQueue&Q){//构造一个空队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);//存储分配失败Q.front-next=NULL;//头结点的next域为空returnOK;}//-----基本操作的算法描述-----建队操作——构造空队列Q9Q(队尾)(队首)fronta1a2a3^rearp链队会满吗？一般不会，因为删除时有free动作。除非内存不足！入队（尾部插入）：rear-next=S;rear=S;出队（头部删除）：p=front-next;//P指向第一个元素front-next=p-next;free(p);Se^链队列的入队和出队操作10StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存储分配失败p-data=e;//将值e赋给新节点；p-next=NULL;//新节点的next域为空；Q.rear-next=p;//原队尾节点指针指向新节点；Q.rear=p;//队尾指针指向新节点returnOK;}11StatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK；否则返回ERRORif(Q.front==Q.rear)returnERROR;//判空p=Q.front-next;//p指向队头节点e=p-data;//将队头元素赋给eQ.front-next=p-next;//头结点指向下一个节点if(Q.rear==p)//如果删除的是队尾节点Q.rear=Q.front;//修改队尾指针，让其指向头//结点。一定要考虑free(p);returnOK;}队列的顺序存储结构(循环队列，重点）typedefstruct{QElemType*base;//初始化动态分配空间基址intfront;//头指针，若队列不空，指向队列首元素intrear;//尾指针，若队列不空，//指向队列尾元素的下一个位置。}SqQueue;约定：空队列Q.front=Q.rear;入队列（插入元素）Q.rear++;出队列（删除元素）Q.front++;非空队列，front指针始终指向队头元素，rear指针始终指向队尾元素的下一位置。2.循环队列-队列的顺序表示和实现13队列的顺序存储结构如下图所示：012n-2n-1a1a2a3...an-1anfrontrear附设两个指针front和rear分别指示队列头元素的位置和队列尾元素的下一个位置012...n-2n-1front=0rear=0约定：初始化建空队列时，令front=rear=0；2.循环队列-队列的顺序表示和实现14（2）空队列的特征？约定：front=rear问题：（1）怎样实现入队和出队操作？核心语句如下：入队(尾部插入)：Q[rear]=e;rear++;出队(头部删除)：e=Q[front];front++;（3）队列会满吗？极易装满！因为数组通常有长度限制，而其前端空间无法释放。有假溢出现象。如图：0123456a4a5a6a7frontrearQueue[6]543210rearfront(1)空队列543210rearfrontcbad(2)a、b、c、d依次入队543210rearfrontd(3)a、b、c出队543210rearfrontdef(4)e、f入队“假溢出”16解决假溢出的途径———采用循环队列在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但实际上数组中还有空位置，这就叫“假溢出”。讨论：什么叫“假溢出”？如何解决？将存储队列元素的一维数组首尾相接，形成一个环状。17a3a2a10123N-1rearfront循环队列（臆造）顺序队列a3a2a1frontrear0123..N-1012354rearfront(a)空队列012354e6e7e8e3e4e5012354(b)队列满(b)一般情况frontreare3e4e5frontrear19新问题：在循环队列中，队空时front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有二：①使用一个计数器记录队列中元素个数（即队列长度）；②人为浪费一个单元，约定：队列头指针在队列尾指针的下一位置上作为队列呈“满”状态的标志。则队满特征可改为front=(rear+1)%N（N为最大队列长度）；实际中常选用方案2（人为浪费一个单元）a1a2a3a4a5basefrontrear①尾指针增1:Q.rear=(Q.rear+1)%MAXQSIZE;②头指针增1:Q.front=(Q.front+1)%MAXQSIZE;③队列空：Q.rear=Q.front;④队列满：a)设置一个标志位tag;b)计数器count,初值count=0;c)少占用一个元素空间，(Q.rear+1)%MAXQSIZE=Q.front;21建队核心语句：Q.base=newQElemType[MAXQSIZE];//分配空间关于整个顺序队的总体描述#defineMAXQSIZE100//最大队列长度typedefstruct{QElemType*base;//队列的基址intfront;//队头指针intrear;//队尾指针}SqQueue//-----循环队列——队列的顺序存储结构-----有可能是负数，必须+N22队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=MAXQSIZE)队列长度：L=（N＋rear－front）%NJ2J3J1J4J5frontrear问3：在具有N个单元的循环队列中，队满时共有多少个元素？N-1个6问1：左图中队列MAXQSIZEN=？问2：左图中队列长度L=？5⑤循环队列中元素的个数元素个数=0;若Q.front=Q.rear队列空Q.rear–Q.front;若Q.rearQ.frontQ.rear–Q.front+MAXQSIZE;若Q.rearQ.frontMAXQSIZE-1.若队满元素个数=(Q.rear–Q.front+MAXQSIZE)%MAXQSIZE24例1.一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?J2J3J1J4J5front=1rear=0解：由图可知，队头和队尾指针的初态分别为front=1和rear=0。删除4个元素后front=5；再插入4个元素后，rear=(0+4)%6=4front=5J6J5J7J8J9rear=4rear=0front=525例2.Q[0…10]是一个循环队列，初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队b出队n,o,p入队26讨论：循环队列的基本操作如何实现？以建队、入队和出队三种基本操作为例1）初始化一个空队列算法要求：生成一空队列算法操作：为队列分配基本容量空间设置队列为空队列，其特征即：front=rear=0（也可为任意单元，如1，2，…）27建队的完整算法：StatusInitQueue(SqQueue&Q){//初始化空循环队列QQ.base=newQElemType[MAXQSIZE];//分配空间if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;//置空队列returnOK;}//InitQueue;28算法说明：向循环队列的队尾插入一个元素分析：(1)插入前应当先判断队列是否满？if((Q.rear+1)%MAXQSIZE)==Q.front)returnERROR;(2）插入动作Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;2）入队操作队列尺寸先存放元素，后移动队尾指针29StatusEnQueue(SqQueue&Q,QElemTypee){//向循环队列q的队尾加入一个元素eif((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//队满则上溢Q.base[Q.rear]=e;//新元素e入队Q.rear=(Q.rear+1)%MAXQSIZE;//指针后移returnOK;}//EnQueue;入队操作完整算法303）出队操作算法说明：删除队头元素，返回其值e分析：（1）在删除前应当判断队列是否空？if(Q.front==Q.rear)returnERROR;（2）删除动作分析：前面约定指针front指向队首元素的位置，故：e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;队列尺寸先取出元素，后移动队头指针31StatusDeQueue(SqQueue&Q,QElemType&e){//若队列不空，删除循环队列q的队头元素，//由e返回其值，并返回OKif(Q.front==Q.rear)returnERROR;//队列空e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZ