数据结构(Java版)队列课件.ppt

1、队列主要内容1.队列的定义2.队列的操作3.队列的实现4.实践项目：使用队列实现模拟营业厅程序。5.用java类库实现模拟营业厅程序。队列的应用n网络打印程序。当网络中的用户发送了打印作业后，那么这些作业将进入一个打印队列中等候打印，而网络打印程序每打印一份作业，就从队列中出队一份作业。n磁盘驱动程序。管理一个磁盘输入/输出请求的队列。n操作系统中的调度程序，维护一个等待处理器时间片的进程队列。n行业应用程序。比如，医院候诊程序、银行业务等候程序、移动电话业务等候程序等等。n基数排序程序。使用队列实现的一种排序方法。问题引入移动电话公司计划在某个区的某条路上新增设一个业移动电话公司计划在某个区

2、的某条路上新增设一个业务厅，配置多少个营业员比较合理？务厅，配置多少个营业员比较合理？下面是根据市场下面是根据市场调查得到的一组数据，希望以此为依据能测算出比较调查得到的一组数据，希望以此为依据能测算出比较合理的营业员配置数目。合理的营业员配置数目。n平均每天约100个顾客，平均每30秒增加一个顾客。n一个营业员处理一个顾客业务的平均时间是2分钟（120秒），也就是一个顾客实际办理业务的平均时间。n营业员处理顾客需求原则营业员处理顾客需求原则：只有一个顾客等候队列，先到先办理。如果某个营业员可以提供服务，则顾客一到就可以办理业务。如何用程序来解决这个问题呢？1、队列的定义队列的定义 和栈相反，

3、和栈相反，队列队列(Queue)是一种先进先出是一种先进先出(First In First Out,缩写为缩写为FIFO)的线性结构。的线性结构。n它只允许在表的一端进行插入，而在另一端删除元素。n这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。n在队列中，允许插入的一端叫做队尾队尾(rear)，允许删除的一端则称为队头队头(front)。2、队列的操作（运算）、队列的操作（运算）n进队：在队尾添加一个数据元素。n出队：删除队头的数据元素。n获取队头元素：获取队列中当前队头的数据元素。n获取当前队列中的元素个数：求当前队列中的元素个数。n判断队列是否为空：判断当前队列中是否还有元

4、素。3、队列的实现队列可用两种方式来实现1.数组实现：队首是索引为0的位置。2.链式实现：借助两个引用（指针）front和rear，front指向链表第一个元素,rear指向的链表最后一个元素。顺序队列存储结构及其基本状态 顺序队列的顺序队列的“假溢出假溢出”问题问题 n假设用来存储一个顺序队列的数组的长度n=5，则当数据data1,data2,data3进队后，将data1,data2依次出队，然后将data4,data5入队。此时队尾指针rear=5，如果此时有一个数据元素data想进入队列，则发生“假溢出”现象。如下图:如何解决顺序队列假溢出?n顺序队列假溢出是因为队头指针front和队

5、尾指针rear没能及时地随数组上下界值的变化而进行变化。因此解决的方法是因此解决的方法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相接的循环队列，即最后一个存储单元相邻的下一个存储位置是数组的第一个存储单元。也就是说，当也就是说，当rear和和front的值达到的值达到n-1（数组的长度）时，就使其等于（数组的长度）时，就使其等于0，这样就可以避免顺序队列头部空出许多存储单元，而队尾却因数组下标越界出现假溢出的状况。顺序循环队列的存储结构及其状态链式队列的存储结构及其基本状态 项目实践 调试运行例题调试运行例题3-2 项目设计n首先对数据元素（顾客）和数据操作（进队和出队等）进行设计，然后

6、设计一个顾客队列实现所定义的数据操作，最后在主程序中加载一个顾客队列并对其进行处理，从而得到所要的结果。项目实现步骤程序共包含下面三个类，一个接口，都放在一个源程序文件 SimulationOffice.java中。nCustomer类。定义数据元素，记录顾客到达和离开的时刻。nQueueADT类。定义数据元素的操作，即进队、出队等。nArrayQueue类。用数组实现的队列，ArrayQueue对象可以模拟顾客队列。nSimulationOffice类。接受输入数据，完成顾客队列的加载和处理，计算并输出顾客来营业厅办理业务所花费的平均时间。类SimulationOffice 需要解决的问题n

7、从键盘输入业员个数、顾客人数、业务处理时间和顾客到达的平均间隔时间。n根据顾客人数和顾客到达的平均间隔时间值构造一个顾客等候队列，办事原则是先到先办理。如果某个营业员可以提供服务（空闲），则顾客一到就可以办理业务。n设置一个数组用来记录营业员当前的空闲时刻。为了简单起见，我们用整数来表示这个时间，初始的空闲时刻均为0。总是最先空闲的那个营业员来处理当前顾客队列中的队头顾客，当一个营业员处理完一个顾客要求后，顾客离去的时刻就是这个营业员的当前空闲时刻。n顾客离去时间的计算。如果顾客到达时间大于当前营业员当前空闲时刻，则顾客一到就可以办理业务，离去时间=到达时间+业务处理时间；如果顾客到达时间小于

8、营业员当前空闲时刻，则需要等候，离去时间=营业员当前空闲时刻+业务处理时刻n累加每个顾客花费的时间。n计算并输出每个顾客平均花费的时间。具体实现算法1 定义相关变量2 从键盘输入售票员个数,业务处理时间,顾客数目,顾客之间的间隔时间.3 定义一个数组用来记录每个营业员的当前时间4 定义一个顾客队列cQueue,并初始化队列中每个顾客的到达时间,每隔*秒到达一个顾客5 Whilie(cQueue不空)出队一个顾客 找出当前时间最小的那个营业员,由该营业员来处理这个 顾客.当顾客到达时间大于营业员当前时间时,该顾客的离开时间为 顾客到达时间+营业员处理一个顾客的时间 否则,该顾客的离开时间为该营业

9、员的当前时间+营业员处理一个 顾客的时间.修改该营业员的当前时间 累加顾客花费时间 6 计算顾客平均花费时间 7 输出售票员个数和顾客平均花费时间.课堂实训1修改程序。n为顾客增加一个编号n显示XX号顾客到XX号窗口（营业员）办理业务。课堂实训2链式队列的设计与实现链式队列的设计与实现:将例题3-2中的顺序队列改为链式队列。课堂实训3n使用使用Java类库中的集类库中的集合类实现模拟营业厅程合类实现模拟营业厅程序序.n在JAVA类库中，没有类似于Stack类的专门用来处理队列的类，但是我们可以通过LinkedList类来实现队列的功能.使用java.util.LinkedList实现队列并使用队列的步骤为：（1）导入java.util.LinkedList类（2）定义数据元素（3）实现队列（4）使用队列小结自己设计队列并使用这个队列解决问题分为下面四个步骤：（1）定义数据元素（2）定义数据操作（3）实现队列（4）使用队列