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

《数据结构(Java版)队列课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、O)的线性结构。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。2、队列的操作（运算）进队：在队尾添加一个数据元素。出队：删除队头的数据元素。获取队头元素：获取队列中当前队头的数据元素。获取当前队列中的元素个数：求当前队列中的元素个数。判断队列是否为空：判断当前队列中是否还有元素。3、队列的实现队列可用两种方式来实现数组实现：队首是索引为0的位置。链式实现：借助两个引用（指

4、针）front和rear，front指向链表第一个元素,rear指向的链表最后一个元素。顺序队列存储结构及其基本状态顺序队列的“假溢出”问题假设用来存储一个顺序队列的数组的长度n=5，则当数据data1,data2,data3进队后，将data1,data2依次出队，然后将data4,data5入队。此时队尾指针rear=5，如果此时有一个数据元素data想进入队列，则发生“假溢出”现象。如下图:如何解决顺序队列假溢出?顺序队列假溢出是因为队头指针front和队尾指针rear没能及时地随数组上下界值的变化而进行变化。因

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

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

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

8、办理业务，离去时间=到达时间+业务处理时间；如果顾客到达时间小于营业员当前空闲时刻，则需要等候，离去时间=营业员当前空闲时刻+业务处理时刻累加每个顾客花费的时间。计算并输出每个顾客平均花费的时间。具体实现算法1定义相关变量2从键盘输入售票员个数,业务处理时间,顾客数目,顾客之间的间隔时间.3定义一个数组用来记录每个营业员的当前时间