簡介這份資源是面向計(jì)算機(jī)專業(yè)學(xué)生與數(shù)據(jù)結(jié)構(gòu)初學(xué)者的課程作業(yè)參考包圍繞「銀行排隊(duì)系統(tǒng)」這一經(jīng)典場景重點(diǎn)演示隊(duì)列FIFO結(jié)構(gòu)及VIP與普通用戶雙隊(duì)列的優(yōu)先級調(diào)度設(shè)計(jì)。包內(nèi)共9個文件以cpp源碼、txt數(shù)據(jù)文件、cbp工程配置及exe可執(zhí)行程序?yàn)橹髁砗幾g中間產(chǎn)物與項(xiàng)目布局文件壓縮包約1.03MB可直接用Code::Blocks打開運(yùn)行。源碼中涵蓋入隊(duì)出隊(duì)、多隊(duì)列優(yōu)先級判斷、文件讀取用戶信息與循環(huán)模擬服務(wù)流程等核心邏輯適合對照理解STL queue容器的實(shí)際用法并作為期末作業(yè)的排錯與結(jié)構(gòu)參考。目前已有3367人學(xué)習(xí)下載便于讀者快速搭建可運(yùn)行示例、驗(yàn)證優(yōu)先級處理思路并查漏補(bǔ)缺。1. 銀行排隊(duì)系統(tǒng)一份數(shù)據(jù)結(jié)構(gòu)期末作業(yè)的完整落地思路銀行排隊(duì)系統(tǒng)這個題目幾乎每年都會出現(xiàn)在數(shù)據(jù)結(jié)構(gòu)期末作業(yè)的選題清單里。表面上看它只是隊(duì)列的增刪改查但真正動手做過的同學(xué)都清楚難點(diǎn)根本不在隊(duì)列本身而在于怎么把隨機(jī)到達(dá)的客戶、多個服務(wù)窗口、等待時(shí)間統(tǒng)計(jì)這幾件事組織成一個能跑、能出數(shù)據(jù)、能講清楚的結(jié)構(gòu)。我見過太多作業(yè)最后只交了一個Queue類加幾個cout答辯時(shí)被問一句平均等待時(shí)間怎么算的就卡住了。這份方案要解決的就是這個問題把銀行排隊(duì)系統(tǒng)當(dāng)成一個完整的小型仿真系統(tǒng)來設(shè)計(jì)從需求拆解、數(shù)據(jù)結(jié)構(gòu)選型到模塊實(shí)現(xiàn)、指標(biāo)統(tǒng)計(jì)再到最后的驗(yàn)收答辯給出一條能直接照著走的路徑。適合正在趕數(shù)據(jù)結(jié)構(gòu)期末作業(yè)、課程設(shè)計(jì)的學(xué)生也適合想拿一個經(jīng)典案例練手隊(duì)列與仿真的開發(fā)者。2. 需求拆解與數(shù)據(jù)結(jié)構(gòu)選型為什么不能只用一個隊(duì)列2.1 先把業(yè)務(wù)場景翻譯成可計(jì)算的需求銀行排隊(duì)系統(tǒng)的原始描述通常很模糊模擬客戶排隊(duì)辦理業(yè)務(wù)。要把它變成能寫代碼的需求我一般會先問四個問題客戶怎么來、窗口怎么服務(wù)、排隊(duì)規(guī)則是什么、最后要輸出什么。這四個問題對應(yīng)四組需求?？蛻舻竭_(dá)是隨機(jī)的通常假設(shè)單位時(shí)間內(nèi)到達(dá)人數(shù)服從泊松分布或者簡化為每個時(shí)間片以概率 p 到達(dá)一個客戶。服務(wù)時(shí)間也是隨機(jī)的常見做法是給每個客戶隨機(jī)生成一個業(yè)務(wù)辦理時(shí)長或者按業(yè)務(wù)類型存取款、開戶、轉(zhuǎn)賬給不同的時(shí)長區(qū)間。排隊(duì)規(guī)則默認(rèn)是先到先服務(wù)也就是標(biāo)準(zhǔn)隊(duì)列語義但如果要做進(jìn)階版可以加入 VIP 客戶優(yōu)先這就變成了優(yōu)先隊(duì)列。輸出指標(biāo)一般包括總客戶數(shù)、平均等待時(shí)間、最大等待時(shí)間、各窗口服務(wù)人數(shù)、客戶平均逗留時(shí)間。把這四組需求寫清楚作業(yè)的評分點(diǎn)基本就浮出來了。導(dǎo)師看的不只是你有沒有用隊(duì)列而是你有沒有把隨機(jī)性和統(tǒng)計(jì)這兩件事做對。很多作業(yè)翻車就翻在只做了確定性的入隊(duì)出隊(duì)沒有任何隨機(jī)模擬也沒有任何統(tǒng)計(jì)輸出看起來像隊(duì)列的單元測試而不是一個系統(tǒng)。2.2 核心結(jié)構(gòu)隊(duì)列為主輔助結(jié)構(gòu)補(bǔ)齊主結(jié)構(gòu)毫無疑問是隊(duì)列?？蛻舻竭_(dá)時(shí)入隊(duì)窗口空閑時(shí)從隊(duì)頭取人這是最基礎(chǔ)的 FIFO 語義。但只有隊(duì)列是不夠的實(shí)際實(shí)現(xiàn)里通常還要配幾個輔助結(jié)構(gòu)。窗口狀態(tài)需要一個數(shù)組或列表來維護(hù)每個窗口記錄當(dāng)前是否忙碌和當(dāng)前客戶還需服務(wù)多久。事件處理需要一個時(shí)間驅(qū)動的循環(huán)每個時(shí)間片推進(jìn)一次檢查有沒有新客戶到達(dá)、有沒有窗口完成服務(wù)。統(tǒng)計(jì)部分需要累加器記錄每個客戶的到達(dá)時(shí)刻和開始服務(wù)時(shí)刻兩者相減就是等待時(shí)間。如果做 VIP 版本主結(jié)構(gòu)就要從普通隊(duì)列換成優(yōu)先隊(duì)列通常用堆實(shí)現(xiàn)優(yōu)先級按客戶等級排序同級再按到達(dá)時(shí)間排序。這里有個容易忽略的點(diǎn)優(yōu)先隊(duì)列的穩(wěn)定很重要如果兩個 VIP 客戶等級相同必須先服務(wù)先到的那個否則統(tǒng)計(jì)結(jié)果會失真。標(biāo)準(zhǔn)堆不保證穩(wěn)定性通常的做法是在優(yōu)先級里加入到達(dá)時(shí)間作為次級鍵。下面是一個簡化的結(jié)構(gòu)定義用 Python 寫邏輯清晰換成 C 或 Java 也容易遷移from dataclasses import dataclass, field from collections import deque import random dataclass class Customer: cid: int # 客戶編號 arrive_time: int # 到達(dá)時(shí)刻 service_duration: int # 需要服務(wù)時(shí)長 start_time: int -1 # 開始服務(wù)時(shí)刻-1 表示尚未開始 level: int 0 # 0 普通1 VIP dataclass class Window: wid: int busy_until: int 0 # 當(dāng)前客戶服務(wù)結(jié)束時(shí)刻 served_count: int 0 # 已服務(wù)人數(shù)這段代碼的關(guān)鍵在于Customer同時(shí)攜帶了到達(dá)時(shí)刻和服務(wù)時(shí)長Window用busy_until表示占用狀態(tài)而不是布爾值。用結(jié)束時(shí)刻代替是否忙碌的好處是時(shí)間推進(jìn)時(shí)只需要比較當(dāng)前時(shí)刻和busy_until不用額外維護(hù)倒計(jì)時(shí)邏輯更干凈。start_time初始化為 -1 是為了區(qū)分還沒開始服務(wù)和在時(shí)刻 0 開始服務(wù)統(tǒng)計(jì)等待時(shí)間時(shí)不會算錯。2.3 時(shí)間驅(qū)動還是事件驅(qū)動這是選型里最容易被低估的一個決策。時(shí)間驅(qū)動是每個時(shí)間片推進(jìn)一格檢查所有窗口和到達(dá)事件事件驅(qū)動是維護(hù)一個事件優(yōu)先隊(duì)列每次直接跳到下一個事件發(fā)生的時(shí)刻。兩種都能做對但適用場景不同。時(shí)間驅(qū)動的優(yōu)點(diǎn)是直觀、好調(diào)試每個時(shí)間片的狀態(tài)都能打印出來適合作業(yè)演示和答辯講解。缺點(diǎn)是如果服務(wù)時(shí)長跨度很大會有大量空轉(zhuǎn)時(shí)間片。事件驅(qū)動效率高但實(shí)現(xiàn)復(fù)雜度上一個臺階需要維護(hù)到達(dá)事件和離開事件兩類事件還要處理同一時(shí)刻多個事件的順序。我的建議是期末作業(yè)默認(rèn)用時(shí)間驅(qū)動把時(shí)間片設(shè)成 1 分鐘或 1 個時(shí)間單位客戶到達(dá)概率和服務(wù)時(shí)長都按這個粒度生成。這樣代碼量可控答辯時(shí)也容易畫時(shí)間軸解釋。如果導(dǎo)師明確要求性能或者要做大規(guī)模仿真再上事件驅(qū)動。選型不是越復(fù)雜越好而是要和你的演示能力匹配。3. 總體架構(gòu)與模塊劃分四個模塊撐起一個可演示的系統(tǒng)3.1 分層結(jié)構(gòu)輸入層、仿真層、統(tǒng)計(jì)層、輸出層一個能拿得出手的銀行排隊(duì)系統(tǒng)代碼不應(yīng)該全堆在一個main里。我通常按四層來切輸入層負(fù)責(zé)讀取參數(shù)窗口數(shù)、仿真總時(shí)長、到達(dá)概率、服務(wù)時(shí)長范圍仿真層負(fù)責(zé)時(shí)間推進(jìn)和隊(duì)列調(diào)度統(tǒng)計(jì)層負(fù)責(zé)收集指標(biāo)輸出層負(fù)責(zé)打印結(jié)果和生成報(bào)告。這樣切的好處是每一層都能單獨(dú)測試。輸入層可以用固定參數(shù)跑仿真層可以注入確定性的隨機(jī)種子復(fù)現(xiàn)結(jié)果統(tǒng)計(jì)層可以喂假數(shù)據(jù)驗(yàn)證公式輸出層可以單獨(dú)調(diào)格式。答辯時(shí)如果被問到某個指標(biāo)怎么來的你能直接指到統(tǒng)計(jì)層的某個函數(shù)而不是在一大坨代碼里翻。模塊之間的數(shù)據(jù)流是單向的輸入層產(chǎn)出配置對象仿真層消費(fèi)配置并產(chǎn)出客戶記錄列表統(tǒng)計(jì)層消費(fèi)客戶記錄算出指標(biāo)輸出層消費(fèi)指標(biāo)和記錄生成展示。單向數(shù)據(jù)流意味著任何一層出問題都不會污染其他層排查時(shí)可以先看客戶記錄對不對再看統(tǒng)計(jì)公式對不對最后看輸出格式。3.2 仿真主循環(huán)的設(shè)計(jì)要點(diǎn)仿真層的核心是一個按時(shí)間推進(jìn)的主循環(huán)。每個時(shí)間片做三件事處理新到達(dá)、處理窗口完成、推進(jìn)時(shí)間。順序很重要如果先推進(jìn)時(shí)間再處理到達(dá)會導(dǎo)致客戶到達(dá)時(shí)刻偏移如果先處理窗口完成再處理到達(dá)同一時(shí)刻的空閑窗口可能錯過剛到達(dá)的客戶。正確的順序通常是先檢查窗口完成釋放窗口再處理新到達(dá)入隊(duì)然后嘗試把隊(duì)頭客戶分配給空閑窗口最后時(shí)間加一。這個順序保證了同一時(shí)刻釋放的窗口能立刻服務(wù)同一時(shí)刻到達(dá)的客戶符合現(xiàn)實(shí)直覺。def simulate(config, seed42): random.seed(seed) # 固定種子保證結(jié)果可復(fù)現(xiàn) queue deque() windows [Window(i) for i in range(config.window_count)] customers [] cid 0 for t in range(config.total_time): # 1. 釋放已完成服務(wù)的窗口 for w in windows: if w.busy_until t: w.busy_until 0 # 2. 新客戶到達(dá) if random.random() config.arrive_prob: c Customer(cid, t, random.randint(*config.service_range)) cid 1 queue.append(c) customers.append(c) # 3. 空閑窗口取隊(duì)頭 for w in windows: if w.busy_until 0 and queue: c queue.popleft() c.start_time t w.busy_until t c.service_duration w.served_count 1 return customers, windows這段主循環(huán)里busy_until t的判斷讓窗口在服務(wù)結(jié)束的那個時(shí)間片就能被釋放而不是等到下一個時(shí)間片。random.seed(seed)是血淚經(jīng)驗(yàn)沒有固定種子每次跑出來的平均等待時(shí)間都不一樣答辯時(shí)沒法復(fù)現(xiàn)導(dǎo)師會懷疑你的統(tǒng)計(jì)有問題。固定種子后同一組參數(shù)永遠(yuǎn)得到同一組結(jié)果調(diào)試和演示都穩(wěn)。參數(shù)說明arrive_prob是每個時(shí)間片的到達(dá)概率取值 0 到 1通常設(shè) 0.3 到 0.5 比較接近真實(shí)銀行網(wǎng)點(diǎn)的忙碌程度service_range是服務(wù)時(shí)長的閉區(qū)間比如 (2, 8) 表示每個客戶需要 2 到 8 個時(shí)間單位total_time是仿真總時(shí)長設(shè) 480 可以模擬一個 8 小時(shí)工作日的分鐘級仿真。3.3 統(tǒng)計(jì)模塊指標(biāo)公式要經(jīng)得起追問統(tǒng)計(jì)模塊是整個作業(yè)的黑匣子也是最容易被追問的地方。核心指標(biāo)有四個公式必須寫清楚。平均等待時(shí)間等于所有客戶的start_time - arrive_time之和除以客戶總數(shù)。注意只統(tǒng)計(jì)真正被服務(wù)過的客戶如果仿真結(jié)束時(shí)隊(duì)列里還有沒被服務(wù)的客戶要么排除要么單獨(dú)標(biāo)注不能混進(jìn)平均值。最大等待時(shí)間是所有等待時(shí)間取最大值用來反映最壞體驗(yàn)。平均逗留時(shí)間等于start_time - arrive_time service_duration的平均值也就是客戶從進(jìn)店到離開的總時(shí)長。窗口利用率等于窗口忙碌時(shí)間片總數(shù)除以窗口數(shù)乘以總時(shí)長。這里有個常見錯誤把start_time為 -1 的客戶也算進(jìn)平均等待時(shí)間結(jié)果出現(xiàn)負(fù)數(shù)或者異常大的值。正確的做法是先過濾start_time 0的客戶再統(tǒng)計(jì)。另一個錯誤是窗口利用率的分母算錯應(yīng)該是窗口數(shù) × 仿真時(shí)長不是客戶數(shù) × 平均服務(wù)時(shí)長后者在客戶沒排滿時(shí)會高估利用率。def compute_stats(customers, windows, total_time): served [c for c in customers if c.start_time 0] waits [c.start_time - c.arrive_time for c in served] stays [c.start_time - c.arrive_time c.service_duration for c in served] busy_slots sum(w.served_count * 0 for w in windows) # 占位實(shí)際按記錄累加 return { total_customers: len(customers), served_customers: len(served), avg_wait: sum(waits) / len(waits) if waits else 0, max_wait: max(waits) if waits else 0, avg_stay: sum(stays) / len(stays) if stays else 0, unserved: len(customers) - len(served), }這段統(tǒng)計(jì)代碼里served的過濾是關(guān)鍵unserved單獨(dú)輸出是為了讓報(bào)告完整——如果仿真結(jié)束時(shí)還有大量客戶沒被服務(wù)說明窗口數(shù)或仿真時(shí)長設(shè)置不合理這個數(shù)字本身就是結(jié)論的一部分。busy_slots那行是占位實(shí)際實(shí)現(xiàn)里應(yīng)該在仿真循環(huán)中累加每個窗口的忙碌時(shí)間片而不是事后用served_count反推因?yàn)椴煌蛻舻姆?wù)時(shí)長不同反推會失真。4. 關(guān)鍵實(shí)現(xiàn)細(xì)節(jié)從能跑到跑得對4.1 隨機(jī)數(shù)生成的可復(fù)現(xiàn)性前面提過固定種子這里展開說。Python 的random模塊是全局狀態(tài)如果仿真函數(shù)里調(diào)用了其他也使用random的代碼種子會被干擾。穩(wěn)妥的做法是給仿真單獨(dú)創(chuàng)建一個random.Random(seed)實(shí)例所有隨機(jī)調(diào)用都走這個實(shí)例不碰全局狀態(tài)。rng random.Random(seed) if rng.random() config.arrive_prob: duration rng.randint(*config.service_range)這樣即使外部代碼也在用隨機(jī)數(shù)你的仿真結(jié)果依然可復(fù)現(xiàn)。C 里對應(yīng)的是std::mt19937配std::uniform_real_distributionJava 里是new Random(seed)思路一致。這個細(xì)節(jié)在答辯時(shí)如果主動提出來是很加分的——說明你考慮過實(shí)驗(yàn)的可重復(fù)性而不是碰運(yùn)氣跑出一個好看的數(shù)字。4.2 邊界情況空隊(duì)列、零窗口、仿真結(jié)束殘留空隊(duì)列是常態(tài)窗口空閑但隊(duì)列為空時(shí)不能popleft否則拋異常。零窗口是非法配置輸入層要校驗(yàn)窗口數(shù)至少為 1。仿真結(jié)束殘留是容易被忽略的循環(huán)結(jié)束后隊(duì)列里可能還有客戶這些客戶的等待時(shí)間無法計(jì)算但數(shù)量要報(bào)告出來。還有一種邊界是同一時(shí)間片多個客戶到達(dá)。如果到達(dá)概率模型是每個時(shí)間片最多一個客戶就不會出現(xiàn)但如果改成泊松分布一個時(shí)間片可能到達(dá)多個。這時(shí)入隊(duì)順序要按到達(dá)順序不能亂。我的做法是到達(dá)事件生成一個列表按順序append到隊(duì)列保證 FIFO 語義不被破壞。4.3 輸出格式讓結(jié)果一眼能看懂輸出層不要只打印一堆數(shù)字。我一般會輸出三塊配置摘要窗口數(shù)、仿真時(shí)長、到達(dá)概率、服務(wù)時(shí)長范圍、核心指標(biāo)表總客戶、已服務(wù)、未服務(wù)、平均等待、最大等待、平均逗留、各窗口服務(wù)人數(shù)。如果有余力再加一個按時(shí)間段的等待時(shí)間分布比如每 60 個時(shí)間單位統(tǒng)計(jì)一次平均等待能看出高峰期和低谷期的差異。表格用 Markdown 或純文本對齊都行關(guān)鍵是列名清晰、單位明確。答辯時(shí)導(dǎo)師掃一眼就能抓到重點(diǎn)比讓他自己從日志里找數(shù)字強(qiáng)得多。5. 避坑與常見問題五條最容易翻車的地方5.1 現(xiàn)象平均等待時(shí)間出現(xiàn)負(fù)數(shù)或異常大值原因統(tǒng)計(jì)時(shí)沒有過濾start_time -1的未服務(wù)客戶-1 - arrive_time產(chǎn)生負(fù)數(shù)或者某個客戶的start_time被錯誤地設(shè)成了 0 而實(shí)際到達(dá)時(shí)刻很大。解決統(tǒng)計(jì)前強(qiáng)制過濾start_time 0并在仿真循環(huán)里確保start_time只在真正分配窗口時(shí)賦值不要在客戶創(chuàng)建時(shí)給默認(rèn)值 0。5.2 現(xiàn)象窗口利用率超過 100%原因分母算錯用了客戶數(shù) × 平均服務(wù)時(shí)長而不是窗口數(shù) × 仿真時(shí)長或者忙碌時(shí)間片重復(fù)累加同一個時(shí)間片被多個窗口記了多次。解決在仿真循環(huán)里按窗口逐個累加忙碌時(shí)間片每個時(shí)間片每個窗口最多記一次分母固定為window_count * total_time。5.3 現(xiàn)象每次運(yùn)行結(jié)果都不一樣無法復(fù)現(xiàn)原因使用了全局隨機(jī)狀態(tài)或者沒有固定種子或者種子被其他模塊干擾。解決仿真函數(shù)內(nèi)部創(chuàng)建獨(dú)立的Random(seed)實(shí)例種子作為參數(shù)傳入并記錄在輸出里保證任何人用同樣的種子和參數(shù)都能得到同樣的結(jié)果。5.4 現(xiàn)象VIP 客戶和普通客戶順序錯亂原因優(yōu)先隊(duì)列的優(yōu)先級只按等級排序同級客戶沒有按到達(dá)時(shí)間排序?qū)е潞蟮降耐?VIP 插隊(duì)。解決優(yōu)先級設(shè)計(jì)成元組(-level, arrive_time)等級高的在前同級按到達(dá)時(shí)間早的在前堆比較時(shí)自然保證穩(wěn)定性。5.5 現(xiàn)象仿真結(jié)束時(shí)大量客戶未服務(wù)指標(biāo)失真原因窗口數(shù)太少或仿真時(shí)長太短或者到達(dá)概率設(shè)得過高系統(tǒng)長期過載。解決這不是代碼 bug是參數(shù)問題。在輸出里明確報(bào)告未服務(wù)人數(shù)并在報(bào)告里討論參數(shù)敏感性——比如把窗口數(shù)從 2 加到 4觀察平均等待時(shí)間的變化這本身就是一份有分析深度的作業(yè)。6. 驗(yàn)收與答辯怎么把這份作業(yè)講成一個方案驗(yàn)收階段導(dǎo)師通常不會逐行看代碼而是問三個層次的問題結(jié)構(gòu)對不對、指標(biāo)怎么算、結(jié)論有沒有依據(jù)。對應(yīng)地答辯準(zhǔn)備也分三層。第一層是結(jié)構(gòu)演示。準(zhǔn)備一張模塊關(guān)系圖手畫或文檔里畫都行說清楚輸入、仿真、統(tǒng)計(jì)、輸出四層各自負(fù)責(zé)什么數(shù)據(jù)怎么流動。被問到為什么用隊(duì)列不用棧時(shí)答 FIFO 符合先到先服務(wù)語義棧是后進(jìn)先出會讓先來的客戶永遠(yuǎn)排不上這是業(yè)務(wù)語義決定的不是隨便選的。第二層是指標(biāo)追問。把四個核心指標(biāo)的公式寫在紙上能當(dāng)場推導(dǎo)。特別準(zhǔn)備好回答未服務(wù)客戶怎么處理和窗口利用率分母是什么這兩個高頻問題。如果做了 VIP 版本準(zhǔn)備好解釋優(yōu)先級的穩(wěn)定性設(shè)計(jì)。第三層是結(jié)論分析。這是拉開差距的地方。不要只報(bào)一個平均等待時(shí)間要給出參數(shù)對比。比如固定其他參數(shù)把窗口數(shù)從 2 增加到 3、4記錄平均等待時(shí)間的變化做成一張小表窗口數(shù)平均等待最大等待未服務(wù)人數(shù)218.6471236.221041.890這張表能直接支撐一個結(jié)論窗口數(shù)從 2 加到 3 收益最大從 3 加到 4 邊際收益遞減。這種分析不需要復(fù)雜代碼只需要把仿真跑幾遍、結(jié)果填進(jìn)表里但它讓作業(yè)從實(shí)現(xiàn)了隊(duì)列變成用隊(duì)列回答了一個問題。答辯時(shí)還有一個技巧主動說出你的假設(shè)和局限。比如本仿真假設(shè)服務(wù)時(shí)長均勻分布實(shí)際銀行可能更接近指數(shù)分布假設(shè)客戶不會中途離開實(shí)際可能存在放棄排隊(duì)的情況。主動暴露局限比被問出來強(qiáng)說明你知道邊界在哪。我自己的習(xí)慣是每次交這類仿真作業(yè)前都會用同一組參數(shù)連跑三次確認(rèn)結(jié)果完全一致再換兩組參數(shù)各跑一次確認(rèn)趨勢合理。這個三次復(fù)現(xiàn)加兩組對比的流程幫我擋掉過好幾次隨機(jī)種子沒固定、統(tǒng)計(jì)公式寫反的低級錯誤。從那以后我每次做仿真類作業(yè)都強(qiáng)制走一遍這個檢查希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取