基于队列的超市排队业务离散事件
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于队列的超市排队业务离散事件范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要： 对于日常生活中出现的排队问题，作者利用队列的相关算法加以解决，建立相应模块和流程图，将数据结构中的队列知识进行实际应用。通过提出问题、分析问题、选择数据结构类型、创建流程图以及算法实现等一系列过程将离散事件进行分析与研究。
关键词： 数据结构；队列；算法实现
中图分类号：TP3 文献标识码：A 文章编号：1671-7597（2012）1220092-02
0 引言
排队是我们日常生活中经常遇到的现象。一般说来，当某个时刻要求服务的数量超过服务机构的容量时，就会出现排队现象。在各种排队系统中，顾客到达的时刻与接受服务的时间都是不确定的，随着不同的时机与条件而变化，因此排队系统在某一时刻的状态也是随机的，排队现象几乎是不可避免的。如果增添服务设备，就要增加投资或产生空闲浪费；如果服务设备太少，排队现象就会严重，对顾客个人和社会都带来不利影响。所以，管理人员必须考虑在这两者之间取得平衡，以期提高服务质量，降低成本。
1 提出问题
假设某超市有十个收银窗口，从开始营业便有顾客光临。由于每个窗口在某一时刻只能接待一个顾客，因此在顾客人数众多时需在每个窗口前顺次排队，对于刚进入付款窗口的顾客，如果某个窗口的工作人员正空闲，则可上前办理业务，反之，若十个窗口均有客户所占，他便会排在人数最少的队伍后面。现在如何编制一个程序来模拟超市付款业务活动并计算顾客付款逗留的平均时间。
2 分析问题
在许多商业机构看来，顾客等待时间关乎商家的服务质量，与顾客的满意度直接相关，因此研究顾客等待服务的时间，就显得十分必要，商家可以根据统计情况，找出资源配置的薄弱环节，对资源进行优化配置。为了计算顾客付款逗留的平均时间，我们需要掌握两个关键时间点，即每个顾客到达银台和离开银台这两个时刻，用后者减去前者即为每个顾客在银台的逗留时间。那么用所有顾客逗留时间的总和除以所有进入银台的顾客数便可得出所求的平均时间。
2.2 数据结构的选择
在算法1中需要处理两类时间，一类是顾客到达银台事件，另一类是顾客离开银台事件。前一类事件发生的时刻随客户到来自然形成；后一类事件发生时刻则由顾客事务所需时间和等待所耗时间而定。根据此程序驱动是按事件发生时刻的先后顺序进行，则确定事件表为有序表，其主要操作是插入和删除事件。
模拟程序需要的另一种数据结构是队列，即表示顾客排队的队列。由于假设超市有十个收银台，因此程序中需要十个队列，每个队列中的队头顾客即为正在窗口办理业务的顾客，他办完业务离开队列的时刻就是发生顾客离开事件的时刻，也可以说，对每个队头顾客都存在一个将要驱动的客户离开事件。综上所述，此模拟程序中需要两种数据结构：有序链表和队列。
3 队列算法实现
3.1 算法思想
假设第一个顾客进入银台的时刻为0，即是模拟程序处理的第一个事件，之后每个顾客到达的时刻在前一个顾客到达时设定。设定到达的客户办理事务所需时间为durtime；下一个顾客将到达的时间间隔为intertime，假设当前事件发生的时刻为occurtime，则下一个顾客到达事件发生的时刻为occurtime+intertime。由此产生一个新的客户到达事件插入事件表；刚到达的客户则应插入到当前所含元素最少的队列中；若该队列在插入前为空，则还应产生一个顾客离开事件插入事件表。
顾客离开事件的处理，首先计算该顾客在银台逗留的时间，然后从队列中删除该顾客后查看队列是否空，若不空则设定一个新的队头顾客离开事件。
3.2 步骤的实现
4 结束语
实际生活中，我们常常遇到类似问题需要解决，那么如何利用数据结构的算法知识解决实际问题是我们学习者急需解决和突破的难题。本文展示的实例就为读者介绍了如何利用数据结构中的队列知识解决离散事件问题，也为今后读者更好地利用其它知识解决实际问题提供参考依据。
参考文献：
[1]严蔚敏、吴伟民，数据结构（C语言版）[M].北京：清华大学出版社.
[2]高永平、周书民，计算机与现代化[J].2005，116（4）：9-13.
[3]刘姣、葛召炎、谢静，计算机仿真[J].2011，28（7）：340-343.
[4]张桂芬、葛丽娜、黄银娟，计算机技术发展[J].2009，19（12）：51-54.