实用数据结构基础（第五版） 课件 第03章 队列.pptx

第3章队列

第3章队列3.1队列的定义和操作队列的定义和特性队列的基本操作3.2队列的存储和实现顺序队列链式队列3.3队列的应用举例2

重难点队列和线性表的关系——操作受限的含义循环顺序队列的相关操作链式队列利用队列的特点解决应用问题（后续章节中树和图的遍历等）3

3.1队列的定义和操作?4?进队出队

3.1.1队列的定义和特性队列的特性队列中的元素须按进队的次序出队，也就是说队列的操作遵循“先进先出”(FirstInFirstOut,FIFO)的操作原则。应用实例计算机处理文件打印食堂排队打饭车站排队买票5

3.1.2队列的基本操作进队操作：inQueue(q,x)初始条件：队列q存在，且未满。操作结果：插入一个元素x到队尾，队列长度加1出队操作：outQueue(q,x）初始条件：队列q存在，且非空。操作结果：将队首元素赋值给x带回给主调函数，然后将队首元素从队列中删除，队列长度减1。6

3.1.2队列的基本操作判队空操作：isQEmpty(q)初始条件：队列q存在操作结果：队列空则返回1，否则返回0判队满操作：isQFull(q)初始条件：队列q存在操作结果：队列满则返回1，否则返回0读取队头和队尾元素：readFrontRear(q,x,y）初始条件：队列q存在，且非空。操作结果：将队头元素赋值给x带回给主调函数，将队尾元素赋值给y带回给主调函数，队列内容不变。7

3.1.2队列的基本操作显示队列中元素showQueue(q)初始条件：队列q存在，且非空。操作结果：显示队列中的所有元素。求队列长度：getQLength(q)初始条件：队列q存在操作结果：返回队列中当前元素的个数。8

#defineN8typedefstruct{??ElemTypedata[N];??intfront;//front指示队头元素的位置??intrear;?//rear指示队尾元素的位置}SeqQueue;??//定义顺序队列的类型SeqQueue3.2队列的存储和实现3.2.1顺序队列用一组地址连续的存储单元(即数组)存储队中元素901234567????rear=4front=-1N?正好指在队尾元素指在队头元素的前一个位置data

3.2.1顺序队列顺序队列的初始化若SeqQueueq;一般设置队头和队尾q.front=q.rear=-1;进队时：先执行q.rear++;然后将元素进队到q.rear所指单元出队时：先执行q.front++;然后将q.front所指的元素出队若将q.front和q.rear的初值设为0，进队和出队的细节可能会不同1001234567rear=-1front=-1N正好指在队尾元素指在队头元素的前一个位置

3.2.1顺序队列顺序队列的初始化如果将q.front和q.rear的初始值设为0一般先存取元素，再移动队头或队尾指针进队时，先按q.rear指示的位置存入元素，再执行q.rear++，q.rear指示队尾元素的后一位置。出队时，先将下标为q.front的元素取出，再执行q.front++，q.front指示队头元素的位置。1101234567rear=2front=0指在队尾的后一个位置指在队头的位置

3.2.1顺序队列进队前提：队列未满；q.rear++; //先将队尾指针加1q.data[q.rear]=x; //元素x进队1201234567frontN=8指在队头元素的前一个位置?????rear指在队尾元素的位置

N=8rear正好指在队尾元素的位置3.2.1顺序队列出队前提：队列非空；q.front++; //先将队头指针加1x=q.data[q.front];//队头元素赋值给x1301234567???front指在队头元素的前一个位置??

3.2.1顺序队列判队空开始队列为空，队头指针q.front和队尾指针q.rear的初值一样(同时为-1或0)；进队一个元素时q.rear++，而出队一个元素时q.front++；若进队了m个元素，又出队了m个元素，则一定有q.front==q.rear因此当q.front==q.rear时(即，队头和队尾指针再次指向同一个单元时)，队列肯定为空。14rear=-1front=-1rear=4front=4datadata进队了5个元素同时又出队了5个元素

3.2.1顺序队列判队满显然，队列中的元素个数m=q.rear—q.front应该是当队列中的元素个数m==N时，队列数组data中没有空单元