利用队列解决离散事件问题的应用研究

王 敬

（天津市红桥区职工大学，天津 300131）

队列（Queue）是仅限定在表的一端进行插入，在另一端进

行删除的线性表，具有先进先出（简称FIFO）的特性（见图1）。我们把队列中允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列是一种重要的数据结构，广泛应用于日常排队问题的求解。文中分别对队列进行数据类型定义，队列算法的实现过程，分析队列的具体应用。

一、提出问题

在日常生活中，我们遇到需要排队的情境有很多，往往需要

用到队列这一线性表数据结构来模拟程序，下面就拿超市收银业务为例，介绍队列如何在实际问题中进行应用。

假设某超市有十个收银窗口，从开始营业便有顾客光临。由于每个窗口在某一时刻只能接待一个顾客，因此在顾客人数众多时需在每个窗口前顺次排队，对于刚进入付款窗口的顾客，如果某个窗口的工作人员正空闲，则可上前办理业务，反之，若十个窗口均有客户所占，他便会排在人数最少的队伍后面。现在如何编制一个程序来模拟超市付款业务活动并计算顾客付款逗留的平均时间。

二、分析问题

为了计算顾客付款逗留的平均时间，我们需要掌握两个关键时间点，即每个顾客到达银台和离开银台这两个时刻，用后者减去前者即为每个顾客在银台的逗留时间。那么用所有顾客逗留时间的总和除以所有进入银台的顾客数便可得出所求的平均时间。

（一）建立离散事件驱动模拟程序

称顾客到达银台和离开银台这两个时刻发生的事情为“事件”，则整个模拟程序将按事件发生的先后顺序进行处理，这样一种模拟程序称为事件驱动模拟。下面这个算法对此离散事件驱动模拟程序进行描述。

图1 队列示意图

（二）数据结构的选择

在算法1中需要处理两类时间，一类是顾客到达银台事件，另一类是顾客离开银台事件。前一类事件发生的时刻随客户到来自然形成；后一类事件发生时刻则由顾客事务所需时间和等待所耗时间而定。根据此程序驱动是按事件发生时刻的先后顺序进行，则确定事件表为有序表，其主要操作是插入和删除事件。

模拟程序需要的另一种数据结构是队列，即表示顾客排队的队列。由于假设超市有十个收银台，因此程序中需要十个队列，每个队列中的队头顾客即为正在窗口办理业务的顾客，他办完业务离开队列的时刻就是发生顾客离开事件的时刻，也可以说，对每个队头顾客都存在一个将要驱动的客户离开事件。综上所述，此模拟程序中需要两种数据结构：有序链表和队列。

（三）数据类型定义

根据模拟程序的两种数据结构，确定了数据元素类型分别定义如下：

三、队列算法实现

（一）算法思想

假设第一个顾客进入银台的时刻为0，即是模拟程序处理的第一个事件，之后每个顾客到达的时刻在前一个顾客到达时设定。设定到达的客户办理事务所需时间为durtime；下一个顾客将到达的时间间隔为intertime，假设当前事件发生的时刻为occurtime，则下一个顾客到达事件发生的时刻为occurtime＋intertime。由此产生一个新的客户到达事件插入事件表；刚到达的客户则应插入到当前所含元素最少的队列中；若该队列在插入前为空，则还应产生一个顾客离开事件插入事件表。

顾客离开事件的处理，首先计算该顾客在银台逗留的时间，然后从队列中删除该顾客后查看队列是否空，若不空则设定一个新的队头顾客离开事件。

（二）算法实现

四、结束语

实际生活中，我们常常遇到类似问题需要解决，那么如何利用数据结构的算法知识解决实际问题是我们学习者急需解决和突破的难题。本文展示的实例就为读者介绍了如何利用数据结构中的队列知识解决离散事件问题，也为今后读者更好地利用其它知识解决实际问题提供参考依据。

［1］严蔚敏，吴伟民．数据结构（C语言版）［M］．北京：清华大学出版社，1997．

［2］高永平，周书民．循环队列中入队算法的研究［J］．计算机与现代化，2005，（04）．

［3］刘姣，葛召炎，谢静．停车场泊车问题的研究与仿真［J］．计算机仿真，2011，（07）．

［4］张桂芬，葛丽娜，黄银娟．基于栈结构的孔明棋算法研究［J］．计算机技术发展，2009，（12）．