列、鏈?zhǔn)疥?duì)列與約瑟夫環(huán)的C++實(shí)現(xiàn)與避坑指南)
隊(duì)列這個(gè)結(jié)構(gòu)剛學(xué)數(shù)據(jù)結(jié)構(gòu)那會(huì)兒我覺得它比棧簡(jiǎn)單——不就是先進(jìn)先出嘛能有多難。結(jié)果第一次用數(shù)組手寫循環(huán)隊(duì)列被取模運(yùn)算繞得頭暈第一次用鏈表實(shí)現(xiàn)隊(duì)列指針操作寫反了導(dǎo)致內(nèi)存泄漏第一次做約瑟夫環(huán)用數(shù)組模擬報(bào)數(shù)邊界條件調(diào)了整整一個(gè)下午。這三個(gè)東西單獨(dú)拎出來(lái)都不算復(fù)雜但放在一起恰好覆蓋了線性結(jié)構(gòu)里最核心的幾類問題連續(xù)存儲(chǔ)與離散存儲(chǔ)的取舍、循環(huán)利用空間的技巧、以及用數(shù)據(jù)結(jié)構(gòu)解決經(jīng)典數(shù)學(xué)問題的建模思路。下面我就按自己踩坑的順序把順序隊(duì)列、鏈?zhǔn)疥?duì)列和約瑟夫環(huán)的C實(shí)現(xiàn)從頭到尾捋一遍代碼全部實(shí)測(cè)可跑關(guān)鍵位置我會(huì)解釋為什么這么寫而不是那么寫。1. 為什么隊(duì)列值得單獨(dú)花時(shí)間啃很多人學(xué)數(shù)據(jù)結(jié)構(gòu)有個(gè)誤區(qū)覺得隊(duì)列太簡(jiǎn)單看一眼就跳過去把精力全砸在樹和圖上面。我當(dāng)初也這么想直到后來(lái)做項(xiàng)目時(shí)遇到一個(gè)消息緩沖的需求才發(fā)現(xiàn)自己對(duì)隊(duì)列的理解全是漏洞。隊(duì)列的本質(zhì)是受限的線性表——只允許在一端插入另一端刪除。這個(gè)限制看起來(lái)是閹割了線性表的能力但實(shí)際上它帶來(lái)的語(yǔ)義非常明確先來(lái)的先被處理。這個(gè)語(yǔ)義在操作系統(tǒng)調(diào)度、網(wǎng)絡(luò)數(shù)據(jù)包緩沖、打印任務(wù)排隊(duì)、廣度優(yōu)先搜索等場(chǎng)景里反復(fù)出現(xiàn)。你如果只是背下來(lái)先進(jìn)先出四個(gè)字遇到具體問題照樣寫不對(duì)。順序隊(duì)列和鏈?zhǔn)疥?duì)列解決的是同一個(gè)問題但底層存儲(chǔ)方式完全不同。順序隊(duì)列用一段連續(xù)內(nèi)存靠?jī)蓚€(gè)下標(biāo)front和rear標(biāo)記隊(duì)頭和隊(duì)尾鏈?zhǔn)疥?duì)列用離散節(jié)點(diǎn)靠指針串聯(lián)。兩者各有各的坑順序隊(duì)列如果不做循環(huán)處理會(huì)出現(xiàn)假溢出——明明數(shù)組前面有空位但因?yàn)閞ear已經(jīng)到頭了新元素就是插不進(jìn)去鏈?zhǔn)疥?duì)列則要小心指針操作順序?qū)懛匆徊骄褪莾?nèi)存泄漏或者段錯(cuò)誤。約瑟夫環(huán)則是隊(duì)列的一個(gè)經(jīng)典應(yīng)用場(chǎng)景。問題描述很簡(jiǎn)單n個(gè)人圍成一圈從第一個(gè)人開始報(bào)數(shù)報(bào)到m的人出列然后從下一個(gè)人繼續(xù)報(bào)數(shù)直到所有人出列。用隊(duì)列來(lái)模擬這個(gè)過程非常自然——每次把隊(duì)頭元素移到隊(duì)尾相當(dāng)于跳過一個(gè)人報(bào)到m時(shí)直接出隊(duì)相當(dāng)于淘汰一個(gè)人。但真正寫起來(lái)邊界條件、報(bào)數(shù)起點(diǎn)、剩余人數(shù)的處理每一個(gè)都可能讓你調(diào)試半天。我下面會(huì)先講順序隊(duì)列的循環(huán)實(shí)現(xiàn)再講鏈?zhǔn)疥?duì)列的指針操作最后用隊(duì)列思路解約瑟夫環(huán)。每一部分都會(huì)給出完整代碼、關(guān)鍵邏輯解釋以及我在實(shí)際調(diào)試中總結(jié)的注意事項(xiàng)。2. 順序隊(duì)列的循環(huán)數(shù)組實(shí)現(xiàn)與假溢出陷阱2.1 順序隊(duì)列的基本結(jié)構(gòu)設(shè)計(jì)順序隊(duì)列最直覺的做法是開一個(gè)固定大小的數(shù)組用front記錄隊(duì)頭位置用rear記錄隊(duì)尾位置。入隊(duì)時(shí)把元素放到rear位置然后rear加一出隊(duì)時(shí)取走front位置的元素然后front加一。空隊(duì)列的條件是front等于rear。這個(gè)設(shè)計(jì)在元素只進(jìn)不出的情況下沒問題但一旦有出隊(duì)操作front就會(huì)往后移動(dòng)前面空出來(lái)的位置就永遠(yuǎn)浪費(fèi)了。比如數(shù)組大小是5你入隊(duì)5個(gè)元素rear到了5越界此時(shí)出隊(duì)2個(gè)元素front變成2數(shù)組下標(biāo)0和1的位置空著但rear已經(jīng)不能再加了。這就是假溢出——不是真的沒空間而是空間沒有被循環(huán)利用。解決辦法是把數(shù)組在邏輯上彎成一個(gè)環(huán)。當(dāng)rear到達(dá)數(shù)組末尾時(shí)如果前面還有空位就讓它繞回到下標(biāo)0繼續(xù)存放。實(shí)現(xiàn)上就是每次移動(dòng)下標(biāo)時(shí)做一次取模運(yùn)算rear (rear 1) % capacity。這樣數(shù)組的物理存儲(chǔ)還是線性的但邏輯上變成了循環(huán)的。這里有一個(gè)關(guān)鍵細(xì)節(jié)如何區(qū)分隊(duì)空和隊(duì)滿。如果不做特殊處理隊(duì)空時(shí)front等于rear隊(duì)滿時(shí)front也等于rear因?yàn)閞ear繞了一圈追上了front兩者條件沖突。常見的解決方案有三種犧牲一個(gè)存儲(chǔ)單元隊(duì)滿的條件變成(rear 1) % capacity front也就是說(shuō)當(dāng)rear的下一個(gè)位置是front時(shí)就算滿實(shí)際可用容量是capacity減一。增加一個(gè)size變量記錄當(dāng)前元素個(gè)數(shù)隊(duì)空時(shí)size為0隊(duì)滿時(shí)size等于capacity判斷簡(jiǎn)單直接。增加一個(gè)tag標(biāo)記記錄最后一次操作是入隊(duì)還是出隊(duì)配合front和rear判斷。我個(gè)人最推薦第二種——加一個(gè)size變量。原因很簡(jiǎn)單代碼可讀性最好不需要在腦子里繞取模邏輯而且實(shí)際項(xiàng)目中隊(duì)列的容量通常不會(huì)卡到極限多一個(gè)int變量的開銷完全可以忽略。下面給出的實(shí)現(xiàn)就用這種方式。2.2 循環(huán)隊(duì)列的完整C實(shí)現(xiàn)#include iostream using namespace std; templatetypename T class CircularQueue { private: T* data; // 動(dòng)態(tài)數(shù)組 int capacity; // 容量 int front; // 隊(duì)頭下標(biāo) int rear; // 隊(duì)尾下標(biāo)下一個(gè)入隊(duì)位置 int count; // 當(dāng)前元素個(gè)數(shù) public: CircularQueue(int cap 10) { capacity cap; data new T[capacity]; front 0; rear 0; count 0; } ~CircularQueue() { delete[] data; } bool isEmpty() const { return count 0; } bool isFull() const { return count capacity; } int size() const { return count; } bool enqueue(const T value) { if (isFull()) { return false; // 隊(duì)列已滿入隊(duì)失敗 } data[rear] value; rear (rear 1) % capacity; count; return true; } bool dequeue(T value) { if (isEmpty()) { return false; // 隊(duì)列為空出隊(duì)失敗 } value data[front]; front (front 1) % capacity; count--; return true; } bool getFront(T value) const { if (isEmpty()) { return false; } value data[front]; return true; } void print() const { if (isEmpty()) { cout 隊(duì)列為空 endl; return; } cout 隊(duì)列元素: ; int idx front; for (int i 0; i count; i) { cout data[idx] ; idx (idx 1) % capacity; } cout endl; } };這段代碼有幾個(gè)地方值得展開說(shuō)。為什么用模板隊(duì)列里存什么類型的數(shù)據(jù)是不確定的可能是int、string也可能是自定義的結(jié)構(gòu)體。用模板可以讓同一份代碼適配所有類型避免為每種類型重復(fù)寫一遍。如果你暫時(shí)不熟悉模板把templatetypename T去掉把所有T換成int邏輯完全一樣。為什么用動(dòng)態(tài)數(shù)組而不是固定大小數(shù)組固定大小數(shù)組在編譯期就確定了容量不夠靈活。用new T[capacity]在堆上分配內(nèi)存容量可以在構(gòu)造時(shí)指定用完之后在析構(gòu)函數(shù)里delete[]釋放。這里要注意如果是存自定義類型T需要有無(wú)參構(gòu)造函數(shù)或者你需要在分配時(shí)做額外處理不過對(duì)于基礎(chǔ)類型和標(biāo)準(zhǔn)庫(kù)類型都沒問題。入隊(duì)和出隊(duì)的返回值設(shè)計(jì)我讓enqueue和dequeue返回bool表示操作是否成功。這樣做的好處是調(diào)用方可以明確知道操作結(jié)果而不是默默失敗。有些教材的實(shí)現(xiàn)直接返回void隊(duì)列滿時(shí)什么都不做調(diào)用方根本不知道數(shù)據(jù)有沒有進(jìn)去。實(shí)際項(xiàng)目中這種沉默失敗是災(zāi)難性的。取模運(yùn)算的位置rear (rear 1) % capacity這行代碼是循環(huán)隊(duì)列的核心。當(dāng)rear等于capacity減一時(shí)加一變成capacity取模后變成0正好繞回?cái)?shù)組開頭。front的移動(dòng)同理。你可以手動(dòng)模擬一下capacity為5rear從0開始依次變成1、2、3、4、0、1……永遠(yuǎn)不會(huì)越界。2.3 實(shí)測(cè)中容易踩的三個(gè)坑第一個(gè)坑取模運(yùn)算的優(yōu)先級(jí)。C中%的優(yōu)先級(jí)和*、/同級(jí)高于和-。所以rear 1 % capacity會(huì)被解析成rear (1 % capacity)結(jié)果完全錯(cuò)誤。必須寫成(rear 1) % capacity。我當(dāng)初就是因?yàn)樯賹懥艘粚?duì)括號(hào)調(diào)試了半個(gè)小時(shí)才發(fā)現(xiàn)問題。第二個(gè)坑遍歷隊(duì)列時(shí)的下標(biāo)處理。因?yàn)殛?duì)列是循環(huán)的不能簡(jiǎn)單地從front循環(huán)到rear因?yàn)閞ear可能小于front。正確的做法是用count控制循環(huán)次數(shù)每次下標(biāo)加一后取模。上面print函數(shù)就是這么寫的。如果你用for (int i front; i ! rear; i (i 1) % capacity)也可以但要注意隊(duì)列滿時(shí)front等于rear這個(gè)循環(huán)一次都不會(huì)執(zhí)行需要額外處理。第三個(gè)坑拷貝構(gòu)造和賦值運(yùn)算符。上面的類用了動(dòng)態(tài)內(nèi)存分配如果直接拷貝對(duì)象兩個(gè)對(duì)象會(huì)共享同一塊內(nèi)存析構(gòu)時(shí)就會(huì)double free。正確的做法是實(shí)現(xiàn)拷貝構(gòu)造函數(shù)和賦值運(yùn)算符深拷貝或者用std::vector代替裸指針。為了代碼簡(jiǎn)潔我這里沒有展開但你在實(shí)際使用中一定要注意。如果只是局部使用、不涉及對(duì)象拷貝問題不大一旦要把隊(duì)列作為參數(shù)傳遞或者放入容器就必須處理這個(gè)問題。提示如果你用的是C11及以上標(biāo)準(zhǔn)可以用std::unique_ptrT[]來(lái)管理數(shù)組內(nèi)存這樣連析構(gòu)函數(shù)都不用寫了而且自動(dòng)禁止拷貝避免誤用。3. 鏈?zhǔn)疥?duì)列的指針操作與邊界處理3.1 鏈?zhǔn)疥?duì)列的節(jié)點(diǎn)設(shè)計(jì)與頭尾指針順序隊(duì)列的容量是固定的一旦滿了就沒法再入隊(duì)。鏈?zhǔn)疥?duì)列沒有這個(gè)問題——每個(gè)元素是一個(gè)獨(dú)立的節(jié)點(diǎn)用指針串聯(lián)起來(lái)理論上只要內(nèi)存夠就可以一直入隊(duì)。鏈?zhǔn)疥?duì)列需要維護(hù)兩個(gè)指針front指向隊(duì)頭節(jié)點(diǎn)rear指向隊(duì)尾節(jié)點(diǎn)。入隊(duì)在rear后面接一個(gè)新節(jié)點(diǎn)出隊(duì)刪除front指向的節(jié)點(diǎn)。這里有一個(gè)設(shè)計(jì)選擇要不要帶頭節(jié)點(diǎn)。帶頭節(jié)點(diǎn)的意思是front指向一個(gè)不存數(shù)據(jù)的啞節(jié)點(diǎn)真正的隊(duì)頭元素是front-next。帶頭的好處是入隊(duì)和出隊(duì)的代碼可以統(tǒng)一處理不需要單獨(dú)判斷隊(duì)列是否為空。不帶頭的代碼更直觀但空隊(duì)列時(shí)插入第一個(gè)元素需要特殊處理。我兩種都寫過個(gè)人更傾向于不帶頭節(jié)點(diǎn)因?yàn)榇a更短邏輯更直接。但如果你追求代碼的對(duì)稱性和統(tǒng)一性帶頭節(jié)點(diǎn)也是很好的選擇。下面給出的實(shí)現(xiàn)不帶頭節(jié)點(diǎn)。#include iostream using namespace std; templatetypename T struct Node { T data; Node* next; Node(const T d) : data(d), next(nullptr) {} }; templatetypename T class LinkedQueue { private: NodeT* front; // 隊(duì)頭指針 NodeT* rear; // 隊(duì)尾指針 int count; // 元素個(gè)數(shù) public: LinkedQueue() : front(nullptr), rear(nullptr), count(0) {} ~LinkedQueue() { while (front ! nullptr) { NodeT* temp front; front front-next; delete temp; } } bool isEmpty() const { return front nullptr; } int size() const { return count; } void enqueue(const T value) { NodeT* newNode new NodeT(value); if (isEmpty()) { front rear newNode; } else { rear-next newNode; rear newNode; } count; } bool dequeue(T value) { if (isEmpty()) { return false; } value front-data; NodeT* temp front; front front-next; if (front nullptr) { rear nullptr; // 隊(duì)列變空rear也要置空 } delete temp; count--; return true; } bool getFront(T value) const { if (isEmpty()) { return false; } value front-data; return true; } void print() const { if (isEmpty()) { cout 隊(duì)列為空 endl; return; } cout 隊(duì)列元素: ; NodeT* cur front; while (cur ! nullptr) { cout cur-data ; cur cur-next; } cout endl; } };3.2 入隊(duì)和出隊(duì)的指針變化過程鏈?zhǔn)疥?duì)列的入隊(duì)操作分兩種情況。如果隊(duì)列為空新節(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾所以front rear newNode。如果隊(duì)列不為空把新節(jié)點(diǎn)接到rear的后面然后更新rear指向新節(jié)點(diǎn)。注意這里不能先更新rear再連接否則就找不到原來(lái)的隊(duì)尾了。順序必須是先rear-next newNode再rear newNode。出隊(duì)操作也分兩種情況。如果出隊(duì)后隊(duì)列變空f(shuō)ront變成了nullptr必須把rear也置為nullptr。這一步非常容易漏掉。如果你漏了rear會(huì)指向一個(gè)已經(jīng)被delete的節(jié)點(diǎn)下次入隊(duì)時(shí)rear-next newNode就會(huì)訪問已釋放的內(nèi)存程序可能崩潰或者產(chǎn)生不可預(yù)期的行為。我當(dāng)初就是因?yàn)槁┝诉@一行程序在小數(shù)據(jù)量下運(yùn)行正常一旦數(shù)據(jù)量大了就隨機(jī)崩潰排查了很久才定位到。內(nèi)存釋放的順序出隊(duì)時(shí)先用temp保存front然后front后移最后delete temp。順序不能反——如果先delete front再訪問front-next就是訪問已釋放內(nèi)存。這個(gè)錯(cuò)誤在初學(xué)者代碼里非常常見。析構(gòu)函數(shù)的實(shí)現(xiàn)析構(gòu)時(shí)需要遍歷整個(gè)鏈表逐個(gè)delete節(jié)點(diǎn)。注意在delete當(dāng)前節(jié)點(diǎn)之前要先把front移到下一個(gè)節(jié)點(diǎn)否則就找不到后續(xù)節(jié)點(diǎn)了。上面的析構(gòu)函數(shù)就是這么寫的。3.3 鏈?zhǔn)疥?duì)列相比順序隊(duì)列的取舍鏈?zhǔn)疥?duì)列和順序隊(duì)列沒有絕對(duì)的優(yōu)劣關(guān)鍵看使用場(chǎng)景。我整理了一個(gè)對(duì)比表格對(duì)比維度順序隊(duì)列循環(huán)數(shù)組鏈?zhǔn)疥?duì)列內(nèi)存分配一次性分配連續(xù)內(nèi)存每次入隊(duì)動(dòng)態(tài)分配節(jié)點(diǎn)容量限制固定滿了無(wú)法入隊(duì)理論上無(wú)限制受內(nèi)存約束緩存友好度高連續(xù)內(nèi)存訪問快低節(jié)點(diǎn)分散在堆上入隊(duì)時(shí)間復(fù)雜度O(1)O(1)但有new操作開銷出隊(duì)時(shí)間復(fù)雜度O(1)O(1)但有delete操作開銷內(nèi)存開銷僅數(shù)組本身每個(gè)節(jié)點(diǎn)多一個(gè)指針域適用場(chǎng)景容量可預(yù)估、追求性能容量不確定、頻繁增刪如果你的隊(duì)列容量可以預(yù)估比如做嵌入式開發(fā)時(shí)緩沖區(qū)大小固定順序隊(duì)列更合適——沒有動(dòng)態(tài)內(nèi)存分配不會(huì)產(chǎn)生內(nèi)存碎片訪問速度也更快。如果容量完全不可預(yù)測(cè)比如處理網(wǎng)絡(luò)請(qǐng)求鏈?zhǔn)疥?duì)列更靈活。還有一個(gè)實(shí)際因素動(dòng)態(tài)內(nèi)存分配的開銷。每次入隊(duì)都new一個(gè)節(jié)點(diǎn)每次出隊(duì)都delete一個(gè)節(jié)點(diǎn)在高頻場(chǎng)景下這個(gè)開銷不可忽視。有些高性能場(chǎng)景會(huì)用內(nèi)存池來(lái)優(yōu)化預(yù)先分配一批節(jié)點(diǎn)循環(huán)使用避免頻繁的系統(tǒng)調(diào)用。不過這屬于進(jìn)階優(yōu)化初學(xué)階段先把基礎(chǔ)實(shí)現(xiàn)搞扎實(shí)。注意鏈?zhǔn)疥?duì)列的enqueue操作如果new失敗內(nèi)存耗盡會(huì)拋出std::bad_alloc異常。在資源受限的環(huán)境下你可能需要捕獲這個(gè)異常并做降級(jí)處理而不是讓程序直接崩潰。4. 約瑟夫環(huán)的隊(duì)列建模與模擬實(shí)現(xiàn)4.1 約瑟夫環(huán)問題的本質(zhì)拆解約瑟夫環(huán)的描述有很多版本核心邏輯是一樣的n個(gè)人圍成一圈從某個(gè)人開始報(bào)數(shù)每報(bào)到m的人出列然后從出列者的下一個(gè)人重新開始報(bào)數(shù)直到所有人出列。要求輸出出列的順序。這個(gè)問題的數(shù)學(xué)模型其實(shí)是一個(gè)遞推問題有O(n)的數(shù)學(xué)解法。但用隊(duì)列來(lái)模擬是最直觀的也是理解隊(duì)列應(yīng)用的絕佳案例。用隊(duì)列模擬的思路是把n個(gè)人依次入隊(duì)。從隊(duì)頭開始每次把隊(duì)頭元素取出并重新入隊(duì)到隊(duì)尾相當(dāng)于這個(gè)人報(bào)數(shù)不是m跳過。當(dāng)報(bào)數(shù)到m時(shí)隊(duì)頭元素直接出隊(duì)不再入隊(duì)這個(gè)人被淘汰。重復(fù)上述過程直到隊(duì)列為空。這里的關(guān)鍵是報(bào)數(shù)計(jì)數(shù)器的維護(hù)。你可以用一個(gè)變量從1開始計(jì)數(shù)每處理一個(gè)人就加一當(dāng)計(jì)數(shù)器等于m時(shí)執(zhí)行淘汰并重置計(jì)數(shù)器為1。也可以每輪固定移動(dòng)m減一次然后淘汰隊(duì)頭。兩種寫法等價(jià)但后者代碼更簡(jiǎn)潔。4.2 用鏈?zhǔn)疥?duì)列模擬約瑟夫環(huán)#include iostream using namespace std; // 復(fù)用上面的LinkedQueue這里簡(jiǎn)化為int類型 void josephus(int n, int m) { LinkedQueueint q; for (int i 1; i n; i) { q.enqueue(i); } cout 出列順序: ; int count 0; // 已出列人數(shù) while (!q.isEmpty()) { int cur; q.dequeue(cur); count; if (count % m 0) { // 報(bào)到m出列 cout cur ; } else { // 未報(bào)到m重新入隊(duì) q.enqueue(cur); } } cout endl; } int main() { int n 7, m 3; cout n n , m m endl; josephus(n, m); return 0; }運(yùn)行結(jié)果出列順序: 3 6 2 7 5 1 4。這個(gè)實(shí)現(xiàn)非常簡(jiǎn)潔但有幾個(gè)細(xì)節(jié)值得注意。為什么用count % m而不是維護(hù)一個(gè)獨(dú)立的報(bào)數(shù)變量count記錄的是當(dāng)前處理到第幾個(gè)人包括已經(jīng)出列和重新入隊(duì)的每處理一個(gè)人count加一。當(dāng)count能被m整除時(shí)說(shuō)明當(dāng)前這個(gè)人正好是第m個(gè)報(bào)數(shù)的應(yīng)該出列。這種寫法避免了在出列后重置計(jì)數(shù)器的操作邏輯更統(tǒng)一。出列后為什么不需要特殊處理因?yàn)槌隽械娜酥苯訌年?duì)列中移除了隊(duì)列的front自動(dòng)指向下一個(gè)人下一輪循環(huán)自然從下一個(gè)人開始報(bào)數(shù)。這正是隊(duì)列先進(jìn)先出特性帶來(lái)的便利——你不需要手動(dòng)維護(hù)下一個(gè)人是誰(shuí)。時(shí)間復(fù)雜度分析每處理一個(gè)人要么出列O(1)要么重新入隊(duì)O(1)?？偣蔡幚淼娜舜螖?shù)是n乘以m因?yàn)槊刻蕴粋€(gè)人需要跳過m減一個(gè)人所以時(shí)間復(fù)雜度是O(n*m)。當(dāng)n和m都很大時(shí)這個(gè)模擬會(huì)非常慢。比如n等于一百萬(wàn)、m等于一百萬(wàn)運(yùn)算量是萬(wàn)億級(jí)別肯定超時(shí)。這時(shí)候就需要用數(shù)學(xué)遞推法把時(shí)間復(fù)雜度降到O(n)。4.3 數(shù)學(xué)遞推法的思路與對(duì)比數(shù)學(xué)遞推法的核心是找到出列編號(hào)的遞推關(guān)系。假設(shè)f(n, m)表示n個(gè)人報(bào)數(shù)m時(shí)最后剩下的人或者第一個(gè)出列的人的編號(hào)。經(jīng)過推導(dǎo)可以得到遞推公式f(n, m) (f(n-1, m) m) % n其中f(1, m)等于0假設(shè)編號(hào)從0開始。這個(gè)公式的含義是n個(gè)人問題的解等于n減一個(gè)人問題的解加上m再對(duì)n取模。你可以這樣理解淘汰一個(gè)人之后剩下n減一個(gè)人重新圍成一圈但起點(diǎn)變了需要做一個(gè)偏移映射。用遞推法求第一個(gè)出列的人int josephusMath(int n, int m) { int result 0; // f(1, m) 0 for (int i 2; i n; i) { result (result m) % i; } return result 1; // 轉(zhuǎn)換回1-based編號(hào) }這個(gè)算法的時(shí)間復(fù)雜度是O(n)空間復(fù)雜度是O(1)比隊(duì)列模擬快得多。但它只能求出最后剩下的人如果要輸出完整的出列順序還是得用模擬法或者更復(fù)雜的數(shù)學(xué)方法。兩種方法的適用場(chǎng)景如果只需要知道最后誰(shuí)留下用數(shù)學(xué)遞推法如果需要完整的出列順序用隊(duì)列模擬法。在實(shí)際面試中面試官可能會(huì)先讓你用模擬法寫然后問你有沒有更優(yōu)的解法這時(shí)候數(shù)學(xué)遞推法就是加分項(xiàng)。提示約瑟夫環(huán)的數(shù)學(xué)解法有多種變體有的求最后剩下的人有的求第k個(gè)出列的人。遞推公式的初始條件和邊界處理略有不同使用前一定要確認(rèn)清楚問題的具體定義。5. 三個(gè)實(shí)現(xiàn)串起來(lái)看存儲(chǔ)方式如何決定代碼形態(tài)把順序隊(duì)列、鏈?zhǔn)疥?duì)列和約瑟夫環(huán)放在一起看會(huì)發(fā)現(xiàn)一個(gè)有意思的規(guī)律底層存儲(chǔ)方式直接決定了代碼的形態(tài)和容易出錯(cuò)的地方。順序隊(duì)列的代碼里到處都是取模運(yùn)算因?yàn)槟阋谶壿嬌习丫€性數(shù)組彎成環(huán)。取模運(yùn)算的優(yōu)先級(jí)、邊界值的處理、隊(duì)空隊(duì)滿的判斷這些坑都源于用連續(xù)內(nèi)存模擬循環(huán)這個(gè)核心設(shè)計(jì)。你如果理解了這一點(diǎn)就能預(yù)判哪些地方容易出問題——所有涉及下標(biāo)移動(dòng)的地方都要檢查取模所有涉及front和rear比較的地方都要考慮繞圈的情況。鏈?zhǔn)疥?duì)列的代碼里到處都是指針操作因?yàn)槟阋謩?dòng)管理節(jié)點(diǎn)的連接和釋放。指針操作順序、空隊(duì)列的特殊處理、內(nèi)存泄漏的防范這些坑都源于用離散節(jié)點(diǎn)維護(hù)順序關(guān)系這個(gè)核心設(shè)計(jì)。你如果理解了這一點(diǎn)就能預(yù)判哪些地方容易出問題——所有涉及指針賦值的地方都要考慮順序所有涉及節(jié)點(diǎn)刪除的地方都要檢查是否有其他指針還指向它。約瑟夫環(huán)的代碼則體現(xiàn)了數(shù)據(jù)結(jié)構(gòu)選擇對(duì)問題建模的影響。用隊(duì)列來(lái)模擬代碼不到二十行邏輯清晰到幾乎不需要注釋。如果用數(shù)組來(lái)模擬你需要手動(dòng)維護(hù)當(dāng)前報(bào)數(shù)位置、標(biāo)記已出列的人、處理數(shù)組越界繞回代碼量至少翻倍而且容易出錯(cuò)。這就是數(shù)據(jù)結(jié)構(gòu)的價(jià)值——選對(duì)了結(jié)構(gòu)問題本身就變簡(jiǎn)單了。我在實(shí)際編碼中總結(jié)了一個(gè)判斷原則如果問題的核心操作是在一端加入、在另一端刪除就用隊(duì)列如果核心操作是在一端加入、在同一端刪除就用棧如果核心操作是隨機(jī)訪問任意位置就用數(shù)組或鏈表。約瑟夫環(huán)的核心操作是跳過一個(gè)人從隊(duì)頭移到隊(duì)尾和淘汰一個(gè)人從隊(duì)頭刪除正好符合隊(duì)列的操作模式所以隊(duì)列是最自然的選擇。再補(bǔ)充一個(gè)實(shí)際調(diào)試中的經(jīng)驗(yàn)先用小數(shù)據(jù)量驗(yàn)證邏輯再逐步增大。比如約瑟夫環(huán)先用n等于5、m等于2跑一遍手動(dòng)推演結(jié)果確認(rèn)代碼輸出和手算一致。然后再用n等于7、m等于3驗(yàn)證。如果小數(shù)據(jù)量下結(jié)果正確大數(shù)據(jù)量下出錯(cuò)那基本是邊界條件或者內(nèi)存問題如果小數(shù)據(jù)量下就錯(cuò)了那就是核心邏輯有問題。這個(gè)排查思路幫我省了很多時(shí)間。最后說(shuō)一個(gè)關(guān)于模板類的小坑。上面的順序隊(duì)列和鏈?zhǔn)疥?duì)列都用了模板如果你把類的聲明和實(shí)現(xiàn)分開寫在.h和.cpp文件里鏈接時(shí)會(huì)報(bào)未定義引用的錯(cuò)誤。原因是模板的實(shí)例化需要在編譯期完成編譯器看不到實(shí)現(xiàn)就無(wú)法生成代碼。解決辦法有兩個(gè)把實(shí)現(xiàn)也寫在頭文件里或者在.cpp文件末尾顯式實(shí)例化你需要的類型。我一般直接把實(shí)現(xiàn)寫在頭文件里省事。代碼這東西看一遍和寫一遍完全是兩回事。順序隊(duì)列的取模、鏈?zhǔn)疥?duì)列的指針、約瑟夫環(huán)的邊界每一個(gè)我都建議你親手敲一遍故意改錯(cuò)幾個(gè)地方看看會(huì)出什么現(xiàn)象。比如把(rear 1) % capacity的括號(hào)去掉把出隊(duì)時(shí)的rear nullptr刪掉把約瑟夫環(huán)的count % m改成count m跑一下看看結(jié)果有什么變化。這種故意犯錯(cuò)再修復(fù)的練習(xí)方式比照著正確代碼抄一遍有效得多。 順序隊(duì)列、鏈?zhǔn)疥?duì)列與約瑟夫環(huán)的C++實(shí)現(xiàn)與避坑指南
隊(duì)列這個(gè)結(jié)構(gòu)剛學(xué)數(shù)據(jù)結(jié)構(gòu)那會(huì)兒我覺得它比棧簡(jiǎn)單——不就是先進(jìn)先出嘛能有多難。結(jié)果第一次用數(shù)組手寫循環(huán)隊(duì)列被取模運(yùn)算繞得頭暈第一次用鏈表實(shí)現(xiàn)隊(duì)列指針操作寫反了導(dǎo)致內(nèi)存泄漏第一次做約瑟夫環(huán)用數(shù)組模擬報(bào)數(shù)邊界條件調(diào)了整整一個(gè)下午。這三個(gè)東西單獨(dú)拎出來(lái)都不算復(fù)雜但放在一起恰好覆蓋了線性結(jié)構(gòu)里最核心的幾類問題連續(xù)存儲(chǔ)與離散存儲(chǔ)的取舍、循環(huán)利用空間的技巧、以及用數(shù)據(jù)結(jié)構(gòu)解決經(jīng)典數(shù)學(xué)問題的建模思路。下面我就按自己踩坑的順序把順序隊(duì)列、鏈?zhǔn)疥?duì)列和約瑟夫環(huán)的C實(shí)現(xiàn)從頭到尾捋一遍代碼全部實(shí)測(cè)可跑關(guān)鍵位置我會(huì)解釋為什么這么寫而不是那么寫。1. 為什么隊(duì)列值得單獨(dú)花時(shí)間啃很多人學(xué)數(shù)據(jù)結(jié)構(gòu)有個(gè)誤區(qū)覺得隊(duì)列太簡(jiǎn)單看一眼就跳過去把精力全砸在樹和圖上面。我當(dāng)初也這么想直到后來(lái)做項(xiàng)目時(shí)遇到一個(gè)消息緩沖的需求才發(fā)現(xiàn)自己對(duì)隊(duì)列的理解全是漏洞。隊(duì)列的本質(zhì)是受限的線性表——只允許在一端插入另一端刪除。這個(gè)限制看起來(lái)是閹割了線性表的能力但實(shí)際上它帶來(lái)的語(yǔ)義非常明確先來(lái)的先被處理。這個(gè)語(yǔ)義在操作系統(tǒng)調(diào)度、網(wǎng)絡(luò)數(shù)據(jù)包緩沖、打印任務(wù)排隊(duì)、廣度優(yōu)先搜索等場(chǎng)景里反復(fù)出現(xiàn)。你如果只是背下來(lái)先進(jìn)先出四個(gè)字遇到具體問題照樣寫不對(duì)。順序隊(duì)列和鏈?zhǔn)疥?duì)列解決的是同一個(gè)問題但底層存儲(chǔ)方式完全不同。順序隊(duì)列用一段連續(xù)內(nèi)存靠?jī)蓚€(gè)下標(biāo)front和rear標(biāo)記隊(duì)頭和隊(duì)尾鏈?zhǔn)疥?duì)列用離散節(jié)點(diǎn)靠指針串聯(lián)。兩者各有各的坑順序隊(duì)列如果不做循環(huán)處理會(huì)出現(xiàn)假溢出——明明數(shù)組前面有空位但因?yàn)閞ear已經(jīng)到頭了新元素就是插不進(jìn)去鏈?zhǔn)疥?duì)列則要小心指針操作順序?qū)懛匆徊骄褪莾?nèi)存泄漏或者段錯(cuò)誤。約瑟夫環(huán)則是隊(duì)列的一個(gè)經(jīng)典應(yīng)用場(chǎng)景。問題描述很簡(jiǎn)單n個(gè)人圍成一圈從第一個(gè)人開始報(bào)數(shù)報(bào)到m的人出列然后從下一個(gè)人繼續(xù)報(bào)數(shù)直到所有人出列。用隊(duì)列來(lái)模擬這個(gè)過程非常自然——每次把隊(duì)頭元素移到隊(duì)尾相當(dāng)于跳過一個(gè)人報(bào)到m時(shí)直接出隊(duì)相當(dāng)于淘汰一個(gè)人。但真正寫起來(lái)邊界條件、報(bào)數(shù)起點(diǎn)、剩余人數(shù)的處理每一個(gè)都可能讓你調(diào)試半天。我下面會(huì)先講順序隊(duì)列的循環(huán)實(shí)現(xiàn)再講鏈?zhǔn)疥?duì)列的指針操作最后用隊(duì)列思路解約瑟夫環(huán)。每一部分都會(huì)給出完整代碼、關(guān)鍵邏輯解釋以及我在實(shí)際調(diào)試中總結(jié)的注意事項(xiàng)。2. 順序隊(duì)列的循環(huán)數(shù)組實(shí)現(xiàn)與假溢出陷阱2.1 順序隊(duì)列的基本結(jié)構(gòu)設(shè)計(jì)順序隊(duì)列最直覺的做法是開一個(gè)固定大小的數(shù)組用front記錄隊(duì)頭位置用rear記錄隊(duì)尾位置。入隊(duì)時(shí)把元素放到rear位置然后rear加一出隊(duì)時(shí)取走front位置的元素然后front加一。空隊(duì)列的條件是front等于rear。這個(gè)設(shè)計(jì)在元素只進(jìn)不出的情況下沒問題但一旦有出隊(duì)操作front就會(huì)往后移動(dòng)前面空出來(lái)的位置就永遠(yuǎn)浪費(fèi)了。比如數(shù)組大小是5你入隊(duì)5個(gè)元素rear到了5越界此時(shí)出隊(duì)2個(gè)元素front變成2數(shù)組下標(biāo)0和1的位置空著但rear已經(jīng)不能再加了。這就是假溢出——不是真的沒空間而是空間沒有被循環(huán)利用。解決辦法是把數(shù)組在邏輯上彎成一個(gè)環(huán)。當(dāng)rear到達(dá)數(shù)組末尾時(shí)如果前面還有空位就讓它繞回到下標(biāo)0繼續(xù)存放。實(shí)現(xiàn)上就是每次移動(dòng)下標(biāo)時(shí)做一次取模運(yùn)算rear (rear 1) % capacity。這樣數(shù)組的物理存儲(chǔ)還是線性的但邏輯上變成了循環(huán)的。這里有一個(gè)關(guān)鍵細(xì)節(jié)如何區(qū)分隊(duì)空和隊(duì)滿。如果不做特殊處理隊(duì)空時(shí)front等于rear隊(duì)滿時(shí)front也等于rear因?yàn)閞ear繞了一圈追上了front兩者條件沖突。常見的解決方案有三種犧牲一個(gè)存儲(chǔ)單元隊(duì)滿的條件變成(rear 1) % capacity front也就是說(shuō)當(dāng)rear的下一個(gè)位置是front時(shí)就算滿實(shí)際可用容量是capacity減一。增加一個(gè)size變量記錄當(dāng)前元素個(gè)數(shù)隊(duì)空時(shí)size為0隊(duì)滿時(shí)size等于capacity判斷簡(jiǎn)單直接。增加一個(gè)tag標(biāo)記記錄最后一次操作是入隊(duì)還是出隊(duì)配合front和rear判斷。我個(gè)人最推薦第二種——加一個(gè)size變量。原因很簡(jiǎn)單代碼可讀性最好不需要在腦子里繞取模邏輯而且實(shí)際項(xiàng)目中隊(duì)列的容量通常不會(huì)卡到極限多一個(gè)int變量的開銷完全可以忽略。下面給出的實(shí)現(xiàn)就用這種方式。2.2 循環(huán)隊(duì)列的完整C實(shí)現(xiàn)#include iostream using namespace std; templatetypename T class CircularQueue { private: T* data; // 動(dòng)態(tài)數(shù)組 int capacity; // 容量 int front; // 隊(duì)頭下標(biāo) int rear; // 隊(duì)尾下標(biāo)下一個(gè)入隊(duì)位置 int count; // 當(dāng)前元素個(gè)數(shù) public: CircularQueue(int cap 10) { capacity cap; data new T[capacity]; front 0; rear 0; count 0; } ~CircularQueue() { delete[] data; } bool isEmpty() const { return count 0; } bool isFull() const { return count capacity; } int size() const { return count; } bool enqueue(const T value) { if (isFull()) { return false; // 隊(duì)列已滿入隊(duì)失敗 } data[rear] value; rear (rear 1) % capacity; count; return true; } bool dequeue(T value) { if (isEmpty()) { return false; // 隊(duì)列為空出隊(duì)失敗 } value data[front]; front (front 1) % capacity; count--; return true; } bool getFront(T value) const { if (isEmpty()) { return false; } value data[front]; return true; } void print() const { if (isEmpty()) { cout 隊(duì)列為空 endl; return; } cout 隊(duì)列元素: ; int idx front; for (int i 0; i count; i) { cout data[idx] ; idx (idx 1) % capacity; } cout endl; } };這段代碼有幾個(gè)地方值得展開說(shuō)。為什么用模板隊(duì)列里存什么類型的數(shù)據(jù)是不確定的可能是int、string也可能是自定義的結(jié)構(gòu)體。用模板可以讓同一份代碼適配所有類型避免為每種類型重復(fù)寫一遍。如果你暫時(shí)不熟悉模板把templatetypename T去掉把所有T換成int邏輯完全一樣。為什么用動(dòng)態(tài)數(shù)組而不是固定大小數(shù)組固定大小數(shù)組在編譯期就確定了容量不夠靈活。用new T[capacity]在堆上分配內(nèi)存容量可以在構(gòu)造時(shí)指定用完之后在析構(gòu)函數(shù)里delete[]釋放。這里要注意如果是存自定義類型T需要有無(wú)參構(gòu)造函數(shù)或者你需要在分配時(shí)做額外處理不過對(duì)于基礎(chǔ)類型和標(biāo)準(zhǔn)庫(kù)類型都沒問題。入隊(duì)和出隊(duì)的返回值設(shè)計(jì)我讓enqueue和dequeue返回bool表示操作是否成功。這樣做的好處是調(diào)用方可以明確知道操作結(jié)果而不是默默失敗。有些教材的實(shí)現(xiàn)直接返回void隊(duì)列滿時(shí)什么都不做調(diào)用方根本不知道數(shù)據(jù)有沒有進(jìn)去。實(shí)際項(xiàng)目中這種沉默失敗是災(zāi)難性的。取模運(yùn)算的位置rear (rear 1) % capacity這行代碼是循環(huán)隊(duì)列的核心。當(dāng)rear等于capacity減一時(shí)加一變成capacity取模后變成0正好繞回?cái)?shù)組開頭。front的移動(dòng)同理。你可以手動(dòng)模擬一下capacity為5rear從0開始依次變成1、2、3、4、0、1……永遠(yuǎn)不會(huì)越界。2.3 實(shí)測(cè)中容易踩的三個(gè)坑第一個(gè)坑取模運(yùn)算的優(yōu)先級(jí)。C中%的優(yōu)先級(jí)和*、/同級(jí)高于和-。所以rear 1 % capacity會(huì)被解析成rear (1 % capacity)結(jié)果完全錯(cuò)誤。必須寫成(rear 1) % capacity。我當(dāng)初就是因?yàn)樯賹懥艘粚?duì)括號(hào)調(diào)試了半個(gè)小時(shí)才發(fā)現(xiàn)問題。第二個(gè)坑遍歷隊(duì)列時(shí)的下標(biāo)處理。因?yàn)殛?duì)列是循環(huán)的不能簡(jiǎn)單地從front循環(huán)到rear因?yàn)閞ear可能小于front。正確的做法是用count控制循環(huán)次數(shù)每次下標(biāo)加一后取模。上面print函數(shù)就是這么寫的。如果你用for (int i front; i ! rear; i (i 1) % capacity)也可以但要注意隊(duì)列滿時(shí)front等于rear這個(gè)循環(huán)一次都不會(huì)執(zhí)行需要額外處理。第三個(gè)坑拷貝構(gòu)造和賦值運(yùn)算符。上面的類用了動(dòng)態(tài)內(nèi)存分配如果直接拷貝對(duì)象兩個(gè)對(duì)象會(huì)共享同一塊內(nèi)存析構(gòu)時(shí)就會(huì)double free。正確的做法是實(shí)現(xiàn)拷貝構(gòu)造函數(shù)和賦值運(yùn)算符深拷貝或者用std::vector代替裸指針。為了代碼簡(jiǎn)潔我這里沒有展開但你在實(shí)際使用中一定要注意。如果只是局部使用、不涉及對(duì)象拷貝問題不大一旦要把隊(duì)列作為參數(shù)傳遞或者放入容器就必須處理這個(gè)問題。提示如果你用的是C11及以上標(biāo)準(zhǔn)可以用std::unique_ptrT[]來(lái)管理數(shù)組內(nèi)存這樣連析構(gòu)函數(shù)都不用寫了而且自動(dòng)禁止拷貝避免誤用。3. 鏈?zhǔn)疥?duì)列的指針操作與邊界處理3.1 鏈?zhǔn)疥?duì)列的節(jié)點(diǎn)設(shè)計(jì)與頭尾指針順序隊(duì)列的容量是固定的一旦滿了就沒法再入隊(duì)。鏈?zhǔn)疥?duì)列沒有這個(gè)問題——每個(gè)元素是一個(gè)獨(dú)立的節(jié)點(diǎn)用指針串聯(lián)起來(lái)理論上只要內(nèi)存夠就可以一直入隊(duì)。鏈?zhǔn)疥?duì)列需要維護(hù)兩個(gè)指針front指向隊(duì)頭節(jié)點(diǎn)rear指向隊(duì)尾節(jié)點(diǎn)。入隊(duì)在rear后面接一個(gè)新節(jié)點(diǎn)出隊(duì)刪除front指向的節(jié)點(diǎn)。這里有一個(gè)設(shè)計(jì)選擇要不要帶頭節(jié)點(diǎn)。帶頭節(jié)點(diǎn)的意思是front指向一個(gè)不存數(shù)據(jù)的啞節(jié)點(diǎn)真正的隊(duì)頭元素是front-next。帶頭的好處是入隊(duì)和出隊(duì)的代碼可以統(tǒng)一處理不需要單獨(dú)判斷隊(duì)列是否為空。不帶頭的代碼更直觀但空隊(duì)列時(shí)插入第一個(gè)元素需要特殊處理。我兩種都寫過個(gè)人更傾向于不帶頭節(jié)點(diǎn)因?yàn)榇a更短邏輯更直接。但如果你追求代碼的對(duì)稱性和統(tǒng)一性帶頭節(jié)點(diǎn)也是很好的選擇。下面給出的實(shí)現(xiàn)不帶頭節(jié)點(diǎn)。#include iostream using namespace std; templatetypename T struct Node { T data; Node* next; Node(const T d) : data(d), next(nullptr) {} }; templatetypename T class LinkedQueue { private: NodeT* front; // 隊(duì)頭指針 NodeT* rear; // 隊(duì)尾指針 int count; // 元素個(gè)數(shù) public: LinkedQueue() : front(nullptr), rear(nullptr), count(0) {} ~LinkedQueue() { while (front ! nullptr) { NodeT* temp front; front front-next; delete temp; } } bool isEmpty() const { return front nullptr; } int size() const { return count; } void enqueue(const T value) { NodeT* newNode new NodeT(value); if (isEmpty()) { front rear newNode; } else { rear-next newNode; rear newNode; } count; } bool dequeue(T value) { if (isEmpty()) { return false; } value front-data; NodeT* temp front; front front-next; if (front nullptr) { rear nullptr; // 隊(duì)列變空rear也要置空 } delete temp; count--; return true; } bool getFront(T value) const { if (isEmpty()) { return false; } value front-data; return true; } void print() const { if (isEmpty()) { cout 隊(duì)列為空 endl; return; } cout 隊(duì)列元素: ; NodeT* cur front; while (cur ! nullptr) { cout cur-data ; cur cur-next; } cout endl; } };3.2 入隊(duì)和出隊(duì)的指針變化過程鏈?zhǔn)疥?duì)列的入隊(duì)操作分兩種情況。如果隊(duì)列為空新節(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾所以front rear newNode。如果隊(duì)列不為空把新節(jié)點(diǎn)接到rear的后面然后更新rear指向新節(jié)點(diǎn)。注意這里不能先更新rear再連接否則就找不到原來(lái)的隊(duì)尾了。順序必須是先rear-next newNode再rear newNode。出隊(duì)操作也分兩種情況。如果出隊(duì)后隊(duì)列變空f(shuō)ront變成了nullptr必須把rear也置為nullptr。這一步非常容易漏掉。如果你漏了rear會(huì)指向一個(gè)已經(jīng)被delete的節(jié)點(diǎn)下次入隊(duì)時(shí)rear-next newNode就會(huì)訪問已釋放的內(nèi)存程序可能崩潰或者產(chǎn)生不可預(yù)期的行為。我當(dāng)初就是因?yàn)槁┝诉@一行程序在小數(shù)據(jù)量下運(yùn)行正常一旦數(shù)據(jù)量大了就隨機(jī)崩潰排查了很久才定位到。內(nèi)存釋放的順序出隊(duì)時(shí)先用temp保存front然后front后移最后delete temp。順序不能反——如果先delete front再訪問front-next就是訪問已釋放內(nèi)存。這個(gè)錯(cuò)誤在初學(xué)者代碼里非常常見。析構(gòu)函數(shù)的實(shí)現(xiàn)析構(gòu)時(shí)需要遍歷整個(gè)鏈表逐個(gè)delete節(jié)點(diǎn)。注意在delete當(dāng)前節(jié)點(diǎn)之前要先把front移到下一個(gè)節(jié)點(diǎn)否則就找不到后續(xù)節(jié)點(diǎn)了。上面的析構(gòu)函數(shù)就是這么寫的。3.3 鏈?zhǔn)疥?duì)列相比順序隊(duì)列的取舍鏈?zhǔn)疥?duì)列和順序隊(duì)列沒有絕對(duì)的優(yōu)劣關(guān)鍵看使用場(chǎng)景。我整理了一個(gè)對(duì)比表格對(duì)比維度順序隊(duì)列循環(huán)數(shù)組鏈?zhǔn)疥?duì)列內(nèi)存分配一次性分配連續(xù)內(nèi)存每次入隊(duì)動(dòng)態(tài)分配節(jié)點(diǎn)容量限制固定滿了無(wú)法入隊(duì)理論上無(wú)限制受內(nèi)存約束緩存友好度高連續(xù)內(nèi)存訪問快低節(jié)點(diǎn)分散在堆上入隊(duì)時(shí)間復(fù)雜度O(1)O(1)但有new操作開銷出隊(duì)時(shí)間復(fù)雜度O(1)O(1)但有delete操作開銷內(nèi)存開銷僅數(shù)組本身每個(gè)節(jié)點(diǎn)多一個(gè)指針域適用場(chǎng)景容量可預(yù)估、追求性能容量不確定、頻繁增刪如果你的隊(duì)列容量可以預(yù)估比如做嵌入式開發(fā)時(shí)緩沖區(qū)大小固定順序隊(duì)列更合適——沒有動(dòng)態(tài)內(nèi)存分配不會(huì)產(chǎn)生內(nèi)存碎片訪問速度也更快。如果容量完全不可預(yù)測(cè)比如處理網(wǎng)絡(luò)請(qǐng)求鏈?zhǔn)疥?duì)列更靈活。還有一個(gè)實(shí)際因素動(dòng)態(tài)內(nèi)存分配的開銷。每次入隊(duì)都new一個(gè)節(jié)點(diǎn)每次出隊(duì)都delete一個(gè)節(jié)點(diǎn)在高頻場(chǎng)景下這個(gè)開銷不可忽視。有些高性能場(chǎng)景會(huì)用內(nèi)存池來(lái)優(yōu)化預(yù)先分配一批節(jié)點(diǎn)循環(huán)使用避免頻繁的系統(tǒng)調(diào)用。不過這屬于進(jìn)階優(yōu)化初學(xué)階段先把基礎(chǔ)實(shí)現(xiàn)搞扎實(shí)。注意鏈?zhǔn)疥?duì)列的enqueue操作如果new失敗內(nèi)存耗盡會(huì)拋出std::bad_alloc異常。在資源受限的環(huán)境下你可能需要捕獲這個(gè)異常并做降級(jí)處理而不是讓程序直接崩潰。4. 約瑟夫環(huán)的隊(duì)列建模與模擬實(shí)現(xiàn)4.1 約瑟夫環(huán)問題的本質(zhì)拆解約瑟夫環(huán)的描述有很多版本核心邏輯是一樣的n個(gè)人圍成一圈從某個(gè)人開始報(bào)數(shù)每報(bào)到m的人出列然后從出列者的下一個(gè)人重新開始報(bào)數(shù)直到所有人出列。要求輸出出列的順序。這個(gè)問題的數(shù)學(xué)模型其實(shí)是一個(gè)遞推問題有O(n)的數(shù)學(xué)解法。但用隊(duì)列來(lái)模擬是最直觀的也是理解隊(duì)列應(yīng)用的絕佳案例。用隊(duì)列模擬的思路是把n個(gè)人依次入隊(duì)。從隊(duì)頭開始每次把隊(duì)頭元素取出并重新入隊(duì)到隊(duì)尾相當(dāng)于這個(gè)人報(bào)數(shù)不是m跳過。當(dāng)報(bào)數(shù)到m時(shí)隊(duì)頭元素直接出隊(duì)不再入隊(duì)這個(gè)人被淘汰。重復(fù)上述過程直到隊(duì)列為空。這里的關(guān)鍵是報(bào)數(shù)計(jì)數(shù)器的維護(hù)。你可以用一個(gè)變量從1開始計(jì)數(shù)每處理一個(gè)人就加一當(dāng)計(jì)數(shù)器等于m時(shí)執(zhí)行淘汰并重置計(jì)數(shù)器為1。也可以每輪固定移動(dòng)m減一次然后淘汰隊(duì)頭。兩種寫法等價(jià)但后者代碼更簡(jiǎn)潔。4.2 用鏈?zhǔn)疥?duì)列模擬約瑟夫環(huán)#include iostream using namespace std; // 復(fù)用上面的LinkedQueue這里簡(jiǎn)化為int類型 void josephus(int n, int m) { LinkedQueueint q; for (int i 1; i n; i) { q.enqueue(i); } cout 出列順序: ; int count 0; // 已出列人數(shù) while (!q.isEmpty()) { int cur; q.dequeue(cur); count; if (count % m 0) { // 報(bào)到m出列 cout cur ; } else { // 未報(bào)到m重新入隊(duì) q.enqueue(cur); } } cout endl; } int main() { int n 7, m 3; cout n n , m m endl; josephus(n, m); return 0; }運(yùn)行結(jié)果出列順序: 3 6 2 7 5 1 4。這個(gè)實(shí)現(xiàn)非常簡(jiǎn)潔但有幾個(gè)細(xì)節(jié)值得注意。為什么用count % m而不是維護(hù)一個(gè)獨(dú)立的報(bào)數(shù)變量count記錄的是當(dāng)前處理到第幾個(gè)人包括已經(jīng)出列和重新入隊(duì)的每處理一個(gè)人count加一。當(dāng)count能被m整除時(shí)說(shuō)明當(dāng)前這個(gè)人正好是第m個(gè)報(bào)數(shù)的應(yīng)該出列。這種寫法避免了在出列后重置計(jì)數(shù)器的操作邏輯更統(tǒng)一。出列后為什么不需要特殊處理因?yàn)槌隽械娜酥苯訌年?duì)列中移除了隊(duì)列的front自動(dòng)指向下一個(gè)人下一輪循環(huán)自然從下一個(gè)人開始報(bào)數(shù)。這正是隊(duì)列先進(jìn)先出特性帶來(lái)的便利——你不需要手動(dòng)維護(hù)下一個(gè)人是誰(shuí)。時(shí)間復(fù)雜度分析每處理一個(gè)人要么出列O(1)要么重新入隊(duì)O(1)?？偣蔡幚淼娜舜螖?shù)是n乘以m因?yàn)槊刻蕴粋€(gè)人需要跳過m減一個(gè)人所以時(shí)間復(fù)雜度是O(n*m)。當(dāng)n和m都很大時(shí)這個(gè)模擬會(huì)非常慢。比如n等于一百萬(wàn)、m等于一百萬(wàn)運(yùn)算量是萬(wàn)億級(jí)別肯定超時(shí)。這時(shí)候就需要用數(shù)學(xué)遞推法把時(shí)間復(fù)雜度降到O(n)。4.3 數(shù)學(xué)遞推法的思路與對(duì)比數(shù)學(xué)遞推法的核心是找到出列編號(hào)的遞推關(guān)系。假設(shè)f(n, m)表示n個(gè)人報(bào)數(shù)m時(shí)最后剩下的人或者第一個(gè)出列的人的編號(hào)。經(jīng)過推導(dǎo)可以得到遞推公式f(n, m) (f(n-1, m) m) % n其中f(1, m)等于0假設(shè)編號(hào)從0開始。這個(gè)公式的含義是n個(gè)人問題的解等于n減一個(gè)人問題的解加上m再對(duì)n取模。你可以這樣理解淘汰一個(gè)人之后剩下n減一個(gè)人重新圍成一圈但起點(diǎn)變了需要做一個(gè)偏移映射。用遞推法求第一個(gè)出列的人int josephusMath(int n, int m) { int result 0; // f(1, m) 0 for (int i 2; i n; i) { result (result m) % i; } return result 1; // 轉(zhuǎn)換回1-based編號(hào) }這個(gè)算法的時(shí)間復(fù)雜度是O(n)空間復(fù)雜度是O(1)比隊(duì)列模擬快得多。但它只能求出最后剩下的人如果要輸出完整的出列順序還是得用模擬法或者更復(fù)雜的數(shù)學(xué)方法。兩種方法的適用場(chǎng)景如果只需要知道最后誰(shuí)留下用數(shù)學(xué)遞推法如果需要完整的出列順序用隊(duì)列模擬法。在實(shí)際面試中面試官可能會(huì)先讓你用模擬法寫然后問你有沒有更優(yōu)的解法這時(shí)候數(shù)學(xué)遞推法就是加分項(xiàng)。提示約瑟夫環(huán)的數(shù)學(xué)解法有多種變體有的求最后剩下的人有的求第k個(gè)出列的人。遞推公式的初始條件和邊界處理略有不同使用前一定要確認(rèn)清楚問題的具體定義。5. 三個(gè)實(shí)現(xiàn)串起來(lái)看存儲(chǔ)方式如何決定代碼形態(tài)把順序隊(duì)列、鏈?zhǔn)疥?duì)列和約瑟夫環(huán)放在一起看會(huì)發(fā)現(xiàn)一個(gè)有意思的規(guī)律底層存儲(chǔ)方式直接決定了代碼的形態(tài)和容易出錯(cuò)的地方。順序隊(duì)列的代碼里到處都是取模運(yùn)算因?yàn)槟阋谶壿嬌习丫€性數(shù)組彎成環(huán)。取模運(yùn)算的優(yōu)先級(jí)、邊界值的處理、隊(duì)空隊(duì)滿的判斷這些坑都源于用連續(xù)內(nèi)存模擬循環(huán)這個(gè)核心設(shè)計(jì)。你如果理解了這一點(diǎn)就能預(yù)判哪些地方容易出問題——所有涉及下標(biāo)移動(dòng)的地方都要檢查取模所有涉及front和rear比較的地方都要考慮繞圈的情況。鏈?zhǔn)疥?duì)列的代碼里到處都是指針操作因?yàn)槟阋謩?dòng)管理節(jié)點(diǎn)的連接和釋放。指針操作順序、空隊(duì)列的特殊處理、內(nèi)存泄漏的防范這些坑都源于用離散節(jié)點(diǎn)維護(hù)順序關(guān)系這個(gè)核心設(shè)計(jì)。你如果理解了這一點(diǎn)就能預(yù)判哪些地方容易出問題——所有涉及指針賦值的地方都要考慮順序所有涉及節(jié)點(diǎn)刪除的地方都要檢查是否有其他指針還指向它。約瑟夫環(huán)的代碼則體現(xiàn)了數(shù)據(jù)結(jié)構(gòu)選擇對(duì)問題建模的影響。用隊(duì)列來(lái)模擬代碼不到二十行邏輯清晰到幾乎不需要注釋。如果用數(shù)組來(lái)模擬你需要手動(dòng)維護(hù)當(dāng)前報(bào)數(shù)位置、標(biāo)記已出列的人、處理數(shù)組越界繞回代碼量至少翻倍而且容易出錯(cuò)。這就是數(shù)據(jù)結(jié)構(gòu)的價(jià)值——選對(duì)了結(jié)構(gòu)問題本身就變簡(jiǎn)單了。我在實(shí)際編碼中總結(jié)了一個(gè)判斷原則如果問題的核心操作是在一端加入、在另一端刪除就用隊(duì)列如果核心操作是在一端加入、在同一端刪除就用棧如果核心操作是隨機(jī)訪問任意位置就用數(shù)組或鏈表。約瑟夫環(huán)的核心操作是跳過一個(gè)人從隊(duì)頭移到隊(duì)尾和淘汰一個(gè)人從隊(duì)頭刪除正好符合隊(duì)列的操作模式所以隊(duì)列是最自然的選擇。再補(bǔ)充一個(gè)實(shí)際調(diào)試中的經(jīng)驗(yàn)先用小數(shù)據(jù)量驗(yàn)證邏輯再逐步增大。比如約瑟夫環(huán)先用n等于5、m等于2跑一遍手動(dòng)推演結(jié)果確認(rèn)代碼輸出和手算一致。然后再用n等于7、m等于3驗(yàn)證。如果小數(shù)據(jù)量下結(jié)果正確大數(shù)據(jù)量下出錯(cuò)那基本是邊界條件或者內(nèi)存問題如果小數(shù)據(jù)量下就錯(cuò)了那就是核心邏輯有問題。這個(gè)排查思路幫我省了很多時(shí)間。最后說(shuō)一個(gè)關(guān)于模板類的小坑。上面的順序隊(duì)列和鏈?zhǔn)疥?duì)列都用了模板如果你把類的聲明和實(shí)現(xiàn)分開寫在.h和.cpp文件里鏈接時(shí)會(huì)報(bào)未定義引用的錯(cuò)誤。原因是模板的實(shí)例化需要在編譯期完成編譯器看不到實(shí)現(xiàn)就無(wú)法生成代碼。解決辦法有兩個(gè)把實(shí)現(xiàn)也寫在頭文件里或者在.cpp文件末尾顯式實(shí)例化你需要的類型。我一般直接把實(shí)現(xiàn)寫在頭文件里省事。代碼這東西看一遍和寫一遍完全是兩回事。順序隊(duì)列的取模、鏈?zhǔn)疥?duì)列的指針、約瑟夫環(huán)的邊界每一個(gè)我都建議你親手敲一遍故意改錯(cuò)幾個(gè)地方看看會(huì)出什么現(xiàn)象。比如把(rear 1) % capacity的括號(hào)去掉把出隊(duì)時(shí)的rear nullptr刪掉把約瑟夫環(huán)的count % m改成count m跑一下看看結(jié)果有什么變化。這種故意犯錯(cuò)再修復(fù)的練習(xí)方式比照著正確代碼抄一遍有效得多。