Chapter 2 Entity-Relationship Model 2019/8/1 2.4 特殊的线性表----队列 队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。 空队列：不含任何数据元素的队列。 队尾和队首：允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队首。 出队 出队 出队 出队 出队 入队 入队 入队 a1 a2 a3 队首 队首 队尾 队列的操作特性：先进先出 队列的操作： MakeNull(Q)、Front(Q)、EnQueue(x, Q)、DeQueue(Q)、Empty(Q) 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.1 队列的指针实现 队列的链接存储结构及实现 链队列：队列的链接存储结构 如何改造单链表实现队列的链接存储？ 队首指针即为链表的头结点指针 增加一个指向队尾结点的指针 head a1 a2 an ∧ front rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.1 队列的指针实现(Cont.) 队列的链接存储结构及实现 非空队列： 空队列： front a1 a2 an ∧ rear front ∧ rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.1 队列的指针实现(Cont.) 队列的链接存储结构及实现 存储结构定义 //结点的类型： struct celltype { ElemType data； celltype *next ； } ； 队列的 类型： struct QUEUE { celltype *front ； celltype *rear ； }; front a1 a2 an ∧ rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.1 队列的指针实现(Cont.) 队列的链接存储结构及实现 操作的实现----初始化和判空 ① void MakeNull( QUEUE &Q ) { Q.front = new celltype ; Q.front→next = NULL ; Q.rear = Q.front ; } ② Boolean Empty(QUEUE &Q) { if ( Q.front == Q.rear ) return TRUE ; else return FALSE ; } front ∧ rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.1 队列的指针实现(Cont.) 队列的链接存储结构及实现 操作的实现----入队 front a1 an ∧ x q ∧ ③ void EnQueue(ElemType x, QUEUE &Q) { q=new cwlltype; q->data=x ; q->next=NULL; Q.rear->next=q; Q.rear=q; } rear rear front ∧ x q ∧ rear rear 如何没有头结点会怎样？ 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.1 队列的指针实现(Cont.) 队列的链接存储结构及实现 操作的实现---出队 p front a1 a2 an ∧ rear void DeQueue(QUEUE &Q ) { if (Q.rear==Q.front) cout<<“队空"; p=Q.front->next; Q.front->next=p->next; if (p->next==NULL) Q.rear=Q.front; delete p; } p front ∧ a1 ∧ rear rear 考虑边界情况：队列中只有一个元素？ 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.2 队列的指针实现(Cont.) 队列的链接存储结构及实现 操作的实现---返回队首元素 front a1 a2 an ∧ rear ③ ElemType Front ( QUEUE Q ) { if ( Q.front→next ) return Q.front→next→ data ; } front a1 ∧ rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现 队列的数组存储结构及实现 如何改造数组实现队列的顺序存储？ a1a2a3a4依次入队 0 1 2 3 4 入队 出队 a1 a2 a3 a4 rear rear rear rear 入队操作时间性能为O(1) 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 如何改造数组实现队列的顺序存储？ a1a2依次出队 0 1 2 3 4 入队 出队 a1 a2 a3 a4 rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 如何改造数组实现队列的顺序存储？ a1a2依次出队 0 1 2 3 4 入队 出队 a2 a3 a4 rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 如何改造数组实现队列的顺序存储？ a1a2依次出队 0 1 2 3 4 入队 出队 a3 a4 rear 出队操作时间性能为O(n) 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 如何改进出队的时间性能？ 所有元素不必存储在数组的前n个单元; 只要求队列的元素存储在数组中连续单元; 设置队头、队尾两个指针. 例： a1a2a3a4依次入队 0 1 2 3 4 入队 出队 a1 a2 a3 a4 front rear rear rear rear rear 入队操作时间性能仍为O(1) 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 如何改进出队的时间性能？ a1a2依次出队 0 1 2 3 4 入队 出队 a1 a2 a3 a4 front front front rear 入队操作时间性能提高为O(1) 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 队列的移动有什么特点？ 继续入队会出现什么情况？ 假溢出： 当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，但此时数组的低端还有空闲空间，这种现象叫做假溢出。 0 1 2 3 4 入队 出队 a3 a4 a5 front rear rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 如何避免假溢出？ 循环数组：将数组最后一个单元的下一个单元看成是0号单元，即把数组头尾相接----按模加一。 循环队列：用循环数组表示的队列。 0 1 2 3 4 出队 入队 a6 a3 a4 a5 rear front rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 如何判断循环队列队空和队满？ 队空时，front和rear的相对位置 0 1 2 3 4 出队 入队 a3 front rear 0 1 2 3 4 出队 入队 a3 front front rear 队空：front==rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 如何判断循环队列队空和队满？ 队满时，front和rear的相对位置 0 1 2 3 4 出队 入队 a6 a3 a4 a5 rear front 0 1 2 3 4 出队 入队 a6 a7 a3 a4 a5 rear rear front 队满：front==rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 如何区分队空、队满的判定条件？ 方法一：增设一个存储队列中元素个数的计数器count，当front==rear 且count==0时，队空；当front==rear 且count==MaxSize时，队满； 方法二：设置标志flag，当front==rear且flag==0时为队空；当front==rear且flag==1时为队满。 方法三：保留队空的判定条件：front==rear；把队满判定条件修改为： ( (rear+1)%MaxSize==front) 。 代价：浪费一个元素空间，队满时数组中有一个空闲单元； 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 存储结构的定义 struct QUEUE { ElemType data [ MaxSize ] ; int front ； int rear ； }; //队列的类型 0 1 2 3 4 出队 入队 a6 a3 a4 a5 rear front 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 操作的实现---- ①队列初始化 void MakeNull ( QUEUE &Q) { Q.front = MaxSize-1； Q.rear = MaxSize-1; } 出队 0 1 2 3 4 入队 front rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 操作的实现---- ②队列判空 bool Empty( QUEUE Q ) { if ( Q.rear == Q.front ) return TRUE ; else return FALSE ; } 0 1 2 3 4 出队 入队 front rear 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 操作的实现---- ③返回队首元素 ElemType Front( QUEUE Q ) { if ( Empty( Q ) ) return NULLESE ; else { return (Q.data[(Q.front+1)%MaxSize] ); } 0 1 2 3 4 入队 出队 a6 a3 a4 a5 rear front 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 操作的实现---- ④入队 void EnQueue ( ElemType x, QUEUE &Q ) { if ( (Q.rear+1)%MaxSize ==Q.front ) cout<< “队列满”; else{ Q.rear=(Q.rear+1)%MaxSize ; Q.data[ Q.rear ] = x ; } 0 1 2 3 4 出队 a6 入队 a3 a4 a5 rear front 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.3 队列的数组实现(Cont.) 队列的数组存储结构及实现 操作的实现---- ⑤出队 void DeQueue ( QUEUE Q ) ; { if ( Empty ( Q ) ) cout<< “空队列” <<endl; else Q.front = (Q.front+1)%MaxSize ; } 0 1 2 3 4 出队 入队 a6 a3 a4 a5 rear front front 2019/8/1

Chapter 2 Entity-Relationship Model 2019/8/1 2.4.4 队列的应用 队列使用的原则 凡是符合先进先出原则的 服务窗口和排号机、打印机的缓冲区、分时系统、树型结构的层次遍历、图的广度优先搜索等等 举例 约瑟夫出圈问题：n个人排成一圈，从第一个开始报数，报到m的人出圈，剩下的人继续开始从1报数，直到所有的人都出圈为止。 舞伴问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写算法模拟上述舞伴配对问题。 2019/8/1