数据结构（Python Java）（微课版） 课件 3.2 队列

数据结构与算法设计3.2队列队列的定义与基本操作队列的顺序存储结构与实现队列的链式存储结构与实现循环队列与链队列的比较队列的应用案例队列的定义队列的定义与基本操作只能在表的一端进行插入，在表的另一端进行删除的线性表（a1,a2,…,an-1,an）a1

a2

…

an栈a1

a2

…

an队列队头队尾队尾：允许插入的一端，相应地，位于队尾的元素称为队尾元素队头：允许删除的一端，相应地，位于队头的元素称为队头元素队列的操作队列的定义与基本操作队列的操作特性：先进先出（FirstInFirstOut，FIFO）a插入：入队、进队入队bc例：有三个元素按a、b、c的次序依次入队，且每个元素只允许进一次队，则出队序列是什么？答：出队序列只有一种情况：abc出队删除：出队空队列：不含任何数据元素的队列

任何时候执行出队操作，一定是哪个元素呢？队列的基本操作队列的定义与基本操作initQueue()：初始化。设置一个空队列qisEmpty()：判断队列是否为空。若队列q为空，函数值为true，否则为false

size()：求队列长度。函数值为队列q中当前所含元素的个数getHead()：读队头元素。若队列q不为空，函数值为队头元素，否则为空元素enQueue(x)：入队。将元素x插入队列q的尾部，使x成为新的队尾元素delQueue()：出队。若队列q不为空，函数值为队头元素，且从队列q中删除当前队头元素，否则函数值为空元素顺序队列队列的顺序存储结构与实现队列的顺序存储结构队尾：设变量rear存储队尾元素所在的下标队头：用数组的一端作为队头，从下标0处开始存放01234a1a2a3a4例：a1a2a3a4

依次入队顺序队列队列的顺序存储结构与实现例：a1

出队01234a1a2a3a401234a2a3a4队头元素出队后，后面的元素都需要前移，时间性能较差如何改进出队操作的时间性能？01234a2a3a4设置队头、队尾两个位置变量约定：队头front指向队头元素的前一个位置，队尾rear指向队尾元素a1入队、出队时间性能均是O(1)顺序队列队列的顺序存储结构与实现顺序队列队列的顺序存储结构与实现队列的移动有什么特点？01234a2a3a4队列的单向移动性会产生什么问题？a5假溢出：数组空间发生上溢，但数组的低端还有空闲空间循环队列队列的顺序存储结构与实现如何解决假溢出呢？01234a3a4如何使数组下标循环呢？a5a6循环队列：队列采用顺序存储，并且数组是头尾相接的循环结构循环队列队列的顺序存储结构与实现01234a3front如何判断循环队列的队空？队空的判定条件：front==rear循环队列队列的顺序存储结构与实现a6a2a4a5front如何判断循环队列队满？队空的判定条件：front==rear队满的判定条件：front==rearx01234循环队列队列的顺序存储结构与实现如何确定不同的队空、队满的判定条件？队空的判定条件：front==rear队满的判定条件：front==rear数组中有一个空闲单元01234a6a2a4a5front01234a1a2a4a5front(rear+1)%QUEUE_SIZE=front链队列队列的链式存储是单链表，同时带有头指针和尾指针头指针指向队头结点尾指针指向队尾结点队列的链式存储结构头结点^…...head队头队尾tail设队首、队尾指针head和tail,head指向队头，tail指向队尾循环队列与链队列的比较循环队列和链队列基本算法的时间复杂度均为O(1)空间复杂度比较初始时循环队列必须确定一个固定的长度，所以存在存储元素个数的限制和浪费存储空间的问题。链队列没有溢出问题，只有当内存没有可用存储空间时才会出现溢出，但是每个元素都需要指针域，存在结构性开销。队列的应用案例舞伴配对问题在某舞会上，男士和女士进入舞厅时，各自排成一队。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮。在算法中，假设男士和女士的记录存放在一个数组中，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成后，依次使两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮开始时第一个可获得舞伴的人。队列的应用案例时间片轮转调度问题系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一