数据结构CC版第4章 研究队列.pptx

《数据结构CC版第4章 研究队列.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（C语言版）项目四研究队列在本项目中，通过1个工作任务，读者展示队列(Queue)的定义、特点、各种存储结构以及相应的运算。目录任务使用队列模拟打印操作程序使用队列模拟打印操作程序准备知识使用队列模拟打印操作程序队列的的概述队列的抽象数据类型和基本操作队列的顺序存储结构顺序队列的改进——循环队列队列的链式存储结构1.队列的的概述1.队列的的概述队列（queue）也是一种操作受限的线性表，只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。（1）允许删除的一端称为队头（Front）。（2）允许

2、插入的一端称为队尾（Rear）。（3）当队列中没有元素时称为空队列。（4）队列亦称作先进先出（FIFO，First-In-First-Out）的线性表，简称为FIFO表。拓展提高：在具体应用中通常用链表或者数组来实现。队列只允许在后端进行插入操作，在前端进行删除操作。队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。2.队列的抽象数据类型和基本操作2.队列的抽象数据类型和基本操作队列的抽象数据类型定义如下：ADTQueue{（1）数据元素D：可以是任意类型的数据，但必须属于同一个数据对

3、象。（2）数据关系R：队列中数据元素之间是线性关系。（3）队列的基本操作。}队列的基本操作包括：（1）初始化：构造一个空队列Q。（2）判断是否为空：若队列Q为空，则返回真值，否则返回假值。（3）判断队列是否已满：若队列Q为满，则返回真值，否则返回假值。（此操作只适用于队列的顺序存储结构。）（4）清空队列：从队列中清除所有数据元素，队列为空。（5）求队列长度：若队列存在，则返回队列中所有数据元素的个数。（6）取队列头：取队列头元素但元素并不出队列。（7）进队：若队列Q非满，则将元素e插入Q的队尾。亦称入队。（

4、8）出队：若队列Q非空，则删去Q的队头元素，并返回该元素。（9）销毁队列：队列销毁操作。释放队列的空间。2.队列的抽象数据类型和基本操作3.队列的顺序存储结构3.队列的顺序存储结构队列的顺序存储结构称为顺序队列。因为队列的队头和队尾都是活动的，因此，除了队列的数据区外还有队头、队尾两个指针。队列的顺序存储结构和栈类似，在计算机中，常借助于一维数组来存储队列中的元素。顺序队列实际上是运算受限的顺序队列。顺序队列有如下特性：（1）和顺序队列一样，顺序队列用一个向量空间来存放当前队列中的元素。（2）由于队列的队头

5、和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0，如下图所示。顺序队列示意图3.队列的顺序存储结构1.顺序队列的改进

6、

7、循环队列4.顺序队列的改进——循环队列针对上节中提到的假溢出问题，通常会采用循环队列的形式来处理。循环队列是将队列的数据区data[MAXSIZE]看成头尾相接的循环结构，头尾指针的关系不变。知识点链接循环队列实质上仍然还是顺序存储结构，只是形式上有所改变而已，但是能有效的解决假溢出问题。5.队列的链式存

8、储结构5.队列的链式存储结构对于使用中数据元素变动较大的数据结构，采用链式存储结构比顺序存储结构更有利。链队列就是这样一种数据结构。用链表表示的队列需要两个指针，分别指示队头和队尾，如下图所示。链队列示意图知识点链接（1）和链栈类似，单链队列使用链表作为基本数据结果，所以不存在伪溢出的问题，队列长度也没有限制。但插入和读取的时间代价较高。（2）在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。（3）以上讨论的是无头结点

9、链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算。任务实施张丽是某公司程序员，接到上级任务，她需要编写程序，要求模似办公室共享一台打印机，设置打印机的打印管理顺序。使用队列模拟打印操作程序任务：使用队列模拟打印操作程序任务分析：理解牢记！由于队列的特点是先进先出。同时，使用打印机打印文件也是先到先打印文件。因此，张丽决定使用队列来完成此任务。任务：使用队列模拟打印操作程序任务实施使用队列模拟打印机打印顺序某公司办公系统局域网内有若干台计算机

10、，共享一台打印机。张丽设计一个对打印机的打印任务进行管理的程序，打印机的打印任务按先来先服务的方式进行管理。算法分析：打印任务可设计成一个队列，本例采用链式队列实现。打印队列管理应包含的基本操作包括：InitQueue(LinkedQueue*Q)：初始化队列。EnPrintTaskQueue(LinkedQueue*Q，Elmente)：入队列，把新的打印任务加入到队尾。DePrintTaskQueue(Lin