據(jù)結(jié)構(gòu)實(shí)戰(zhàn)：用隊(duì)列模擬買(mǎi)房排隊(duì)全流程)
拿到“w11必做題1買(mǎi)房必做2隊(duì)列”這個(gè)題目描述時(shí)我的第一反應(yīng)是這標(biāo)題寫(xiě)得也太隨手了活像備忘錄里的一條待辦。但等你真正坐下來(lái)讀題會(huì)發(fā)現(xiàn)這恰好是數(shù)據(jù)結(jié)構(gòu)課程里最值得認(rèn)真做的一類(lèi)練習(xí)——它用“買(mǎi)房排隊(duì)”這個(gè)生活場(chǎng)景把隊(duì)列Queue這個(gè)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)考得明明白白。這篇文章我打算直接按“業(yè)務(wù)拆解 → 數(shù)據(jù)結(jié)構(gòu)選型 → 完整實(shí)現(xiàn) → 踩坑復(fù)盤(pán) → 工程擴(kuò)展”的順序來(lái)講。不管你是正在趕作業(yè)的學(xué)生還是想復(fù)習(xí)隊(duì)列應(yīng)用細(xì)節(jié)的開(kāi)發(fā)者都可以照著這份思路把代碼寫(xiě)出來(lái)并且能解釋清楚每個(gè)設(shè)計(jì)決策的理由。尤其是那些OJ上不報(bào)錯(cuò)、但代碼評(píng)審一眼就能看出來(lái)的問(wèn)題我會(huì)單獨(dú)拉一章來(lái)講。1. “買(mǎi)房”到底在考什么先讀懂業(yè)務(wù)再談代碼1.1 一個(gè)售樓處選房的完整業(yè)務(wù)過(guò)程題目叫“買(mǎi)房”但具體到代碼層面它到底想模擬什么我給你還原一個(gè)最常見(jiàn)的出題版本。假設(shè)售樓處有若干套房子分為幾種戶(hù)型。比如A戶(hù)型還剩2套B戶(hù)型還剩1套C戶(hù)型已經(jīng)售罄。然后有若干個(gè)客戶(hù)按照到達(dá)順序一個(gè)接一個(gè)地進(jìn)入選房區(qū)。每位客戶(hù)身上帶著三個(gè)關(guān)鍵屬性姓名、心理預(yù)算、偏好的戶(hù)型。流程是客戶(hù)走到前臺(tái)說(shuō)出自己想要的戶(hù)型如果這個(gè)戶(hù)型還有余量并且客戶(hù)預(yù)算足夠那么成交該戶(hù)型余量減一如果目標(biāo)戶(hù)型已經(jīng)售罄或者預(yù)算不夠客戶(hù)可以選擇放棄也可以考慮備選戶(hù)型具體看題目規(guī)則不管成交還是放棄這個(gè)客戶(hù)處理完之后下一位客戶(hù)才能上來(lái)。最后程序要輸出什么一般是兩類(lèi)結(jié)果一類(lèi)是每套房子的成交情況另一類(lèi)是每個(gè)客戶(hù)最終買(mǎi)到了什么、等待了多長(zhǎng)時(shí)間。有些版本還要求統(tǒng)計(jì)成交率、平均等待時(shí)長(zhǎng)。注意這里最核心的約束是“按照到達(dá)順序一個(gè)接一個(gè)”。這就是一個(gè)標(biāo)準(zhǔn)的先進(jìn)先出過(guò)程。你不需要把客戶(hù)按預(yù)算排序也不需要按姓氏排序甚至不能因?yàn)槟硞€(gè)客戶(hù)出價(jià)高就讓他插隊(duì)。先來(lái)后到就是唯一的規(guī)則。1.2 為什么這題的核心不是“排序”而是“排隊(duì)”很多同學(xué)看到“買(mǎi)房”兩個(gè)字第一反應(yīng)是這不就是個(gè)排序題嗎把客戶(hù)按預(yù)算從高到低排把房子從貴到便宜排然后逐個(gè)匹配。這一步其實(shí)已經(jīng)掉進(jìn)陷阱了。如果題目沒(méi)有明確說(shuō)“出價(jià)高者優(yōu)先”那買(mǎi)房就是先到先得。兩個(gè)客戶(hù)同時(shí)看中同一套房先到的客戶(hù)預(yù)算不足后到的客戶(hù)預(yù)算反而夠了你能讓后到的客戶(hù)直接買(mǎi)走嗎真實(shí)業(yè)務(wù)里不可以因?yàn)榭蛻?hù)是按順序接待的。也就是說(shuō)順序是絕對(duì)剛性的預(yù)算只能決定這個(gè)客戶(hù)買(mǎi)不買(mǎi)得起不能決定他排在哪。那用數(shù)組模擬行不行當(dāng)然行但不優(yōu)雅。如果你用一個(gè)數(shù)組存放所有客戶(hù)然后每次從頭處理處理完一個(gè)就把后面的元素整體前移每次刪除的時(shí)間復(fù)雜度是 O(n)處理 n 個(gè)客戶(hù)就是 O(n2)。數(shù)據(jù)量小還能忍數(shù)據(jù)量一大就明顯超時(shí)。隊(duì)列的好處是入隊(duì)和出隊(duì)都是 O(1)整個(gè)流程跑下來(lái)是 O(n)這才符合“模擬業(yè)務(wù)過(guò)程”的本意。我習(xí)慣用一個(gè)簡(jiǎn)單的對(duì)比來(lái)看待這類(lèi)問(wèn)題數(shù)組適合“隨機(jī)訪問(wèn)”棧適合“后到先處理”隊(duì)列適合“先到先處理”。買(mǎi)房選房這個(gè)場(chǎng)景天然就和隊(duì)列綁定。所以這道題真正考的是你能不能把一個(gè)業(yè)務(wù)過(guò)程翻譯成數(shù)據(jù)結(jié)構(gòu)操作。2. 隊(duì)列實(shí)現(xiàn)選型鏈?zhǔn)疥?duì)列和循環(huán)數(shù)組隊(duì)列怎么選2.1 兩種存儲(chǔ)結(jié)構(gòu)的核心差異確定了要用隊(duì)列緊接著就面臨選型問(wèn)題。數(shù)據(jù)結(jié)構(gòu)課本里教過(guò)兩種隊(duì)列實(shí)現(xiàn)方式鏈?zhǔn)疥?duì)列和循環(huán)數(shù)組隊(duì)列。課堂上兩種都要求會(huì)寫(xiě)但實(shí)際做題時(shí)選哪個(gè)取決于輸入規(guī)模。鏈?zhǔn)疥?duì)列的優(yōu)點(diǎn)是容量可以動(dòng)態(tài)增長(zhǎng)不需要事先知道客戶(hù)總數(shù)。缺點(diǎn)也很明顯每個(gè)節(jié)點(diǎn)需要額外存一個(gè)指針字段內(nèi)存開(kāi)銷(xiāo)略大操作時(shí)還要小心指針指錯(cuò)。循環(huán)數(shù)組隊(duì)列的優(yōu)點(diǎn)是內(nèi)存緊湊、操作簡(jiǎn)單性能通常會(huì)比鏈?zhǔn)铰院靡稽c(diǎn)。但它要求你提前知道最大容量。如果題目給了明確的人數(shù)上限比如“客戶(hù)總數(shù)不超過(guò)10000”那用循環(huán)數(shù)組非常省心。我通常這樣判斷如果輸入第一行給了總?cè)藬?shù) n或者題目說(shuō)明了規(guī)模上限我優(yōu)先用循環(huán)數(shù)組隊(duì)列如果題目是一個(gè)流式的輸入不知道什么時(shí)候結(jié)束我就用鏈?zhǔn)疥?duì)列。下面是一個(gè)簡(jiǎn)單的對(duì)比表方便你快速?zèng)Q策維度鏈?zhǔn)疥?duì)列循環(huán)數(shù)組隊(duì)列容量動(dòng)態(tài)增長(zhǎng)需要預(yù)知上限內(nèi)存開(kāi)銷(xiāo)每個(gè)節(jié)點(diǎn)多一個(gè)指針固定數(shù)組略省內(nèi)存入隊(duì)/出隊(duì)復(fù)雜度O(1)O(1)實(shí)現(xiàn)難度中等需處理指針較低但要注意滿(mǎn)/空判斷適用場(chǎng)景未知輸入量、頻繁增刪已知規(guī)模、OJ時(shí)間要求嚴(yán)格2.2 一個(gè)最小可用的隊(duì)列接口設(shè)計(jì)無(wú)論你選哪種實(shí)現(xiàn)方式我都強(qiáng)烈建議按照“接口思維”來(lái)寫(xiě)隊(duì)列不要讓業(yè)務(wù)代碼直接操作隊(duì)列的內(nèi)部節(jié)點(diǎn)。這也是這道題隱藏的加分點(diǎn)代碼結(jié)構(gòu)清晰。以鏈?zhǔn)疥?duì)列為例我會(huì)把業(yè)務(wù)字段和隊(duì)列節(jié)點(diǎn)分開(kāi)設(shè)計(jì)。一個(gè)客戶(hù)節(jié)點(diǎn)可以這樣定義typedef struct Customer { char name[32]; int budget; // 心理預(yù)算 int prefer; // 偏好戶(hù)型編號(hào) int arrive_time; // 到達(dá)時(shí)間用于統(tǒng)計(jì)等待時(shí)長(zhǎng) } Customer; typedef struct QNode { Customer data; struct QNode *next; } QNode; typedef struct Queue { QNode *front; QNode *rear; int size; } Queue;這里把業(yè)務(wù)數(shù)據(jù)和隊(duì)列指針?lè)蛛x開(kāi)好處是日后如果要改隊(duì)列的數(shù)據(jù)類(lèi)型不用動(dòng)主邏輯。然后實(shí)現(xiàn)四個(gè)最基本的方法初始化、判空、入隊(duì)、出隊(duì)、取隊(duì)頭。注意一個(gè)細(xì)節(jié)取隊(duì)頭是讀但不刪除出隊(duì)是刪除但不返回?cái)?shù)據(jù)。這樣拆分是為了避免你在出隊(duì)時(shí)還要考慮要不要釋放內(nèi)存的問(wèn)題。void initQueue(Queue *q) { q-front q-rear NULL; q-size 0; } int isEmpty(Queue *q) { return q-size 0; } void enQueue(Queue *q, Customer c) { QNode *node (QNode *)malloc(sizeof(QNode)); node-data c; node-next NULL; if (q-rear NULL) { q-front q-rear node; } else { q-rear-next node; q-rear node; } q-size; } Customer getFront(Queue *q) { return q-front-data; } Customer deQueue(Queue *q) { Customer c q-front-data; QNode *tmp q-front; q-front q-front-next; if (q-front NULL) { q-rear NULL; } free(tmp); q-size--; return c; }這段代碼里的關(guān)鍵點(diǎn)有兩個(gè)。第一出隊(duì)的時(shí)候必須特判“出隊(duì)后隊(duì)列變空”的情況把 rear 也置為 NULL否則后面再入隊(duì)時(shí) rear 還指向一個(gè)已經(jīng)釋放的節(jié)點(diǎn)就會(huì)出現(xiàn)野指針。第二如果你實(shí)際上不需要出隊(duì)后返回的數(shù)據(jù)可以直接調(diào)用 getFront 拿到隊(duì)頭再調(diào)用 deQueue 刪除業(yè)務(wù)邏輯會(huì)更清晰。3. 買(mǎi)房主流程實(shí)現(xiàn)入隊(duì)、出隊(duì)、成交判斷的分工與合作3.1 輸入階段與主循環(huán)的整體結(jié)構(gòu)隊(duì)列寫(xiě)完之后接下來(lái)就是業(yè)務(wù)主流程。這個(gè)主流程本身并不復(fù)雜核心就是一句話把所有客戶(hù)按順序入隊(duì)然后循環(huán)處理隊(duì)頭客戶(hù)直到隊(duì)列為空。我先把整體骨架羅列出來(lái)int main() { Queue q; initQueue(q); int n; scanf(%d, n); for (int i 0; i n; i) { Customer c; scanf(%s %d %d %d, c.name, c.budget, c.prefer, c.arrive_time); enQueue(q, c); } while (!isEmpty(q)) { Customer c getFront(q); // 1. 判斷客戶(hù)是否買(mǎi)得起、目標(biāo)戶(hù)型是否有余量 // 2. 成交或放棄 // 3. 記錄結(jié)果 deQueue(q); } // 輸出結(jié)果 }為什么不寫(xiě)成一邊出隊(duì)一邊判斷也就是直接調(diào)用 deQueue 拿到客戶(hù)數(shù)據(jù)再判斷因?yàn)榭赡艹鲫?duì)之后你才發(fā)現(xiàn)這個(gè)客戶(hù)還需要和其他狀態(tài)項(xiàng)比如備選方案交互如果一開(kāi)始就把數(shù)據(jù)取走隊(duì)列的完整性就沒(méi)有意義了。保持“先查看隊(duì)頭再?zèng)Q定是否出隊(duì)”的順序可以讓邏輯更接近真實(shí)業(yè)務(wù)。3.2 分支條件的判斷次序很重要我給一個(gè)最簡(jiǎn)單的版本每個(gè)客戶(hù)只有一個(gè)目標(biāo)戶(hù)型如果目標(biāo)戶(hù)型售罄或預(yù)算不足客戶(hù)直接離開(kāi)。while (!isEmpty(q)) { Customer c getFront(q); if (house_count[c.prefer] 0 c.budget house_price[c.prefer]) { house_count[c.prefer]--; printf(%s bought house %d\n, c.name, c.prefer); } else { printf(%s left\n, c.name); } deQueue(q); }這段代碼看著沒(méi)有問(wèn)題但如果你把兩個(gè)判斷條件反過(guò)來(lái)寫(xiě)就會(huì)出現(xiàn)邏輯錯(cuò)誤。比如你先判斷預(yù)算夠不夠再判斷房源余量那么“預(yù)算夠但沒(méi)有房”和“預(yù)算不夠但有房”會(huì)被混為一類(lèi)輸出信息不夠準(zhǔn)確。更隱蔽的問(wèn)題是如果題目要求“目標(biāo)戶(hù)型售罄時(shí)可以買(mǎi)備選戶(hù)型”判斷次序就更加關(guān)鍵必須先用目標(biāo)戶(hù)型嘗試失敗后再用備選戶(hù)型而不是一上來(lái)就檢查備選。我給出一個(gè)帶備選戶(hù)型版本的判斷順序先看目標(biāo)戶(hù)型是否有余量且預(yù)算足夠滿(mǎn)足則成交否則看備選戶(hù)型是否有余量且預(yù)算足夠滿(mǎn)足則買(mǎi)備選兩個(gè)都不滿(mǎn)足客戶(hù)離開(kāi)。這個(gè)順序是嚴(yán)格按照現(xiàn)實(shí)業(yè)務(wù)邏輯來(lái)的客戶(hù)優(yōu)先選擇自己最喜歡的戶(hù)型買(mǎi)不到才會(huì)退而求其次。3.3 統(tǒng)計(jì)指標(biāo)等待時(shí)間與成交數(shù)據(jù)的處理不少題目要求輸出平均等待時(shí)間或者判斷“誰(shuí)的等待時(shí)間最長(zhǎng)”。這時(shí)候你就要在客戶(hù)節(jié)點(diǎn)里記錄到達(dá)時(shí)間然后在輪到他處理時(shí)計(jì)算等待時(shí)間。int wait_time current_time - c.arrive_time;這里有幾個(gè)細(xì)節(jié)很容易出錯(cuò)。第一current_time 是什么如果題目描述的是“每個(gè)客戶(hù)處理需要固定時(shí)間”那 current_time 就是從頭開(kāi)始累計(jì)的處理時(shí)間如果題目描述的是“當(dāng)前時(shí)刻”那 current_time 可能已經(jīng)給定。一定要仔細(xì)讀題。第二如果用 int 統(tǒng)計(jì)總等待時(shí)間客戶(hù)數(shù)量超過(guò)一定規(guī)模時(shí)會(huì)溢出。雖然業(yè)務(wù)上單個(gè)人等待時(shí)間不會(huì)很長(zhǎng)但總和可能很大。習(xí)慣上用 long 來(lái)存累計(jì)等待時(shí)間更穩(wěn)妥。第三如果你需要知道“最后買(mǎi)走某套房子的客戶(hù)是誰(shuí)”建議在房源結(jié)構(gòu)里維護(hù)一個(gè)買(mǎi)家字段而不是等到最后再回頭查。4. 實(shí)測(cè)踩坑復(fù)盤(pán)這題最容易扣分的四個(gè)細(xì)節(jié)4.1 坑一把“先來(lái)后到”實(shí)現(xiàn)成“排序后處理”這個(gè)坑我見(jiàn)過(guò)太多次。題目剛發(fā)下來(lái)有同學(xué)一看“買(mǎi)房”立刻聯(lián)想到貪心算法把客戶(hù)按預(yù)算從高到低排序優(yōu)先處理出價(jià)高的人。這種方案在某些“拍賣(mài)型”題目里是對(duì)的但在這道“排隊(duì)型”題目里直接掛掉。原因很簡(jiǎn)單業(yè)務(wù)規(guī)則決定順序算法不能擅自改變順序。如果題目明確說(shuō)“客戶(hù)按到達(dá)順序依次選房”那到達(dá)順序就是一條不可違反的鐵律。你在設(shè)計(jì)算法時(shí)第一步應(yīng)該是找“順序約束”而不是找“最優(yōu)策略”。怎么檢查你有沒(méi)有踩這個(gè)坑把輸入數(shù)據(jù)打亂順序再跑一遍如果結(jié)果變了說(shuō)明你的算法依賴(lài)輸入順序之外的某種排序規(guī)則那就要警惕了。4.2 坑二鏈?zhǔn)疥?duì)列出隊(duì)后沒(méi)有釋放舊節(jié)點(diǎn)這屬于典型的內(nèi)存管理問(wèn)題。OJ上跑的話通常不會(huì)爆出內(nèi)存泄漏的報(bào)錯(cuò)最多就是內(nèi)存占用偏高。但如果是人工代碼評(píng)審這一步基本要被扣分。錯(cuò)誤寫(xiě)法通常是這樣的Customer deQueue(Queue *q) { QNode *tmp q-front; q-front q-front-next; return tmp-data; // 忘了 free(tmp) }每次出隊(duì)少 free 一次跑一萬(wàn)個(gè)客戶(hù)就泄漏一萬(wàn)個(gè)節(jié)點(diǎn)。更麻煩的是如果出隊(duì)的是最后一個(gè)節(jié)點(diǎn)你還要把 rear 置為 NULL否則后續(xù)入隊(duì)會(huì)訪問(wèn)到原本已經(jīng)釋放的內(nèi)存。這兩個(gè)問(wèn)題經(jīng)常同時(shí)出現(xiàn)。我建議你寫(xiě)完隊(duì)列之后專(zhuān)門(mén)寫(xiě)一個(gè)“只有三個(gè)客戶(hù)”的小測(cè)試逐一入隊(duì)再逐一出隊(duì)配合內(nèi)存檢測(cè)工具檢查是否有泄漏。這一步花費(fèi)的時(shí)間很少但能避免很多隱性扣分。4.3 坑三循環(huán)數(shù)組隊(duì)列的“滿(mǎn)”和“空”判斷搞反如果你選用循環(huán)數(shù)組隊(duì)列最常見(jiàn)的問(wèn)題就是“隊(duì)滿(mǎn)”和“隊(duì)空”的判斷條件互相混淆。經(jīng)典的實(shí)現(xiàn)方式是讓數(shù)組保留一個(gè)空位用 front 和 rear 的相對(duì)位置來(lái)判斷隊(duì)列空f(shuō)ront rear隊(duì)列滿(mǎn)(rear 1) % capacity front很多同學(xué)會(huì)把隊(duì)滿(mǎn)條件寫(xiě)成 front rear導(dǎo)致一個(gè)滿(mǎn)隊(duì)列被誤判為空然后死循環(huán)。還有同學(xué)在入隊(duì)時(shí)沒(méi)有正確處理取模操作比如q-rear q-rear 1; // 錯(cuò)誤沒(méi)有取模 q-data[q-rear] c;這條代碼在連續(xù)入隊(duì)幾次之后rear 會(huì)直接越界訪問(wèn)數(shù)組尾部。正確寫(xiě)法是q-rear (q-rear 1) % capacity; q-data[q-rear] c;取模這件事特別容易在“看起來(lái)沒(méi)報(bào)錯(cuò)”的狀態(tài)下出錯(cuò)因?yàn)閿?shù)組越界訪問(wèn)不一定立刻崩潰可能只是偷偷覆蓋了相鄰內(nèi)存等到輸出統(tǒng)計(jì)結(jié)果時(shí)才變得莫名其妙。4.4 坑四判斷次序?qū)懛磳?dǎo)致已售罄戶(hù)型被再次賣(mài)出這個(gè)坑往往出現(xiàn)在稍微復(fù)雜的題目版本里。比如客戶(hù)可以先判斷“預(yù)算夠不夠”再判斷“有沒(méi)有房”。如果預(yù)算不夠程序可能直接輸出離開(kāi)但忽略了房源已經(jīng)被前面的人全部買(mǎi)完此時(shí)應(yīng)該輸出“售罄”而不是“預(yù)算不足”。反過(guò)來(lái)如果先判斷“有沒(méi)有房”再判斷“預(yù)算夠不夠”那么在房源還有、但預(yù)算不夠的情況下應(yīng)該繼續(xù)嘗試備選戶(hù)型而不是直接放棄。換句話說(shuō)判斷分支的先后順序直接決定了業(yè)務(wù)邏輯是否自洽。我的建議是把所有可能的判斷條件列出來(lái)模擬一個(gè)客戶(hù)走完全部流程再?zèng)Q定代碼順序。你可以在代碼里加一條注釋把判斷順序?qū)懗鰜?lái)// 1. 目標(biāo)戶(hù)型是否售罄 // 2. 預(yù)算是否足夠 // 3. 備選戶(hù)型是否售罄 // 4. 備選戶(hù)型是否買(mǎi)得起這看起來(lái)是小事但在寫(xiě)復(fù)雜版本時(shí)這一步能幫你減少無(wú)數(shù)調(diào)試時(shí)間。4.5 如何用邊界測(cè)試驗(yàn)證正確性作業(yè)提交之前我強(qiáng)烈建議你構(gòu)造幾組邊界測(cè)試用例不要只拿題目給的示例跑一遍就完事。下面是我常用的幾組用例類(lèi)型輸入特征期望結(jié)果空輸入客戶(hù)總量 n 0不報(bào)錯(cuò)輸出為空單個(gè)客戶(hù)只有一位客戶(hù)房源充足該客戶(hù)正常成交房源歸零所有戶(hù)型數(shù)量都是 0所有客戶(hù)離開(kāi)預(yù)算不足客戶(hù)預(yù)算低于任何戶(hù)型價(jià)格客戶(hù)全部離開(kāi)順序競(jìng)爭(zhēng)兩客戶(hù)搶同一戶(hù)型先到的預(yù)算不足先到的放棄后到的成交不能交換順序備選邏輯首選戶(hù)型售罄備選有余量客戶(hù)買(mǎi)備選戶(hù)型這些測(cè)試用例構(gòu)造起來(lái)很快但價(jià)值很高。很多隱藏邏輯錯(cuò)誤比如“判斷次序?qū)懛础薄绊樞虮慌判蚱茐摹痹诔Ｒ?guī)測(cè)試?yán)锟床怀鰜?lái)邊界測(cè)試一跑就現(xiàn)出原形。5. 從課堂作業(yè)到工程實(shí)踐隊(duì)列的三種進(jìn)階變形5.1 優(yōu)先隊(duì)列當(dāng)VIP客戶(hù)可以插隊(duì)時(shí)“買(mǎi)房排隊(duì)”這個(gè)場(chǎng)景在真實(shí)世界中往往不是絕對(duì)公平的。有的題目會(huì)加一條規(guī)則VIP客戶(hù)可以?xún)?yōu)先進(jìn)場(chǎng)。這時(shí)候你再用普通隊(duì)列就不合適了。優(yōu)先隊(duì)列和非優(yōu)先隊(duì)列的區(qū)別在于出隊(duì)的不一定是入隊(duì)最早的而是優(yōu)先級(jí)最高的。在C語(yǔ)言里你可以用堆Heap來(lái)實(shí)現(xiàn)在C里可以直接用 priority_queue。這個(gè)數(shù)據(jù)結(jié)構(gòu)在算法題里非常常見(jiàn)核心思路是在入隊(duì)時(shí)就把順序優(yōu)先級(jí)排好出隊(duì)時(shí)直接取堆頂。如果你做完這道“買(mǎi)房隊(duì)列”的必做題我建議你順手把同樣場(chǎng)景改成“VIP優(yōu)先”再寫(xiě)一遍。你會(huì)發(fā)現(xiàn)業(yè)務(wù)規(guī)則一變數(shù)據(jù)結(jié)構(gòu)選擇也跟著變這才是真正的能力考察點(diǎn)。5.2 雙端隊(duì)列當(dāng)客戶(hù)可能反悔時(shí)有些模擬場(chǎng)景中客戶(hù)可能會(huì)“撤銷(xiāo)剛才的選房”或者新來(lái)的客戶(hù)需要排到最前面。這時(shí)雙端隊(duì)列 deque 就派上用場(chǎng)了它允許你在隊(duì)頭和隊(duì)尾兩端都能入隊(duì)、出隊(duì)。在“買(mǎi)房”這個(gè)業(yè)務(wù)里怎么用比如客戶(hù)選完房后突然決定反悔退房出來(lái)后重新排隊(duì)到末尾這個(gè)過(guò)程需要從隊(duì)尾入隊(duì)而如果題目有“老客戶(hù)優(yōu)先”的規(guī)則那就可能需要從隊(duì)頭插入。雙端隊(duì)列能同時(shí)覆蓋這兩種需求抽象能力比普通隊(duì)列強(qiáng)很多。5.3 隊(duì)列在真實(shí)系統(tǒng)中的同構(gòu)應(yīng)用學(xué)完這道作業(yè)題你會(huì)發(fā)現(xiàn)隊(duì)列的應(yīng)用范圍遠(yuǎn)比“模擬排隊(duì)”廣泛。舉幾個(gè)例子消息隊(duì)列生產(chǎn)者把消息入隊(duì)消費(fèi)者按順序出隊(duì)保證消息不丟失、不重復(fù)任務(wù)調(diào)度操作系統(tǒng)中的就緒隊(duì)列CPU按時(shí)間片輪轉(zhuǎn)處理任務(wù)網(wǎng)絡(luò)請(qǐng)求服務(wù)器接收大量并發(fā)請(qǐng)求往往先放入請(qǐng)求隊(duì)列再逐個(gè)處理打印任務(wù)多個(gè)文檔發(fā)送到打印機(jī)打印機(jī)按提交順序逐個(gè)打印。這些場(chǎng)景的共同點(diǎn)都是“先來(lái)先服務(wù)”和買(mǎi)房排隊(duì)本質(zhì)上是同構(gòu)的。你在未來(lái)工作中很可能遇到比這道題大得多的數(shù)據(jù)量但抽象思路完全一樣。最后再分享一個(gè)實(shí)際經(jīng)驗(yàn)。在寫(xiě)這類(lèi)“場(chǎng)景模擬”題目時(shí)我建議你養(yǎng)成一個(gè)習(xí)慣在每一步關(guān)鍵操作前后打印日志比如“XX入隊(duì)當(dāng)前隊(duì)頭是XX”然后拿著日志模擬一遍整個(gè)買(mǎi)房流程。這個(gè)方法看起來(lái)原始但排查邏輯錯(cuò)誤極其高效。很多時(shí)候你以為自己的隊(duì)列出了問(wèn)題其實(shí)只是判斷分支寫(xiě)錯(cuò)了順序。這道作業(yè)題的價(jià)值并不在于讓你背下隊(duì)列的八個(gè)方法而是在于訓(xùn)練一種能力——把現(xiàn)實(shí)世界里復(fù)雜、動(dòng)態(tài)、多約束的業(yè)務(wù)過(guò)程翻譯成一個(gè)只有入隊(duì)、出隊(duì)、取隊(duì)頭三種操作的簡(jiǎn)潔模型。能順利完成這種翻譯數(shù)據(jù)結(jié)構(gòu)這門(mén)課的核心目標(biāo)也就達(dá)到了。 數(shù)據(jù)結(jié)構(gòu)實(shí)戰(zhàn)：用隊(duì)列模擬買(mǎi)房排隊(duì)全流程
拿到“w11必做題1買(mǎi)房必做2隊(duì)列”這個(gè)題目描述時(shí)我的第一反應(yīng)是這標(biāo)題寫(xiě)得也太隨手了活像備忘錄里的一條待辦。但等你真正坐下來(lái)讀題會(huì)發(fā)現(xiàn)這恰好是數(shù)據(jù)結(jié)構(gòu)課程里最值得認(rèn)真做的一類(lèi)練習(xí)——它用“買(mǎi)房排隊(duì)”這個(gè)生活場(chǎng)景把隊(duì)列Queue這個(gè)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)考得明明白白。這篇文章我打算直接按“業(yè)務(wù)拆解 → 數(shù)據(jù)結(jié)構(gòu)選型 → 完整實(shí)現(xiàn) → 踩坑復(fù)盤(pán) → 工程擴(kuò)展”的順序來(lái)講。不管你是正在趕作業(yè)的學(xué)生還是想復(fù)習(xí)隊(duì)列應(yīng)用細(xì)節(jié)的開(kāi)發(fā)者都可以照著這份思路把代碼寫(xiě)出來(lái)并且能解釋清楚每個(gè)設(shè)計(jì)決策的理由。尤其是那些OJ上不報(bào)錯(cuò)、但代碼評(píng)審一眼就能看出來(lái)的問(wèn)題我會(huì)單獨(dú)拉一章來(lái)講。1. “買(mǎi)房”到底在考什么先讀懂業(yè)務(wù)再談代碼1.1 一個(gè)售樓處選房的完整業(yè)務(wù)過(guò)程題目叫“買(mǎi)房”但具體到代碼層面它到底想模擬什么我給你還原一個(gè)最常見(jiàn)的出題版本。假設(shè)售樓處有若干套房子分為幾種戶(hù)型。比如A戶(hù)型還剩2套B戶(hù)型還剩1套C戶(hù)型已經(jīng)售罄。然后有若干個(gè)客戶(hù)按照到達(dá)順序一個(gè)接一個(gè)地進(jìn)入選房區(qū)。每位客戶(hù)身上帶著三個(gè)關(guān)鍵屬性姓名、心理預(yù)算、偏好的戶(hù)型。流程是客戶(hù)走到前臺(tái)說(shuō)出自己想要的戶(hù)型如果這個(gè)戶(hù)型還有余量并且客戶(hù)預(yù)算足夠那么成交該戶(hù)型余量減一如果目標(biāo)戶(hù)型已經(jīng)售罄或者預(yù)算不夠客戶(hù)可以選擇放棄也可以考慮備選戶(hù)型具體看題目規(guī)則不管成交還是放棄這個(gè)客戶(hù)處理完之后下一位客戶(hù)才能上來(lái)。最后程序要輸出什么一般是兩類(lèi)結(jié)果一類(lèi)是每套房子的成交情況另一類(lèi)是每個(gè)客戶(hù)最終買(mǎi)到了什么、等待了多長(zhǎng)時(shí)間。有些版本還要求統(tǒng)計(jì)成交率、平均等待時(shí)長(zhǎng)。注意這里最核心的約束是“按照到達(dá)順序一個(gè)接一個(gè)”。這就是一個(gè)標(biāo)準(zhǔn)的先進(jìn)先出過(guò)程。你不需要把客戶(hù)按預(yù)算排序也不需要按姓氏排序甚至不能因?yàn)槟硞€(gè)客戶(hù)出價(jià)高就讓他插隊(duì)。先來(lái)后到就是唯一的規(guī)則。1.2 為什么這題的核心不是“排序”而是“排隊(duì)”很多同學(xué)看到“買(mǎi)房”兩個(gè)字第一反應(yīng)是這不就是個(gè)排序題嗎把客戶(hù)按預(yù)算從高到低排把房子從貴到便宜排然后逐個(gè)匹配。這一步其實(shí)已經(jīng)掉進(jìn)陷阱了。如果題目沒(méi)有明確說(shuō)“出價(jià)高者優(yōu)先”那買(mǎi)房就是先到先得。兩個(gè)客戶(hù)同時(shí)看中同一套房先到的客戶(hù)預(yù)算不足后到的客戶(hù)預(yù)算反而夠了你能讓后到的客戶(hù)直接買(mǎi)走嗎真實(shí)業(yè)務(wù)里不可以因?yàn)榭蛻?hù)是按順序接待的。也就是說(shuō)順序是絕對(duì)剛性的預(yù)算只能決定這個(gè)客戶(hù)買(mǎi)不買(mǎi)得起不能決定他排在哪。那用數(shù)組模擬行不行當(dāng)然行但不優(yōu)雅。如果你用一個(gè)數(shù)組存放所有客戶(hù)然后每次從頭處理處理完一個(gè)就把后面的元素整體前移每次刪除的時(shí)間復(fù)雜度是 O(n)處理 n 個(gè)客戶(hù)就是 O(n2)。數(shù)據(jù)量小還能忍數(shù)據(jù)量一大就明顯超時(shí)。隊(duì)列的好處是入隊(duì)和出隊(duì)都是 O(1)整個(gè)流程跑下來(lái)是 O(n)這才符合“模擬業(yè)務(wù)過(guò)程”的本意。我習(xí)慣用一個(gè)簡(jiǎn)單的對(duì)比來(lái)看待這類(lèi)問(wèn)題數(shù)組適合“隨機(jī)訪問(wèn)”棧適合“后到先處理”隊(duì)列適合“先到先處理”。買(mǎi)房選房這個(gè)場(chǎng)景天然就和隊(duì)列綁定。所以這道題真正考的是你能不能把一個(gè)業(yè)務(wù)過(guò)程翻譯成數(shù)據(jù)結(jié)構(gòu)操作。2. 隊(duì)列實(shí)現(xiàn)選型鏈?zhǔn)疥?duì)列和循環(huán)數(shù)組隊(duì)列怎么選2.1 兩種存儲(chǔ)結(jié)構(gòu)的核心差異確定了要用隊(duì)列緊接著就面臨選型問(wèn)題。數(shù)據(jù)結(jié)構(gòu)課本里教過(guò)兩種隊(duì)列實(shí)現(xiàn)方式鏈?zhǔn)疥?duì)列和循環(huán)數(shù)組隊(duì)列。課堂上兩種都要求會(huì)寫(xiě)但實(shí)際做題時(shí)選哪個(gè)取決于輸入規(guī)模。鏈?zhǔn)疥?duì)列的優(yōu)點(diǎn)是容量可以動(dòng)態(tài)增長(zhǎng)不需要事先知道客戶(hù)總數(shù)。缺點(diǎn)也很明顯每個(gè)節(jié)點(diǎn)需要額外存一個(gè)指針字段內(nèi)存開(kāi)銷(xiāo)略大操作時(shí)還要小心指針指錯(cuò)。循環(huán)數(shù)組隊(duì)列的優(yōu)點(diǎn)是內(nèi)存緊湊、操作簡(jiǎn)單性能通常會(huì)比鏈?zhǔn)铰院靡稽c(diǎn)。但它要求你提前知道最大容量。如果題目給了明確的人數(shù)上限比如“客戶(hù)總數(shù)不超過(guò)10000”那用循環(huán)數(shù)組非常省心。我通常這樣判斷如果輸入第一行給了總?cè)藬?shù) n或者題目說(shuō)明了規(guī)模上限我優(yōu)先用循環(huán)數(shù)組隊(duì)列如果題目是一個(gè)流式的輸入不知道什么時(shí)候結(jié)束我就用鏈?zhǔn)疥?duì)列。下面是一個(gè)簡(jiǎn)單的對(duì)比表方便你快速?zèng)Q策維度鏈?zhǔn)疥?duì)列循環(huán)數(shù)組隊(duì)列容量動(dòng)態(tài)增長(zhǎng)需要預(yù)知上限內(nèi)存開(kāi)銷(xiāo)每個(gè)節(jié)點(diǎn)多一個(gè)指針固定數(shù)組略省內(nèi)存入隊(duì)/出隊(duì)復(fù)雜度O(1)O(1)實(shí)現(xiàn)難度中等需處理指針較低但要注意滿(mǎn)/空判斷適用場(chǎng)景未知輸入量、頻繁增刪已知規(guī)模、OJ時(shí)間要求嚴(yán)格2.2 一個(gè)最小可用的隊(duì)列接口設(shè)計(jì)無(wú)論你選哪種實(shí)現(xiàn)方式我都強(qiáng)烈建議按照“接口思維”來(lái)寫(xiě)隊(duì)列不要讓業(yè)務(wù)代碼直接操作隊(duì)列的內(nèi)部節(jié)點(diǎn)。這也是這道題隱藏的加分點(diǎn)代碼結(jié)構(gòu)清晰。以鏈?zhǔn)疥?duì)列為例我會(huì)把業(yè)務(wù)字段和隊(duì)列節(jié)點(diǎn)分開(kāi)設(shè)計(jì)。一個(gè)客戶(hù)節(jié)點(diǎn)可以這樣定義typedef struct Customer { char name[32]; int budget; // 心理預(yù)算 int prefer; // 偏好戶(hù)型編號(hào) int arrive_time; // 到達(dá)時(shí)間用于統(tǒng)計(jì)等待時(shí)長(zhǎng) } Customer; typedef struct QNode { Customer data; struct QNode *next; } QNode; typedef struct Queue { QNode *front; QNode *rear; int size; } Queue;這里把業(yè)務(wù)數(shù)據(jù)和隊(duì)列指針?lè)蛛x開(kāi)好處是日后如果要改隊(duì)列的數(shù)據(jù)類(lèi)型不用動(dòng)主邏輯。然后實(shí)現(xiàn)四個(gè)最基本的方法初始化、判空、入隊(duì)、出隊(duì)、取隊(duì)頭。注意一個(gè)細(xì)節(jié)取隊(duì)頭是讀但不刪除出隊(duì)是刪除但不返回?cái)?shù)據(jù)。這樣拆分是為了避免你在出隊(duì)時(shí)還要考慮要不要釋放內(nèi)存的問(wèn)題。void initQueue(Queue *q) { q-front q-rear NULL; q-size 0; } int isEmpty(Queue *q) { return q-size 0; } void enQueue(Queue *q, Customer c) { QNode *node (QNode *)malloc(sizeof(QNode)); node-data c; node-next NULL; if (q-rear NULL) { q-front q-rear node; } else { q-rear-next node; q-rear node; } q-size; } Customer getFront(Queue *q) { return q-front-data; } Customer deQueue(Queue *q) { Customer c q-front-data; QNode *tmp q-front; q-front q-front-next; if (q-front NULL) { q-rear NULL; } free(tmp); q-size--; return c; }這段代碼里的關(guān)鍵點(diǎn)有兩個(gè)。第一出隊(duì)的時(shí)候必須特判“出隊(duì)后隊(duì)列變空”的情況把 rear 也置為 NULL否則后面再入隊(duì)時(shí) rear 還指向一個(gè)已經(jīng)釋放的節(jié)點(diǎn)就會(huì)出現(xiàn)野指針。第二如果你實(shí)際上不需要出隊(duì)后返回的數(shù)據(jù)可以直接調(diào)用 getFront 拿到隊(duì)頭再調(diào)用 deQueue 刪除業(yè)務(wù)邏輯會(huì)更清晰。3. 買(mǎi)房主流程實(shí)現(xiàn)入隊(duì)、出隊(duì)、成交判斷的分工與合作3.1 輸入階段與主循環(huán)的整體結(jié)構(gòu)隊(duì)列寫(xiě)完之后接下來(lái)就是業(yè)務(wù)主流程。這個(gè)主流程本身并不復(fù)雜核心就是一句話把所有客戶(hù)按順序入隊(duì)然后循環(huán)處理隊(duì)頭客戶(hù)直到隊(duì)列為空。我先把整體骨架羅列出來(lái)int main() { Queue q; initQueue(q); int n; scanf(%d, n); for (int i 0; i n; i) { Customer c; scanf(%s %d %d %d, c.name, c.budget, c.prefer, c.arrive_time); enQueue(q, c); } while (!isEmpty(q)) { Customer c getFront(q); // 1. 判斷客戶(hù)是否買(mǎi)得起、目標(biāo)戶(hù)型是否有余量 // 2. 成交或放棄 // 3. 記錄結(jié)果 deQueue(q); } // 輸出結(jié)果 }為什么不寫(xiě)成一邊出隊(duì)一邊判斷也就是直接調(diào)用 deQueue 拿到客戶(hù)數(shù)據(jù)再判斷因?yàn)榭赡艹鲫?duì)之后你才發(fā)現(xiàn)這個(gè)客戶(hù)還需要和其他狀態(tài)項(xiàng)比如備選方案交互如果一開(kāi)始就把數(shù)據(jù)取走隊(duì)列的完整性就沒(méi)有意義了。保持“先查看隊(duì)頭再?zèng)Q定是否出隊(duì)”的順序可以讓邏輯更接近真實(shí)業(yè)務(wù)。3.2 分支條件的判斷次序很重要我給一個(gè)最簡(jiǎn)單的版本每個(gè)客戶(hù)只有一個(gè)目標(biāo)戶(hù)型如果目標(biāo)戶(hù)型售罄或預(yù)算不足客戶(hù)直接離開(kāi)。while (!isEmpty(q)) { Customer c getFront(q); if (house_count[c.prefer] 0 c.budget house_price[c.prefer]) { house_count[c.prefer]--; printf(%s bought house %d\n, c.name, c.prefer); } else { printf(%s left\n, c.name); } deQueue(q); }這段代碼看著沒(méi)有問(wèn)題但如果你把兩個(gè)判斷條件反過(guò)來(lái)寫(xiě)就會(huì)出現(xiàn)邏輯錯(cuò)誤。比如你先判斷預(yù)算夠不夠再判斷房源余量那么“預(yù)算夠但沒(méi)有房”和“預(yù)算不夠但有房”會(huì)被混為一類(lèi)輸出信息不夠準(zhǔn)確。更隱蔽的問(wèn)題是如果題目要求“目標(biāo)戶(hù)型售罄時(shí)可以買(mǎi)備選戶(hù)型”判斷次序就更加關(guān)鍵必須先用目標(biāo)戶(hù)型嘗試失敗后再用備選戶(hù)型而不是一上來(lái)就檢查備選。我給出一個(gè)帶備選戶(hù)型版本的判斷順序先看目標(biāo)戶(hù)型是否有余量且預(yù)算足夠滿(mǎn)足則成交否則看備選戶(hù)型是否有余量且預(yù)算足夠滿(mǎn)足則買(mǎi)備選兩個(gè)都不滿(mǎn)足客戶(hù)離開(kāi)。這個(gè)順序是嚴(yán)格按照現(xiàn)實(shí)業(yè)務(wù)邏輯來(lái)的客戶(hù)優(yōu)先選擇自己最喜歡的戶(hù)型買(mǎi)不到才會(huì)退而求其次。3.3 統(tǒng)計(jì)指標(biāo)等待時(shí)間與成交數(shù)據(jù)的處理不少題目要求輸出平均等待時(shí)間或者判斷“誰(shuí)的等待時(shí)間最長(zhǎng)”。這時(shí)候你就要在客戶(hù)節(jié)點(diǎn)里記錄到達(dá)時(shí)間然后在輪到他處理時(shí)計(jì)算等待時(shí)間。int wait_time current_time - c.arrive_time;這里有幾個(gè)細(xì)節(jié)很容易出錯(cuò)。第一current_time 是什么如果題目描述的是“每個(gè)客戶(hù)處理需要固定時(shí)間”那 current_time 就是從頭開(kāi)始累計(jì)的處理時(shí)間如果題目描述的是“當(dāng)前時(shí)刻”那 current_time 可能已經(jīng)給定。一定要仔細(xì)讀題。第二如果用 int 統(tǒng)計(jì)總等待時(shí)間客戶(hù)數(shù)量超過(guò)一定規(guī)模時(shí)會(huì)溢出。雖然業(yè)務(wù)上單個(gè)人等待時(shí)間不會(huì)很長(zhǎng)但總和可能很大。習(xí)慣上用 long 來(lái)存累計(jì)等待時(shí)間更穩(wěn)妥。第三如果你需要知道“最后買(mǎi)走某套房子的客戶(hù)是誰(shuí)”建議在房源結(jié)構(gòu)里維護(hù)一個(gè)買(mǎi)家字段而不是等到最后再回頭查。4. 實(shí)測(cè)踩坑復(fù)盤(pán)這題最容易扣分的四個(gè)細(xì)節(jié)4.1 坑一把“先來(lái)后到”實(shí)現(xiàn)成“排序后處理”這個(gè)坑我見(jiàn)過(guò)太多次。題目剛發(fā)下來(lái)有同學(xué)一看“買(mǎi)房”立刻聯(lián)想到貪心算法把客戶(hù)按預(yù)算從高到低排序優(yōu)先處理出價(jià)高的人。這種方案在某些“拍賣(mài)型”題目里是對(duì)的但在這道“排隊(duì)型”題目里直接掛掉。原因很簡(jiǎn)單業(yè)務(wù)規(guī)則決定順序算法不能擅自改變順序。如果題目明確說(shuō)“客戶(hù)按到達(dá)順序依次選房”那到達(dá)順序就是一條不可違反的鐵律。你在設(shè)計(jì)算法時(shí)第一步應(yīng)該是找“順序約束”而不是找“最優(yōu)策略”。怎么檢查你有沒(méi)有踩這個(gè)坑把輸入數(shù)據(jù)打亂順序再跑一遍如果結(jié)果變了說(shuō)明你的算法依賴(lài)輸入順序之外的某種排序規(guī)則那就要警惕了。4.2 坑二鏈?zhǔn)疥?duì)列出隊(duì)后沒(méi)有釋放舊節(jié)點(diǎn)這屬于典型的內(nèi)存管理問(wèn)題。OJ上跑的話通常不會(huì)爆出內(nèi)存泄漏的報(bào)錯(cuò)最多就是內(nèi)存占用偏高。但如果是人工代碼評(píng)審這一步基本要被扣分。錯(cuò)誤寫(xiě)法通常是這樣的Customer deQueue(Queue *q) { QNode *tmp q-front; q-front q-front-next; return tmp-data; // 忘了 free(tmp) }每次出隊(duì)少 free 一次跑一萬(wàn)個(gè)客戶(hù)就泄漏一萬(wàn)個(gè)節(jié)點(diǎn)。更麻煩的是如果出隊(duì)的是最后一個(gè)節(jié)點(diǎn)你還要把 rear 置為 NULL否則后續(xù)入隊(duì)會(huì)訪問(wèn)到原本已經(jīng)釋放的內(nèi)存。這兩個(gè)問(wèn)題經(jīng)常同時(shí)出現(xiàn)。我建議你寫(xiě)完隊(duì)列之后專(zhuān)門(mén)寫(xiě)一個(gè)“只有三個(gè)客戶(hù)”的小測(cè)試逐一入隊(duì)再逐一出隊(duì)配合內(nèi)存檢測(cè)工具檢查是否有泄漏。這一步花費(fèi)的時(shí)間很少但能避免很多隱性扣分。4.3 坑三循環(huán)數(shù)組隊(duì)列的“滿(mǎn)”和“空”判斷搞反如果你選用循環(huán)數(shù)組隊(duì)列最常見(jiàn)的問(wèn)題就是“隊(duì)滿(mǎn)”和“隊(duì)空”的判斷條件互相混淆。經(jīng)典的實(shí)現(xiàn)方式是讓數(shù)組保留一個(gè)空位用 front 和 rear 的相對(duì)位置來(lái)判斷隊(duì)列空f(shuō)ront rear隊(duì)列滿(mǎn)(rear 1) % capacity front很多同學(xué)會(huì)把隊(duì)滿(mǎn)條件寫(xiě)成 front rear導(dǎo)致一個(gè)滿(mǎn)隊(duì)列被誤判為空然后死循環(huán)。還有同學(xué)在入隊(duì)時(shí)沒(méi)有正確處理取模操作比如q-rear q-rear 1; // 錯(cuò)誤沒(méi)有取模 q-data[q-rear] c;這條代碼在連續(xù)入隊(duì)幾次之后rear 會(huì)直接越界訪問(wèn)數(shù)組尾部。正確寫(xiě)法是q-rear (q-rear 1) % capacity; q-data[q-rear] c;取模這件事特別容易在“看起來(lái)沒(méi)報(bào)錯(cuò)”的狀態(tài)下出錯(cuò)因?yàn)閿?shù)組越界訪問(wèn)不一定立刻崩潰可能只是偷偷覆蓋了相鄰內(nèi)存等到輸出統(tǒng)計(jì)結(jié)果時(shí)才變得莫名其妙。4.4 坑四判斷次序?qū)懛磳?dǎo)致已售罄戶(hù)型被再次賣(mài)出這個(gè)坑往往出現(xiàn)在稍微復(fù)雜的題目版本里。比如客戶(hù)可以先判斷“預(yù)算夠不夠”再判斷“有沒(méi)有房”。如果預(yù)算不夠程序可能直接輸出離開(kāi)但忽略了房源已經(jīng)被前面的人全部買(mǎi)完此時(shí)應(yīng)該輸出“售罄”而不是“預(yù)算不足”。反過(guò)來(lái)如果先判斷“有沒(méi)有房”再判斷“預(yù)算夠不夠”那么在房源還有、但預(yù)算不夠的情況下應(yīng)該繼續(xù)嘗試備選戶(hù)型而不是直接放棄。換句話說(shuō)判斷分支的先后順序直接決定了業(yè)務(wù)邏輯是否自洽。我的建議是把所有可能的判斷條件列出來(lái)模擬一個(gè)客戶(hù)走完全部流程再?zèng)Q定代碼順序。你可以在代碼里加一條注釋把判斷順序?qū)懗鰜?lái)// 1. 目標(biāo)戶(hù)型是否售罄 // 2. 預(yù)算是否足夠 // 3. 備選戶(hù)型是否售罄 // 4. 備選戶(hù)型是否買(mǎi)得起這看起來(lái)是小事但在寫(xiě)復(fù)雜版本時(shí)這一步能幫你減少無(wú)數(shù)調(diào)試時(shí)間。4.5 如何用邊界測(cè)試驗(yàn)證正確性作業(yè)提交之前我強(qiáng)烈建議你構(gòu)造幾組邊界測(cè)試用例不要只拿題目給的示例跑一遍就完事。下面是我常用的幾組用例類(lèi)型輸入特征期望結(jié)果空輸入客戶(hù)總量 n 0不報(bào)錯(cuò)輸出為空單個(gè)客戶(hù)只有一位客戶(hù)房源充足該客戶(hù)正常成交房源歸零所有戶(hù)型數(shù)量都是 0所有客戶(hù)離開(kāi)預(yù)算不足客戶(hù)預(yù)算低于任何戶(hù)型價(jià)格客戶(hù)全部離開(kāi)順序競(jìng)爭(zhēng)兩客戶(hù)搶同一戶(hù)型先到的預(yù)算不足先到的放棄后到的成交不能交換順序備選邏輯首選戶(hù)型售罄備選有余量客戶(hù)買(mǎi)備選戶(hù)型這些測(cè)試用例構(gòu)造起來(lái)很快但價(jià)值很高。很多隱藏邏輯錯(cuò)誤比如“判斷次序?qū)懛础薄绊樞虮慌判蚱茐摹痹诔Ｒ?guī)測(cè)試?yán)锟床怀鰜?lái)邊界測(cè)試一跑就現(xiàn)出原形。5. 從課堂作業(yè)到工程實(shí)踐隊(duì)列的三種進(jìn)階變形5.1 優(yōu)先隊(duì)列當(dāng)VIP客戶(hù)可以插隊(duì)時(shí)“買(mǎi)房排隊(duì)”這個(gè)場(chǎng)景在真實(shí)世界中往往不是絕對(duì)公平的。有的題目會(huì)加一條規(guī)則VIP客戶(hù)可以?xún)?yōu)先進(jìn)場(chǎng)。這時(shí)候你再用普通隊(duì)列就不合適了。優(yōu)先隊(duì)列和非優(yōu)先隊(duì)列的區(qū)別在于出隊(duì)的不一定是入隊(duì)最早的而是優(yōu)先級(jí)最高的。在C語(yǔ)言里你可以用堆Heap來(lái)實(shí)現(xiàn)在C里可以直接用 priority_queue。這個(gè)數(shù)據(jù)結(jié)構(gòu)在算法題里非常常見(jiàn)核心思路是在入隊(duì)時(shí)就把順序優(yōu)先級(jí)排好出隊(duì)時(shí)直接取堆頂。如果你做完這道“買(mǎi)房隊(duì)列”的必做題我建議你順手把同樣場(chǎng)景改成“VIP優(yōu)先”再寫(xiě)一遍。你會(huì)發(fā)現(xiàn)業(yè)務(wù)規(guī)則一變數(shù)據(jù)結(jié)構(gòu)選擇也跟著變這才是真正的能力考察點(diǎn)。5.2 雙端隊(duì)列當(dāng)客戶(hù)可能反悔時(shí)有些模擬場(chǎng)景中客戶(hù)可能會(huì)“撤銷(xiāo)剛才的選房”或者新來(lái)的客戶(hù)需要排到最前面。這時(shí)雙端隊(duì)列 deque 就派上用場(chǎng)了它允許你在隊(duì)頭和隊(duì)尾兩端都能入隊(duì)、出隊(duì)。在“買(mǎi)房”這個(gè)業(yè)務(wù)里怎么用比如客戶(hù)選完房后突然決定反悔退房出來(lái)后重新排隊(duì)到末尾這個(gè)過(guò)程需要從隊(duì)尾入隊(duì)而如果題目有“老客戶(hù)優(yōu)先”的規(guī)則那就可能需要從隊(duì)頭插入。雙端隊(duì)列能同時(shí)覆蓋這兩種需求抽象能力比普通隊(duì)列強(qiáng)很多。5.3 隊(duì)列在真實(shí)系統(tǒng)中的同構(gòu)應(yīng)用學(xué)完這道作業(yè)題你會(huì)發(fā)現(xiàn)隊(duì)列的應(yīng)用范圍遠(yuǎn)比“模擬排隊(duì)”廣泛。舉幾個(gè)例子消息隊(duì)列生產(chǎn)者把消息入隊(duì)消費(fèi)者按順序出隊(duì)保證消息不丟失、不重復(fù)任務(wù)調(diào)度操作系統(tǒng)中的就緒隊(duì)列CPU按時(shí)間片輪轉(zhuǎn)處理任務(wù)網(wǎng)絡(luò)請(qǐng)求服務(wù)器接收大量并發(fā)請(qǐng)求往往先放入請(qǐng)求隊(duì)列再逐個(gè)處理打印任務(wù)多個(gè)文檔發(fā)送到打印機(jī)打印機(jī)按提交順序逐個(gè)打印。這些場(chǎng)景的共同點(diǎn)都是“先來(lái)先服務(wù)”和買(mǎi)房排隊(duì)本質(zhì)上是同構(gòu)的。你在未來(lái)工作中很可能遇到比這道題大得多的數(shù)據(jù)量但抽象思路完全一樣。最后再分享一個(gè)實(shí)際經(jīng)驗(yàn)。在寫(xiě)這類(lèi)“場(chǎng)景模擬”題目時(shí)我建議你養(yǎng)成一個(gè)習(xí)慣在每一步關(guān)鍵操作前后打印日志比如“XX入隊(duì)當(dāng)前隊(duì)頭是XX”然后拿著日志模擬一遍整個(gè)買(mǎi)房流程。這個(gè)方法看起來(lái)原始但排查邏輯錯(cuò)誤極其高效。很多時(shí)候你以為自己的隊(duì)列出了問(wèn)題其實(shí)只是判斷分支寫(xiě)錯(cuò)了順序。這道作業(yè)題的價(jià)值并不在于讓你背下隊(duì)列的八個(gè)方法而是在于訓(xùn)練一種能力——把現(xiàn)實(shí)世界里復(fù)雜、動(dòng)態(tài)、多約束的業(yè)務(wù)過(guò)程翻譯成一個(gè)只有入隊(duì)、出隊(duì)、取隊(duì)頭三種操作的簡(jiǎn)潔模型。能順利完成這種翻譯數(shù)據(jù)結(jié)構(gòu)這門(mén)課的核心目標(biāo)也就達(dá)到了。