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

1 3 1栈 Stack 3 2队列 Queue 第三章栈和队列 1 定义2 逻辑结构3 存储结构4 运算规则5 实现方式 1 定义2 逻辑结构3 存储结构4 运算规则5 实现方式 2 3 2队列 只能在表的一端进行插入运算 在表的另一端进行删除运算的线性表 1 定义 一 概念 例如 队列Q a1 a2 a3 an 在队尾插入元素称为入队 在队首删除元素称为出队 队头元素 队尾元素 允许插入的一端为队尾 允许删除的一端为队头 3 与线性表相同 仍为一对一关系 顺序队或链队 以循环顺序队更常见 只能在队首和队尾运算 且访问结点时依照先进先出 FIFO 的原则 关键是掌握入队和出队操作 具体实现依顺序队或链队的不同而不同 4 二 队列的抽象数据类型定义 ADTQueue 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 约定a1端为队列头 an端为队列尾 基本操作 ADTStack 5 1 初始化队列InitQueue Q 2 入队EnQueue Q e 3 出队DeQueue Q e 4 获取队头元素内容GetHead Q e 5 判断队列是否为空QueueEmpty Q 基本操作 建队列 判断队列是否为空 入队 出队 读队头元素值 等等 6 链队列类型定义 typedefstruct QueuePtrfront 队头指针QueuePtrrear 队尾指针 LinkQueue 结点类型定义 typedefstructQNode QElemTypedata 元素structQNode next 指向下一结点的指针 Qnode QueuePtr 关于整个链队的总体描述 链队中任一结点的结构 三 队列的表示和实现 1 单链队列 队列的链式存储结构 7 a1 an Q frontQ rear Q frontQ rear 空队列 为了操作方便 添加一个头结点 令头指针指向头结点 Q front Q rear 8 StatusInitQueue LinkQueue 基本操作的算法描述 建队操作 构造空队列Q 9 链队会满吗 一般不会 因为删除时有free动作 除非内存不足 入队 尾部插入 rear next S rear S 出队 头部删除 p front next front next p next free p 链队列的入队和出队操作 10 StatusEnQueue LinkQueue 11 StatusDeQueue LinkQueue 12 队列的顺序存储结构如下图所示 附设两个指针front和rear分别指示队列头元素的位置和队列尾元素的下一个位置 约定 初始化建空队列时 令front rear 0 2 顺序队列 13 2 空队列的特征 约定 front rear 问题 1 怎样实现入队和出队操作 核心语句如下 入队 尾部插入 Q rear e rear 出队 头部删除 e Q front front 3 队列会满吗 极易装满 因为数组通常有长度限制 而其前端空间无法释放 有假溢出现象 如图 14 解决假溢出的途径 采用循环队列 在顺序队中 当尾指针已经到了数组的上界 不能再有入队操作 但实际上数组中还有空位置 这就叫 假溢出 讨论 什么叫 假溢出 如何解决 将存储队列元素的一维数组首尾相接 形成一个环状 15 16 新问题 在循环队列中 队空时front rear 队满时也会有front rear 判决条件将出现二义性 解决方案有二 使用一个计数器记录队列中元素个数 即队列长度 人为浪费一个单元 约定 队列头指针在队列尾指针的下一位置上作为队列呈 满 状态的标志 则队满特征可改为front rear 1 N N为最大队列长度 实际中常选用方案2 人为浪费一个单元 17 建队核心语句 Q base QElemType malloc sizeof QElemType MAXQSIZE 分配空间 关于整个顺序队的总体描述 defineMAXQSIZE100 最大队列长度typedefstruct QElemType base 队列的基址intfront 队头指针intrear 队尾指针 SqQueue 循环队列 队列的顺序存储结构 18 队空条件 front rear 初始化时 front rear 队满条件 front rear 1 N N MAXQSIZE 队列长度 L N rear front N 问3 在具有N个单元的循环队列中 队满时共有多少个元素 N 1个 6 问1 左图中队列MAXQSIZEN 问2 左图中队列长度L 5 19 例1 一循环队列如下图所示 若先删除4个元素 接着再插入4个元素 请问队头和队尾指针分别指向哪个位置 解 由图可知 队头和队尾指针的初态分别为front 1和rear 0 删除4个元素后front 5 再插入4个元素后 rear 0 4 6 4 rear 4 20 例2 Q 0 10 是一个循环队列 初始状态为front rear 0 画出做完下列操作后队列的头尾指针的状态变化情况 若不能入队 请指出其元素 并说明理由 d e b g h入队d e出队i j k l m入队b出队n o p入队 21 讨论 循环队列的基本操作如何实现 以建队 入队和出队三种基本操作为例 1 初始化一个空队列 算法要求 生成一空队列算法操作 为队列分配基本容量空间设置队列为空队列 其特征即 front rear 0 也可为任意单元 如1 2 22 建队的完整算法 StatusInitQueue SqQueue 23 算法说明 向循环队列的队尾插入一个元素分析 1 插入前应当先判断队列是否满 if Q rear 1 MAXQSIZE Q front returnERROR 2 插入动作Q base Q rear e Q rear Q rear 1 MAXQSIZE 2 入队操作 队列尺寸 先存放元素 后移动队尾指针 24 StatusEnQueue SqQueue 入队操作完整算法 25 3 出队操作 算法说明 删除队头元素 返回其值e分析 1 在删除前应当判断队列是否空 if Q front Q rear returnERROR 2 删除动作分析 前面约定指针front指向队首元素的位置 故 e Q base Q front Q front Q front 1 MAXQSIZE 队列尺寸 先取出元素 后移动队头指针 26 StatusDeQueue SqQueue DeQueue 出队操作完整算法 27 例3 编写一个算法 利用栈和队列的基本运算将指定队列中的内容进行逆转 分析 假设为循环队列 建立一个临时栈temps 将指定队列Q中的所有元素出队并入栈到temps中 这样队列Q为空 再将temps中的所有元素出栈并入队到Q队中 这样Q队列中的内容发生了逆转 算法如下 voidreverse SqQueue 28 while QueueEmpty Q 初始化temps栈 DeQueue Q x Push temps x While StackEmpty temps Pop temps x EnQueue Q x 29 本章小结 线性表 栈 队的异同点 相同点 逻辑结构相同 都是线性的 都可以用顺序存储或链式存储 栈和队列是两种特殊的线性表 即受限的线性表 只是对插入 删除运算加以限制 运算规则不同 线性表可任意存取 栈是后进先出表LIFO 队列是先进先出表FIFO 用途不同 线性表比较通用 堆栈用于函数调用 递归和简化设计等 队列用于离散事件模拟 OS作业调度和简化设计等 不同点 30 第3章作业 3 33 43 63 103 123 163 173 293 32