队列的定义、表示、实现.pptVIP

3.1 栈（Stack） 3.2 队列 （Queue) 第三章 栈和队列 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1 3.2 队列 只能在表的一端进行插入运算，在表的 另一端进行删除运算的线性表。 1. 1. 定义定义 一、概念： 例如：队列 Q= (a1 , a2 , a3 , ， an ) 在队尾插入元素称为入队入队； 在队首删除元素称为出队出队。 队头元素 队尾元素 允许插入的一端为队尾，允许删除的一 端为队头。 2 与线性表相同，仍为一对一关系。 顺序队或链队，以循环顺序队更常见。 只能在队首和队尾运算，且访问结点 时依照先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实 现依顺序队或链队的不同而不同。 3. 3. 存储结构：存储结构： 4. 4. 运算规则：运算规则： 5. 5. 实现方式实现方式 ： 2. 2. 逻辑结构：逻辑结构： 3 二、队列的抽象数据类型定义 ADT Queue 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定a1 端为队列头，an 端为队列尾。 基本操作： ADT Stack 4 （1）初始化队列 InitQueue( /队头指针 QueuePtr rear ; /队尾指针 LinkQueue; 结点类型定义： typedef struct QNode QElemType data; /元素 struct QNode *next; /指向下一结点的指针 Qnode , * QueuePtr ; 关于整个链队的 总体描述 链队中任一 结点的结构 三、队列的表示和实 现 1.单链队列 / -队列的链式存储结构- 6 a1 an Q.front Q.rear Q.front Q.rear 空队列 为了操作方便，添加一个头结点，令头指针指向头结点。 Q. front=Q. rear 7 Status InitQueue (LinkQueue if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK; / -基本操作的算法描述- 建队操作建队操作构造空队列构造空队列Q Q 8 Q (队尾)(队首) front a1a2a3 rear p 链队会满吗？ 一般不会，因为删除时有free动作。除 非内存不足！ 入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：p=front-next; front-next=p-next; free(p); S e 链队列的入队和出队操作 9 Status EnQueue (LinkQueue if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; 10 Status DeQueue (LinkQueue p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; /一定要考虑 free (p); return OK; 11 队列的顺序存储结构如下图所示： 附设两个指针front和rear分别指示队列头元素的位 置和队列尾元素的下一个位置 约定：初始化建空队列时，令front=rear=0； 2. 顺序队 列 12 （2） 空队列的特征？ 约定：front=rear 问题：（1）怎样实现入队和出队操作？核心语句如下： 入队(尾部插入)： Qrear=e ; rear+ ; 出队(头部删除)： e=Qfront ; front+; （3）队列会满吗？ 极易装满！因为数组通常有长度限制，而其 前端空间无法释放。有假溢出现象。如图： 13 解决假溢出的途径 采用循环队列 在顺序队中，当尾指针已经到了数组的上界 ，不能再有入队操作，但实际上数组中还有 空位置，这就叫“假溢出”。 讨论：什么叫“假溢出” ？如何解决？ 将存储队列元素的一维数组首尾相接 ，形成一个环状。 14 a3 a2 a1 0 1 2 3 N-1 rear front 循环队列（臆造）循环队列（臆造） 顺序队列顺序队列 a3 a2 a1 front rear 0 1 2 3 . . N-1 15 新问题：在循环队列中，队空时 front=rear；队满时也 会有 front=rear；判决条件将出现二义性！ 解决方案有二： 使用一个计数器记录队列中元素个数（即队列长度）； 人为浪费一个单元，约定：队列头指针在队列尾指针的 下一位置上作为队列呈“满”状态的标志。则队满特征可 改为front=(rear+1)%N （N为最大队列长度）； 实际中常选用方案2（人为浪费一个单元） 16 建队核心语句： Q. base=(QElemType *)malloc(sizeof (QElemType ） * MAXQSIZE); /分配空间 关于整个顺序 队的总体描述 #define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; /队列的基址 int front; /队头指针 int rear; /队尾指针 SqQueue / -循环队列队列的顺序存储结构- 17 队空条件 : front = rear (初始化时：front = rear ) 队满条件： front = (rear+1+1) % N (N=MAXQSIZE) 队列长度：L=（Nrearfront）% N J2 J3 J1 J4 J5 front rear 问3： 在具有N个单元的循 环队列中，队满时共有多少 个元素？ N-1个 6 问1：左图中队列MAXQSIZE N=？ 问2：左图中队列长度 L=？ 5 18 例1. 一循环队列如下图所示，若先删除4个元素，接 着再插入4个元素，请问队头和队尾指针分别指向哪个 位置? J2 J3 J1 J4 J5front=1 rear=0 解：由图可知，队头和队尾指针的初态分别为front=1 和rear=0。 删除4个元素后front=5； 再插入4个元素后，rear=(0+4)%6=4 front=5 J6 J5 J7 J8 J9 rear=4 rear=0 front=5 19 例2. Q010是一个循环队列，初始状态为 front=rear=0,画出做完下列操作后队列的头尾指针 的状态变化情况，若不能入队，请指出其元素，并说 明理由。 d, e, b, g, h 入队 d, e 出队 i, j, k, l, m 入队 b 出队 n, o, p 入队 20 讨论：循环队列的基本操作如何实现？ 以建队、入队和出队三种基本操作为例 1）初始化一个空队列 算法要求：生成一空队列 算法操作：为队列分配基本容量空间 设置队列为空队列，其特征即： front=rear=0（也可为任意单元，如1，2， ） 21 建队的完整算法： Status InitQueue ( SqQueue /分配空间 if (!Q.base) exit(OVERFLOW); Q.front =Q.rear=0; /置空队列 return OK; /InitQueue; 22 算法说明：向循环队列的队尾插入一个元素 分 析： (1) 插入前应当先判断队列是否满？ if ( Q . rear + 1 ) % MAXQSIZE )=Q.front) return ERROR; (2）插入动作 Q. base Q. rear = e; Q. rear = ( Q . rear + 1 ) % MAXQSIZE; 2） 入队操作 队列尺寸先存放元素，后移 动队尾指针 23 Status EnQueue(SqQueue /队满则上溢 Q. base Q. rear = e; /新元素e入队 Q. rear = ( Q . rear + 1 ) % MAXQSIZE; /指针后移 return OK; / EnQueue; 入队操作完整算法 24 3）出队操作 算法说明：删除队头元素，返回其值 e 分 析： （1） 在删除前应当判断队列是否空？ if (Q. front = Q. rear ) return ERROR; （2）删除动作分析： 前面约定指针front指向队首元素的位置，故： e = Q. base Q. front ; Q. front = ( Q. front + 1 ) % MAXQSIZE; 队列尺寸 先取出元素，后 移动队头指针 25 Status DeQueue ( SqQueue /队列空 e = Q. base Q.front ; Q. front=(Q. front+1) %MAXQSIZE ; return OK; / DeQueue 出队操作完整算法 26 例3：编写一个算法，利用栈和队列的基本运算将指 定队列中的内容进行逆转。 分析：假设为循环队列。建立一个临时栈temps，将指 定队列Q中的所有元素出队并入栈到temps中，这样队 列Q为空，再将temps中的所有元素出栈并入队到Q队 中，这样Q队列中的内容发生了逆转。算法如下： void reverse(SqQueue SqStack temps; InitStack(temps); 27 while( ! QueueEmpty (Q) ) /初始化temps栈 DeQueue (Q, x); Push (temps, x); While( ! StackEmpty (temps) ) Pop (temps, x); EnQueue (Q, x); 28 本章小结 线性表、栈、队的异同点： 相同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存 储或链式存储；栈和队列是两种特殊的线性表，即受限 的线性表（只