王 敬

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

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

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

一、提出問題

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

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

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

二、分析問題

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

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

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

圖1 隊列示意圖

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

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

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

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

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

三、隊列算法實現(xiàn)

（一）算法思想

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

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

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

四、結(jié)束語

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

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

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

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

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