利用隊(duì)列解決離散事件問題的應(yīng)用研究

王 敬

（天津市紅橋區(qū)職工大學(xué)，天津 300131）

隊(duì)列（Queue）是僅限定在表的一端進(jìn)行插入，在另一端進(jìn)

行刪除的線性表，具有先進(jìn)先出（簡(jiǎn)稱FIFO）的特性（見圖1）。我們把隊(duì)列中允許插入的一端稱為隊(duì)尾（rear），允許刪除的一端稱為隊(duì)頭（front）。隊(duì)列是一種重要的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于日常排隊(duì)問題的求解。文中分別對(duì)隊(duì)列進(jìn)行數(shù)據(jù)類型定義，隊(duì)列算法的實(shí)現(xiàn)過程，分析隊(duì)列的具體應(yīng)用。

一、提出問題

在日常生活中，我們遇到需要排隊(duì)的情境有很多，往往需要

用到隊(duì)列這一線性表數(shù)據(jù)結(jié)構(gòu)來模擬程序，下面就拿超市收銀業(yè)務(wù)為例，介紹隊(duì)列如何在實(shí)際問題中進(jìn)行應(yīng)用。

假設(shè)某超市有十個(gè)收銀窗口，從開始營業(yè)便有顧客光臨。由于每個(gè)窗口在某一時(shí)刻只能接待一個(gè)顧客，因此在顧客人數(shù)眾多時(shí)需在每個(gè)窗口前順次排隊(duì)，對(duì)于剛進(jìn)入付款窗口的顧客，如果某個(gè)窗口的工作人員正空閑，則可上前辦理業(yè)務(wù)，反之，若十個(gè)窗口均有客戶所占，他便會(huì)排在人數(shù)最少的隊(duì)伍后面。現(xiàn)在如何編制一個(gè)程序來模擬超市付款業(yè)務(wù)活動(dòng)并計(jì)算顧客付款逗留的平均時(shí)間。

二、分析問題

為了計(jì)算顧客付款逗留的平均時(shí)間，我們需要掌握兩個(gè)關(guān)鍵時(shí)間點(diǎn)，即每個(gè)顧客到達(dá)銀臺(tái)和離開銀臺(tái)這兩個(gè)時(shí)刻，用后者減去前者即為每個(gè)顧客在銀臺(tái)的逗留時(shí)間。那么用所有顧客逗留時(shí)間的總和除以所有進(jìn)入銀臺(tái)的顧客數(shù)便可得出所求的平均時(shí)間。

（一）建立離散事件驅(qū)動(dòng)模擬程序

稱顧客到達(dá)銀臺(tái)和離開銀臺(tái)這兩個(gè)時(shí)刻發(fā)生的事情為“事件”，則整個(gè)模擬程序?qū)词录l(fā)生的先后順序進(jìn)行處理，這樣一種模擬程序稱為事件驅(qū)動(dòng)模擬。下面這個(gè)算法對(duì)此離散事件驅(qū)動(dòng)模擬程序進(jìn)行描述。

圖1 隊(duì)列示意圖

（二）數(shù)據(jù)結(jié)構(gòu)的選擇

在算法1中需要處理兩類時(shí)間，一類是顧客到達(dá)銀臺(tái)事件，另一類是顧客離開銀臺(tái)事件。前一類事件發(fā)生的時(shí)刻隨客戶到來自然形成；后一類事件發(fā)生時(shí)刻則由顧客事務(wù)所需時(shí)間和等待所耗時(shí)間而定。根據(jù)此程序驅(qū)動(dòng)是按事件發(fā)生時(shí)刻的先后順序進(jìn)行，則確定事件表為有序表，其主要操作是插入和刪除事件。

模擬程序需要的另一種數(shù)據(jù)結(jié)構(gòu)是隊(duì)列，即表示顧客排隊(duì)的隊(duì)列。由于假設(shè)超市有十個(gè)收銀臺(tái)，因此程序中需要十個(gè)隊(duì)列，每個(gè)隊(duì)列中的隊(duì)頭顧客即為正在窗口辦理業(yè)務(wù)的顧客，他辦完業(yè)務(wù)離開隊(duì)列的時(shí)刻就是發(fā)生顧客離開事件的時(shí)刻，也可以說，對(duì)每個(gè)隊(duì)頭顧客都存在一個(gè)將要驅(qū)動(dòng)的客戶離開事件。綜上所述，此模擬程序中需要兩種數(shù)據(jù)結(jié)構(gòu)：有序鏈表和隊(duì)列。

（三）數(shù)據(jù)類型定義

根據(jù)模擬程序的兩種數(shù)據(jù)結(jié)構(gòu)，確定了數(shù)據(jù)元素類型分別定義如下：

三、隊(duì)列算法實(shí)現(xiàn)

（一）算法思想

假設(shè)第一個(gè)顧客進(jìn)入銀臺(tái)的時(shí)刻為0，即是模擬程序處理的第一個(gè)事件，之后每個(gè)顧客到達(dá)的時(shí)刻在前一個(gè)顧客到達(dá)時(shí)設(shè)定。設(shè)定到達(dá)的客戶辦理事務(wù)所需時(shí)間為durtime；下一個(gè)顧客將到達(dá)的時(shí)間間隔為intertime，假設(shè)當(dāng)前事件發(fā)生的時(shí)刻為occurtime，則下一個(gè)顧客到達(dá)事件發(fā)生的時(shí)刻為occurtime＋intertime。由此產(chǎn)生一個(gè)新的客戶到達(dá)事件插入事件表；剛到達(dá)的客戶則應(yīng)插入到當(dāng)前所含元素最少的隊(duì)列中；若該隊(duì)列在插入前為空，則還應(yīng)產(chǎn)生一個(gè)顧客離開事件插入事件表。

顧客離開事件的處理，首先計(jì)算該顧客在銀臺(tái)逗留的時(shí)間，然后從隊(duì)列中刪除該顧客后查看隊(duì)列是否空，若不空則設(shè)定一個(gè)新的隊(duì)頭顧客離開事件。

（二）算法實(shí)現(xiàn)

四、結(jié)束語

實(shí)際生活中，我們常常遇到類似問題需要解決，那么如何利用數(shù)據(jù)結(jié)構(gòu)的算法知識(shí)解決實(shí)際問題是我們學(xué)習(xí)者急需解決和突破的難題。本文展示的實(shí)例就為讀者介紹了如何利用數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列知識(shí)解決離散事件問題，也為今后讀者更好地利用其它知識(shí)解決實(shí)際問題提供參考依據(jù)。

［1］嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語言版）［M］．北京：清華大學(xué)出版社，1997．

［2］高永平，周書民．循環(huán)隊(duì)列中入隊(duì)算法的研究［J］．計(jì)算機(jī)與現(xiàn)代化，2005，（04）．

［3］劉姣，葛召炎，謝靜．停車場(chǎng)泊車問題的研究與仿真［J］．計(jì)算機(jī)仿真，2011，（07）．

［4］張桂芬，葛麗娜，黃銀娟．基于棧結(jié)構(gòu)的孔明棋算法研究［J］．計(jì)算機(jī)技術(shù)發(fā)展，2009，（12）．