数据结构与算法 (11).pdf
14.1 队列的基本概念4.2 队列的顺序表示与实现4.3 队列的链式表示与实现4.4 队列的应用第4章 队列及其应用2 24.1.1 队列的定义4.1.2 队列的抽象数据类型4.1 队列的基本概念3 队列的定义队列的定义4.1.1 队列的定义队列队列(Queue)是一种运算受限的特殊的线性是一种运算受限的特殊的线性表，它只允许在表的一端进行插入，而在表的另一表，它只允许在表的一端进行插入，而在表的另一端进行删除。端进行删除。队尾队尾(rear)：是队列中允许插入的一端。是队列中允许插入的一端。队头队头(front)：是队列中允许删除的一端。是队列中允许删除的一端。队列的术语队列的术语4队列的特点队列示意图4.1.1 队列的定义队列的定义a1a2a3 an队头队尾出队入队先进先出(First In First Out，简称FIFO)。又称队列为先进先出表。5 54.1.1 队列的定义4.1.2 队列的抽象数据类型4.1 队列的基本概念6ADT Queue 数据对象：数据关系：基本操作：ADT Queue见下页Dai|aiElemSet,i=1,2,.,n,n0R1|ai-1,ai D,i=2,.,n约定其中a1端为队列头，an端为队列尾4.1.2 队列的抽象数据类型7 7InitQueue(&Q)/初始化队列DestroyQueue(&Q)/销毁队列QueueEmpty(Q)/判队列是否空QueueLength(Q)/求队列长度GetHead(Q,&e)/取队头元素ClearQueue(&Q)/清空队列EnQueue(&Q,e)/入队列DeQueue(&Q,&e)/出队列QueueTravers(Q,visit()/遍历队列队列的基本操作8 84.1 队列的基本概念4.2 队列的顺序表示与实现4.3 队列的链式表示与实现4.4 队列的应用举例第4章 队列及其应用9 9 4.2.1 顺序队列4.2.2 循环队列4.2.3 循环队列的实现4.2 4.2 队列的顺序表示与实现10 采用顺序存储结构的队列称为顺序队列。它是利用一组地址连续的存储单元依次存放自队头到队尾的数据元素。顺序队列通常由一个一维数组和记录队列头元素位置的分量front以及记录队尾元素位置的分量rear组成。4.2.1 顺序队列1111typedef struct ElemType dataMaxSize;int front,rear;QNode，*SqQueue;SqQueue Q;01 2 3maxlen-1nfrontrear dataQ顺序队列的C语言描述：121201 2 3maxlen-1nfrontrear dataQ front front 和和rear rear 的初始值在队列初始化时均置的初始值在队列初始化时均置为。为。入队时尾指针加，并将新元素插入所指的位置。出队时头指针加，然后删去所指的元素，并返回被删元素。约定：在非空队列里，头指针始终指向队头元素前的空位，而尾指针始终指向队尾元素。1313(a)队列初始为空（c)a出队出队frontrearfront （b）a,b,c入队入队abcfront abcfront bc(d)b出队出队front rearrearrearrearrearfront 0 1 2 31414 队空：Q-front=Q-rear 队满：队满：QQ-rear=Maxsizerear=Maxsize-1 1 队长：队长：Q Q-rear rear-QQ-frontfront 入队：将队尾指针加一入队：将队尾指针加一，即，即QQ-rearrear=QQ-rear rear+1+1，再将新元素按，再将新元素按rearrear指示位置加入指示位置加入 出队：将队头指针加一，即Q-front=Q-front+1，再将front指示的元素取出。此时：1515可以看出：可以看出：尾指针 rear 已指到数组的最后一个元素，即rear=MaxSize-1,若这时入队，则产生“溢出”同时经过一定数量的出队后，头指针 front 可指向队列的中间，即：数组的前面部分有闲置的空间 这种有可用空间存在的溢出，称“假溢出”问题：如何利用数组前面的可用空间？16164.2.1 顺序队列 4.2.2 循环队列4.2.3 循环队列的实现4.2 4.2 队列的顺序表示与实现174.2.2 循环队列循环队列循环队列：将数组空间看成是一个首尾相接的圆环，即:将data0 看作是dataMaxSize-1 后的下一个存储位置，存储在其中的队列称为循环队列循环队列（CircularCircular Queue)Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1。只不过当头尾指针指向数组的上界（MaxSize-1）时，其加1操作的结果是指向数组的下界0。即：指针运算是+1后对数组长度取模显然，因为循环队列元素的存储空间可以被利用，除非数组真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。0123456frontghkefrontabfrontfrontreardrearrearrearrearfrontrear例：循环队列的操作例：循环队列的操作1919讨论讨论：在循环队列中执行入队和出队操作在循环队列中执行入队和出队操作入队：入队：if(Q-rear=MaxSize 1)Q-rear=0;else Q-rear=Q-rear+1;Q-dataQ-rear=x；0123456ghkefrontdrearrearrearrear或 采用模运算：Q-rear=(1+Q-rear)%MaxSizeQ-dataQ-rear=x；2020或：或：Q-front=(1+Q-front)%MaxSizeeabdrear0123456frontfrontfrontkfront出队：出队：if(Q-front=MaxSize 1)Q-front=0;else Q-front=Q-front+1;2121frontghkeabdrear0123456frontghkeabdrear0123456rearrearrearrearfrontfrontfrontfrontfrontfront入队入队出队出队队满队满队空队空讨论：循环队列队空与队满的描述讨论：循环队列队空与队满的描述2222队空：队空：Q-rear=Q-front队满：队满：Q-rear=Q-front可见，队空与队满有相同的描述方式：可见，队空与队满有相同的描述方式：问题：如何区分队空与队满状态？问题：如何区分队空与队满状态？2323解决方法：解决方法：设置一入队或出队标志，以区分最后一次操作是入队还是出队。这样，当头尾两个指针相等时，由该标志可以判断出满和空。少用一个元素空间，即：将仅剩一个空位置时的状态当作满状态，即:(rear+1)%MaxSize=front时，队列已满，也就是不让rear 指针赶上 front 指针。2424fronthkeabdrear0123456fronthkeabdrear0123456rearrearrearfrontfrontfrontfrontfrontfront入队入队出队出队队满队满:(1+Q-rear)%MaxSize=Q-front队空队空Q-rear=Q-front即：即：25254.2.1 顺序队列4.2.2 循环队列 4.2.3 循环队列的实现4.2 4.2 队列的顺序表示与实现26SqQueue InitQueue(SqQueue Q)Q-front=0；Q-rear=0；return Q；1.置空队置空队 按前面的讨论，队列为空时，其头尾指针相等，且为0。4.2.3 循环队列的基本运算实现循环队列的基本运算实现27int QueueEmpty(SqQueue Q)if(Q-front=Q-rear)return 1；else return 0；/队空时返回队空时返回1，不空返回，不空返回02.判队空判队空 将头尾指针是否相等作为队列是否为空的判定条件。28283.判队满判队满 按约定，“队满”是指仅剩一个空位置时的状态，即：尾指针的下一个位置就是头指针所指的位置。int QueueFull(SqQueue Q)if(Q-front=(Q-rear+1)%MaxSize)return 1；else return 0；/队满时返回队满时返回1，不满返回，不满返回02929ElemType GetHead(SqQueue Q)ElemType x;if(QueueEmpty(Q)return(error);else x=Q-data(Q-front+1)%MaxSize;return x;4.取队头元素取队头元素 首先要判断队是否空，然后才能求解。3030int EnQueue(SqQueue S，ElemType x)if(!QueueFull(Q)/若队不满，进行入队运算若队不满，进行入队运算Q-rear=(Q-rear+1)%MaxSize；Q-dataQ-rear=x；return 1 else return 0；5.入队入队 入队前，要判断队列是否已满3131ElemType DeQueue(SqQueue S)if(!QueueEmpty(Q)/若队不空，则进行出队运算若队不空，则进行出队运算Q-front=(Q-front+1)%Maxsize；return Q-dataQ-frontelse return ERROR；6.出队出队出队前，判断队列是否为空。32 循环队列的出队与入队不需要移动元素，各基本运算的实现均与队列中元素的无关，各基本运算的时间复杂度均为O(1)。循环队列的6种基本运算执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各算法的空间性能均较好。顺序循环队列对于其data数组长度的定义很难把握，如果定义过大，会造成必不可少的空间浪费，过小容易产生溢出。顺序循环队列基本算法性能分析顺序循环队列基本算法性能分析3333思考题：1 1、如何计算循环队列中元素的个数？、如何计算循环队列中元素的个数？2 2、如果对前面所讨论的循环队列采用设置运算标、如果对前面所讨论的循环队列采用设置运算标志位志位FlagFlag的方法来区分队列的满和空的状态，试给的方法来区分队列的满和空的状态，试给出对应的各运算的实现。出对应的各运算的实现。(Q-rear-Q-front+MaxSize)%MaxSize
