課本練習(xí)題：一個(gè)醫(yī)院可以容納n個(gè)病人。每次病人進(jìn)來(lái)時(shí)，都會(huì)對(duì)他進(jìn)行評(píng)估，如果情況非危急，則必須等待輪到他。如果情況危急，他將被轉(zhuǎn)移為下一個(gè)接受治療的人。如果患者在被呼叫時(shí)在洗手間，他會(huì)跳過(guò)輪到他并被視為新患者。在任何時(shí)候，醫(yī)院都需要知道誰(shuí)在接受治療，以及剩余的容量。解決這個(gè)問(wèn)題是否更有效（能夠選擇多個(gè)答案）： 1. deque 2. 數(shù)組 3. 循環(huán)數(shù)組 4. 自定義數(shù)據(jù)結(jié)構(gòu)：數(shù)組 + 堆棧 5. 堆棧
1 回答
慕少森
TA貢獻(xiàn)2019條經(jīng)驗(yàn) 獲得超9個(gè)贊
Deque：這將是一個(gè)不錯(cuò)的選擇，因?yàn)槟梢栽?O(1) 時(shí)間內(nèi)從行的前端/末尾添加/刪除，并且可以使用整數(shù)變量跟蹤患者的數(shù)量，因此獲取大小行的將是 O(1)。您還可以通過(guò)在添加患者之前檢查線路的大小來(lái)確保最大容量為 N。
數(shù)組：由于您需要添加到行首，普通數(shù)組不是一個(gè)好的選擇，因?yàn)槟仨殞⑺性匾苿?dòng) 1 個(gè)位置以在數(shù)組的開(kāi)頭騰出空間。這會(huì)給你 O(n) 來(lái)添加到行的前面。
圓形陣列：這將是最好的選擇，比雙端隊(duì)列更好的一個(gè)小原因......因?yàn)樗幸粋€(gè)底層數(shù)組，所有的內(nèi)存位置（排隊(duì)病人的點(diǎn)）都是連續(xù)的，而有一個(gè)出隊(duì)，這是使用底層鏈表實(shí)現(xiàn)，內(nèi)存位置是隨機(jī)且不連續(xù)的。這提供了一個(gè)小好處。您可以創(chuàng)建一個(gè)大小為 N（醫(yī)院的容量）的數(shù)組，并一遍又一遍地使用相同的內(nèi)存位置。如果醫(yī)院沒(méi)有容量（無(wú)限數(shù)量的患者可以排隊(duì)），則您將需要使用出隊(duì)（因?yàn)閿?shù)組具有固定長(zhǎng)度）。從前/后添加/刪除是 O(1) 就像雙端隊(duì)列一樣，并且獲取行的大小也是 O(1) 因?yàn)槟梢允褂眯械拈_(kāi)始/結(jié)束索引來(lái)計(jì)算它。
數(shù)組 + 堆棧：與僅使用數(shù)組（#2）相比，這沒(méi)有任何好處，因?yàn)槎褩Ｊ菬o(wú)用的（參見(jiàn) #5）。
堆棧：由于您需要添加到行的開(kāi)頭和結(jié)尾，因此堆棧不起作用（它只能添加到一側(cè)）。
所以按照從最好到最壞的順序：3、1、2、4、5。
除了#5 之外，所有都可以使用。
添加回答
舉報(bào)
0/150
提交
取消