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