我見(jiàn)過(guò)太多人把 STL 里的stack和queue當(dāng)成“裝數(shù)據(jù)的盒子”push 一下、pop 一下用起來(lái)比誰(shuí)都熟?？梢坏┍粏?wèn)到“這倆的底層到底是什么”“讓你自己實(shí)現(xiàn)一個(gè)能不能寫(xiě)出來(lái)”不少人就卡住了。原因其實(shí)很統(tǒng)一我們習(xí)慣了站在使用者的角度去看容器卻很少站到實(shí)現(xiàn)者的角度去思考它的內(nèi)存布局、邊界條件、生命周期管理。這個(gè)項(xiàng)目不復(fù)雜但很值得認(rèn)真做一遍——從一個(gè)空類開(kāi)始手寫(xiě) stack 和 queue 的全部關(guān)鍵操作把模板、動(dòng)態(tài)內(nèi)存、拷貝語(yǔ)義、邊界判斷這些東西一次性捋清楚。這篇文章就圍繞“從零實(shí)現(xiàn)”展開(kāi)。我會(huì)先從兩個(gè)容器的設(shè)計(jì)本質(zhì)上拆解思路再分別給出 stack 和 queue 的完整實(shí)現(xiàn)代碼配合測(cè)試和避坑經(jīng)驗(yàn)。不論你是準(zhǔn)備面試還是想把 STL 底層搞得更透這篇都適合你慢慢讀。1. 為什么要從零實(shí)現(xiàn) stack 和 queue1.1 先看清 STL 里的 stack/queue 到底是什么很多人對(duì)std::stack和std::queue有一個(gè)誤解認(rèn)為它們是獨(dú)立的數(shù)據(jù)結(jié)構(gòu)。實(shí)際上它們都是容器適配器container adapter。也就是說(shuō)它們本身不管理內(nèi)存也不存儲(chǔ)數(shù)據(jù)而是通過(guò)包裝另一個(gè)容器默認(rèn)是std::deque來(lái)提供受限的接口。std::stack只讓你操作棧頂push 從頂入、pop 從頂出、top 看棧頂。std::queue只讓你操作兩端push 從隊(duì)尾入、pop 從隊(duì)頭出、front 看隊(duì)頭、back 看隊(duì)尾。你看它們把底層容器的“自由度”砍掉了——deque 能提供隨機(jī)訪問(wèn)但 stack/queue 把這些能力鎖了起來(lái)只暴露出符合語(yǔ)義的那幾個(gè)操作。這是接口約束上的典型設(shè)計(jì)用最少的方法表達(dá)最清晰的數(shù)據(jù)結(jié)構(gòu)語(yǔ)義。從零實(shí)現(xiàn)的意義就在這里當(dāng)你自己動(dòng)手的時(shí)候你才會(huì)意識(shí)到實(shí)現(xiàn)一個(gè) stack 根本不需要從頭發(fā)明什么新東西——你只需要一個(gè)“能存東西、能按順序訪問(wèn)”的底層結(jié)構(gòu)然后把外部接口限制起來(lái)。這個(gè)“把底層容器封裝成語(yǔ)義明確的適配器”的思路比單純背幾個(gè)函數(shù)名重要得多。1.2 從零實(shí)現(xiàn)能換來(lái)什么收獲我之所以推薦你親手寫(xiě)一遍而不是直接打印源碼看是因?yàn)閷?xiě)的過(guò)程中你會(huì)被迫回答這幾類問(wèn)題內(nèi)存管理問(wèn)題棧的容量不夠了怎么辦是每次 push 都擴(kuò)容還是提前預(yù)留擴(kuò)容系數(shù)取多少生命周期問(wèn)題pop 之后被移除的元素它的析構(gòu)函數(shù)是否被調(diào)用了對(duì)象持有的資源有沒(méi)有真正釋放拷貝語(yǔ)義問(wèn)題容器被拷貝時(shí)是淺拷貝還是深拷貝如果直接復(fù)制指針兩份“獨(dú)立”的容器會(huì)不會(huì)在析構(gòu)時(shí)爭(zhēng)搶同一塊內(nèi)存邊界條件問(wèn)題空棧上調(diào)用 top 會(huì)發(fā)生什么隊(duì)列只有一個(gè)元素時(shí) pop會(huì)不會(huì)把隊(duì)尾指針弄丟只調(diào)用現(xiàn)成 API 的人是永遠(yuǎn)不會(huì)思考這些的。但如果你要寫(xiě)自己的容器這些問(wèn)題一個(gè)個(gè)都會(huì)冒出來(lái)。正因如此“從零實(shí)現(xiàn) stack/queue”才是一個(gè)性價(jià)比極高的練習(xí)項(xiàng)目——它不大但足夠的細(xì)節(jié)密度讓你把 C 的內(nèi)存和對(duì)象模型真正串起來(lái)。2. 整體設(shè)計(jì)思路適配器語(yǔ)義與底層容器的取舍2.1 第一步不是寫(xiě)代碼是列清楚操作清單動(dòng)手之前先明確目標(biāo)。一個(gè)合格的 stack 起碼要有這些操作操作含義復(fù)雜度push(const T)入棧在棧頂插入元素O(1) 攤還pop()出棧移除棧頂元素O(1)top()返回棧頂元素的引用O(1)empty()判斷棧是否為空O(1)size()返回棧中元素個(gè)數(shù)O(1)拷貝構(gòu)造/賦值深拷貝保證容器獨(dú)立O(n)析構(gòu)釋放所有資源O(n)queue 的操作類似但把 top 拆成了 front 和 back操作含義復(fù)雜度push(const T)入隊(duì)在隊(duì)尾插入元素O(1)pop()出隊(duì)移除隊(duì)頭元素O(1)front()返回隊(duì)頭元素的引用O(1)back()返回隊(duì)尾元素的引用O(1)empty()/size()判斷空、查數(shù)量O(1)把這些接口列出來(lái)再動(dòng)手后面寫(xiě)代碼時(shí)會(huì)省力很多。因?yàn)槟阒雷约涸趯?shí)現(xiàn)什么而不是“寫(xiě)一步看一步”。2.2 底層容器選型數(shù)組、鏈表還是分段連續(xù)stack 和 queue 的語(yǔ)義其實(shí)對(duì)底層結(jié)構(gòu)沒(méi)有硬性要求只要滿足兩端插入刪除的復(fù)雜度需求即可。常見(jiàn)的底層方案有四種底層方案入棧/入隊(duì)出棧/出隊(duì)內(nèi)存局部性擴(kuò)容代價(jià)實(shí)現(xiàn)復(fù)雜度動(dòng)態(tài)數(shù)組vector 式O(1) 攤還O(1)很好拷貝舊數(shù)據(jù)中等雙向鏈表list 式O(1)O(1)差無(wú)擴(kuò)容但每節(jié)點(diǎn)有指針開(kāi)銷較高環(huán)形緩沖區(qū)O(1) 攤還O(1)很好需重新排列數(shù)據(jù)高分段連續(xù)deque 式O(1) 攤還O(1)好不需要整體搬移非常高STL 默認(rèn)選擇deque核心原因是它能在兩端高效插入刪除同時(shí)內(nèi)存局部性又比鏈表好——擴(kuò)容時(shí)它不用像 vector 那樣搬移所有元素只需要新分配一段 buffer 并連接起來(lái)。這個(gè)設(shè)計(jì)精妙但實(shí)現(xiàn)起來(lái)非常復(fù)雜。從零實(shí)現(xiàn)的角度我建議分兩條路線stack 用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)和 vector 的內(nèi)存管理方式一致邏輯直觀擴(kuò)容時(shí)拷貝元素的機(jī)制也容易講清楚。queue 用鏈表實(shí)現(xiàn)同時(shí)我會(huì)在后面的章節(jié)額外講一下環(huán)形緩沖區(qū)的思路讓你看到第二種方案的優(yōu)缺點(diǎn)。這樣安排你既能看到“連續(xù)內(nèi)存”路徑的實(shí)現(xiàn)細(xì)節(jié)也能對(duì)比“節(jié)點(diǎn)式”結(jié)構(gòu)帶來(lái)的內(nèi)存管理差異。兩種結(jié)構(gòu)都過(guò)一遍手比只盯著一種強(qiáng)太多。2.3 模板設(shè)計(jì)從一開(kāi)始就支持泛型既然是模仿 STL模板是必須的。用模板的好處很直接一份代碼能承載 int、string、自定義對(duì)象等任意類型。類定義寫(xiě)成template typename T class MyStack { // ... };但這也帶來(lái)一些代價(jià)。比如某些類型沒(méi)有默認(rèn)構(gòu)造函數(shù)或者拷貝成本很高這些都會(huì)影響底層內(nèi)存管理策略的選擇。所以我會(huì)在實(shí)現(xiàn)時(shí)重點(diǎn)考慮“如何避免對(duì) T 的額外要求”。換句話說(shuō)只要 T 支持拷貝構(gòu)造和拷貝賦值我的容器就應(yīng)該能正常工作。另外一個(gè)細(xì)節(jié)成員命名。我習(xí)慣在成員變量后面加_后綴例如capacity_、size_用來(lái)區(qū)分形參和成員。這是很多 C 工程里的約定讓代碼一眼就能看出哪些是成員、哪些是局部變量。3. 從零實(shí)現(xiàn) stack完整代碼與關(guān)鍵操作拆解3.1 動(dòng)態(tài)數(shù)組版 MyStack 的整體框架我用動(dòng)態(tài)數(shù)組來(lái)實(shí)現(xiàn) stack。整體結(jié)構(gòu)是這樣的data_指向堆上數(shù)組的指針真正存儲(chǔ)元素的地方。capacity_當(dāng)前已經(jīng)分配的內(nèi)存能容納多少元素。size_棧里當(dāng)前有多少個(gè)元素。這三個(gè)成員構(gòu)成一個(gè)完整的動(dòng)態(tài)數(shù)組容器。size_永遠(yuǎn)小于等于capacity_當(dāng)兩者相等時(shí)下一次 push 必須擴(kuò)容。基礎(chǔ)版本如下#include iostream #include stdexcept template typename T class MyStack { private: T* data_; size_t capacity_; size_t size_; public: explicit MyStack(size_t cap 16) : data_(new T[cap]), capacity_(cap), size_(0) {} ~MyStack() { delete[] data_; } // 禁用拷貝先不后面會(huì)給出正確做法 MyStack(const MyStack) delete; MyStack operator(const MyStack) delete; void push(const T value) { if (size_ capacity_) { grow(); } data_[size_] value; } void pop() { if (empty()) { throw std::runtime_error(stack underflow: pop from empty stack); } --size_; } T top() { if (empty()) { throw std::runtime_error(stack empty: no top element); } return data_[size_ - 1]; } const T top() const { if (empty()) { throw std::runtime_error(stack empty: no top element); } return data_[size_ - 1]; } bool empty() const { return size_ 0; } size_t size() const { return size_; } private: void grow() { size_t new_capacity capacity_ * 2; T* new_data new T[new_capacity]; for (size_t i 0; i size_; i) { new_data[i] data_[i]; } delete[] data_; data_ new_data; capacity_ new_capacity; } };這段代碼把核心操作都實(shí)現(xiàn)了。注意幾個(gè)關(guān)鍵細(xì)節(jié)構(gòu)造函數(shù)里的explicit是為了避免隱式轉(zhuǎn)換。比如MyStackint s 100;這種寫(xiě)法可能會(huì)誤導(dǎo)讀者加上explicit之后必須寫(xiě)成MyStackint s(100);意圖更清晰。pop()只做了--size_沒(méi)有真正銷毀棧頂對(duì)象。原因很簡(jiǎn)單我們用new T[]分配數(shù)組時(shí)所有元素從一開(kāi)始就構(gòu)造好了數(shù)組不銷毀它們的生命周期就不會(huì)結(jié)束。減少size_只是把它們“遮蔽”起來(lái)后續(xù) push 時(shí)會(huì)用賦值運(yùn)算符覆蓋舊值。這種寫(xiě)法對(duì)常規(guī)類型完全沒(méi)問(wèn)題但嚴(yán)格意義上對(duì)象占用的資源沒(méi)有被提前釋放。我后面會(huì)給出更嚴(yán)格的實(shí)現(xiàn)。top()有 const 版本和非 const 版本。非 const 版本允許調(diào)用方修改棧頂元素const 版本用于只讀場(chǎng)景。這是 STL 中非常常見(jiàn)的雙版本模式。3.2 擴(kuò)容機(jī)制與拷貝語(yǔ)義的坑grow()里我選擇了capacity_ * 2也就是每次翻倍。為什么是 2 而不是別的數(shù)這里有一個(gè)攤還復(fù)雜度的經(jīng)典論證假設(shè)從 1 開(kāi)始按 2 倍擴(kuò)容到 n總共會(huì)拷貝1 2 4 ... n/2 n ≈ 2n次也就是說(shuō)push n 個(gè)元素的總拷貝量是 O(n)平均到每次 push 是 O(1)。如果按固定大小擴(kuò)容比如每次加 16那總拷貝量會(huì)變成 O(n2)平均成本就不是 O(1) 了。但拷貝構(gòu)造和賦值運(yùn)算符被我禁用 delete這意味著?？梢员粍?chuàng)建、使用、銷毀但不能被拷貝。這在功能上是不完整的。為什么我要先禁用因?yàn)槿绻苯邮褂媚J(rèn)的拷貝行為data_指針會(huì)被逐字節(jié)復(fù)制兩個(gè) MyStack 對(duì)象會(huì)指向同一塊內(nèi)存析構(gòu)時(shí)就會(huì)發(fā)生double free——同一塊內(nèi)存被釋放兩次程序直接崩潰。正確的做法是深拷貝?？截悩?gòu)造需要分配新內(nèi)存逐一復(fù)制元素賦值運(yùn)算符需要先處理“自賦值”和“異常安全”的問(wèn)題。一個(gè)常見(jiàn)的寫(xiě)法是copy-and-swap 慣用法#include algorithm template typename T class MyStack { private: T* data_; size_t capacity_; size_t size_; void swap(MyStack other) noexcept { std::swap(data_, other.data_); std::swap(capacity_, other.capacity_); std::swap(size_, other.size_); } public: MyStack(const MyStack other) : data_(new T[other.capacity_]), capacity_(other.capacity_), size_(other.size_) { for (size_t i 0; i size_; i) { data_[i] other.data_[i]; } } MyStack operator(MyStack other) { swap(other); return *this; } // 其余方法同上 };這里賦值運(yùn)算符的形參不是const MyStack而是直接按值傳MyStack other。這樣other是從實(shí)參拷貝出來(lái)的臨時(shí)對(duì)象swap 之后舊數(shù)據(jù)被裝進(jìn)了這個(gè)臨時(shí)對(duì)象函數(shù)結(jié)束時(shí)自動(dòng)析構(gòu)完成資源清理。如果實(shí)參拷貝過(guò)程中拋異常賦值操作就整體失敗原對(duì)象狀態(tài)不受影響。這就是 copy-and-swap 的優(yōu)雅之處用拷貝構(gòu)造來(lái)保證異常安全。3.3 進(jìn)階用 placement new 讓容器更嚴(yán)謹(jǐn)前面的實(shí)現(xiàn)雖然很好理解但有一個(gè)明顯的局限new T[cap]要求 T 必須支持默認(rèn)構(gòu)造。如果 T 沒(méi)有默認(rèn)構(gòu)造函數(shù)代碼就無(wú)法編譯。而且用賦值運(yùn)算符覆蓋舊值本質(zhì)上是對(duì)“活著的對(duì)象”進(jìn)行賦值而不是構(gòu)造新對(duì)象。更嚴(yán)謹(jǐn)?shù)淖龇ㄊ侵环峙鋬?nèi)存不構(gòu)造對(duì)象push 時(shí)用 placement new 構(gòu)造pop 時(shí)手動(dòng)調(diào)用析構(gòu)。關(guān)鍵代碼如下template typename T class MyStack { private: T* data_; size_t capacity_; size_t size_; void grow() { size_t new_capacity capacity_ * 2; T* new_data static_castT*(::operator new(sizeof(T) * new_capacity)); size_t i 0; try { for (; i size_; i) { new (new_data[i]) T(data_[i]); // 拷貝構(gòu)造而不是賦值 } } catch (...) { for (size_t j 0; j i; j) { new_data[j].~T(); } ::operator delete(new_data); throw; } for (size_t j 0; j size_; j) { data_[j].~T(); } ::operator delete(data_); data_ new_data; capacity_ new_capacity; } public: explicit MyStack(size_t cap 16) : data_(static_castT*(::operator new(sizeof(T) * cap))), capacity_(cap), size_(0) {} ~MyStack() { for (size_t i 0; i size_; i) { data_[i].~T(); } ::operator delete(data_); } void push(const T value) { if (size_ capacity_) { grow(); } new (data_[size_]) T(value); // placement new size_; } void pop() { if (empty()) { throw std::runtime_error(stack underflow); } --size_; data_[size_].~T(); // 手動(dòng)析構(gòu) } // top/empty/size 同前 };::operator new(sizeof(T) * n)只分配裸內(nèi)存不調(diào)用構(gòu)造函數(shù)new (data_[size_]) T(value)在指定位置上構(gòu)造對(duì)象data_[size_].~T()顯式調(diào)用析構(gòu)函數(shù)。這一套組合拳讓容器可以存放沒(méi)有默認(rèn)構(gòu)造函數(shù)的類型也讓 pop 真正釋放了對(duì)象持有的資源。代價(jià)是代碼復(fù)雜度明顯提高。我的建議是先把第一版搞懂、跑通再升級(jí)到這一版。學(xué)習(xí)路徑本身比直接抄一個(gè)“最強(qiáng)版本”更重要。3.4 測(cè)試 MyStack不只測(cè)功能更要測(cè)邊界寫(xiě)測(cè)試時(shí)不要只驗(yàn)證“能 push 能 pop”。真正的邊界測(cè)試長(zhǎng)這樣int main() { MyStackint stack; // 空棧狀態(tài)檢查 std::cout empty: stack.empty() std::endl; // 1 std::cout size: stack.size() std::endl; // 0 // 連續(xù)壓入觸發(fā)多次擴(kuò)容 for (int i 1; i 100; i) { stack.push(i); } std::cout after push 100: size stack.size() // 100 top stack.top() std::endl; // 100 // 邊 pop 邊看 top while (!stack.empty()) { int topVal stack.top(); stack.pop(); std::cout pop topVal std::endl; } // 空棧 top/pop 應(yīng)該拋異常 try { stack.pop(); } catch (const std::exception e) { std::cout caught: e.what() std::endl; } // 拷貝獨(dú)立性測(cè)試 MyStackint copy stack; // 空?？截?for (int i 0; i 5; i) { copy.push(i); } MyStackint assigned; assigned copy; assigned.top() 100; // 修改副本不影響原對(duì)象 std::cout copy top copy.top() assigned top assigned.top() std::endl; return 0; }跑起來(lái)之后重點(diǎn)觀察幾件事擴(kuò)容是否正常、pop 后 size 是否正確遞減、空棧異常是否被拋出、拷貝出來(lái)的棧是否和原棧完全獨(dú)立。這些測(cè)試點(diǎn)覆蓋了大部分實(shí)現(xiàn)里容易出 bug 的地方。4. 從零實(shí)現(xiàn) queue鏈表核心操作與環(huán)形緩沖區(qū)對(duì)比4.1 用鏈表實(shí)現(xiàn) queue兩個(gè)指針撐起全部操作queue 和 stack 最大的不同在于queue 需要兩端操作。stack 只需要操作棧頂一端但 queue 的 push 在隊(duì)尾、pop 在隊(duì)頭、front 要看隊(duì)頭、back 要看隊(duì)尾。如果我用動(dòng)態(tài)數(shù)組實(shí)現(xiàn) queue隊(duì)頭出隊(duì)時(shí)就會(huì)面臨“前面空出來(lái)但后面滿了”的尷尬局面必須引入環(huán)形緩沖或者移動(dòng)數(shù)據(jù)。而用鏈表實(shí)現(xiàn)情況會(huì)變得很簡(jiǎn)單每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和下一個(gè)節(jié)點(diǎn)的指針front_指向隊(duì)頭節(jié)點(diǎn)back_指向隊(duì)尾節(jié)點(diǎn)。push 時(shí)在鏈表尾部掛新節(jié)點(diǎn)pop 時(shí)摘掉頭節(jié)點(diǎn)。完整實(shí)現(xiàn)如下#include iostream #include stdexcept template typename T class MyQueue { private: struct Node { T data_; Node* next_; Node(const T data, Node* next nullptr) : data_(data), next_(next) {} }; Node* front_; Node* back_; size_t size_; public: MyQueue() : front_(nullptr), back_(nullptr), size_(0) {} ~MyQueue() { while (front_ ! nullptr) { Node* temp front_; front_ front_-next_; delete temp; } } MyQueue(const MyQueue other) : front_(nullptr), back_(nullptr), size_(0) { Node* cur other.front_; while (cur ! nullptr) { push(cur-data_); cur cur-next_; } } MyQueue operator(MyQueue other) { std::swap(front_, other.front_); std::swap(back_, other.back_); std::swap(size_, other.size_); return *this; } void push(const T value) { Node* new_node new Node(value); if (back_ nullptr) { front_ back_ new_node; } else { back_-next_ new_node; back_ new_node; } size_; } void pop() { if (empty()) { throw std::runtime_error(queue underflow: pop from empty queue); } Node* old_front front_; front_ front_-next_; if (front_ nullptr) { back_ nullptr; } delete old_front; --size_; } T front() { if (empty()) { throw std::runtime_error(queue empty: no front element); } return front_-data_; } const T front() const { if (empty()) { throw std::runtime_error(queue empty: no front element); } return front_-data_; } T back() { if (empty()) { throw std::runtime_error(queue empty: no back element); } return back_-data_; } const T back() const { if (empty()) { throw std::runtime_error(queue empty: no back element); } return back_-data_; } bool empty() const { return size_ 0; } size_t size() const { return size_; } };這個(gè)實(shí)現(xiàn)里最需要留意的地方是pop()中的這個(gè)細(xì)節(jié)front_ front_-next_; if (front_ nullptr) { back_ nullptr; }當(dāng)隊(duì)列只有一個(gè)元素時(shí)pop 之后front_變成nullptr但此時(shí)back_還指著那個(gè)已被刪除的節(jié)點(diǎn)。如果不把back_也置空下一次push時(shí)就會(huì)訪問(wèn)懸空指針程序崩潰。這個(gè) bug 非常經(jīng)典我見(jiàn)過(guò)不少人在手寫(xiě)隊(duì)列時(shí)翻車在這個(gè)地方。另外operator用了 copy-and-swap。MyQueue other按值傳入相當(dāng)于自動(dòng)完成了深拷貝三個(gè) swap 交換成員之后舊數(shù)據(jù)被臨時(shí)對(duì)象帶走了函數(shù)結(jié)束時(shí)自動(dòng)析構(gòu)。這樣寫(xiě)異常安全和自賦值問(wèn)題一次全解決。4.2 鏈表 vs 環(huán)形緩沖區(qū)兩種 queue 方案的深度對(duì)比鏈表方案最大的優(yōu)勢(shì)是實(shí)現(xiàn)直觀、節(jié)點(diǎn)生命周期清晰。每個(gè)節(jié)點(diǎn)獨(dú)立分配push 時(shí)創(chuàng)建新節(jié)點(diǎn)pop 時(shí)刪除舊節(jié)點(diǎn)不需要擔(dān)心擴(kuò)容和元素搬移。但它的缺點(diǎn)也很明顯每個(gè)節(jié)點(diǎn)都要通過(guò)new單獨(dú)分配內(nèi)存這些零散的堆分配導(dǎo)致內(nèi)存碎片化而且訪問(wèn)節(jié)點(diǎn)時(shí)的緩存局部性很差。當(dāng)隊(duì)列頻繁 push/pop 時(shí)每次都要 malloc/free性能會(huì)明顯下降。相比之下環(huán)形緩沖區(qū)用一個(gè)連續(xù)數(shù)組模擬隊(duì)列head_和tail_兩個(gè)索引在數(shù)組里“轉(zhuǎn)圈”。核心思路是push 時(shí)把元素寫(xiě)到tail_然后tail_ (tail_ 1) % capacity_pop 時(shí)讀取head_然后head_ (head_ 1) % capacity_。這個(gè)取模操作讓索引到數(shù)組末尾時(shí)自動(dòng)回到開(kāi)頭形成“環(huán)”。環(huán)形緩沖區(qū)最頭疼的地方是擴(kuò)容。數(shù)組滿了之后你不能直接把數(shù)組翻倍復(fù)制就完事——因?yàn)楫?dāng)前隊(duì)列的頭可能在任意位置元素在邏輯上是“繞圈”排列的。擴(kuò)容時(shí)必須把舊元素重新排列到新數(shù)組的前面邏輯上仍然保持隊(duì)頭在前、隊(duì)尾在后。結(jié)合上一章提到的 placement new 知識(shí)你可以寫(xiě)出一個(gè)能支持任意類型的 RingQueue但代碼量會(huì)比鏈表方案多不少。從實(shí)際取舍來(lái)看如果是教學(xué)、面試或快速原型鏈表方案優(yōu)先邏輯清晰、不容易出錯(cuò)。如果是性能敏感的高頻入隊(duì)出隊(duì)場(chǎng)景環(huán)形緩沖區(qū)更合適。在 C 里STL 的std::queue默認(rèn)用std::deque其實(shí)就相當(dāng)于“分段連續(xù)”的環(huán)形緩沖區(qū)優(yōu)化版這才是它性能好的真正原因。4.3 擴(kuò)展思考用兩個(gè)棧實(shí)現(xiàn)隊(duì)列既然手寫(xiě)了 stack你還可以玩一個(gè)經(jīng)典題目用兩個(gè)棧實(shí)現(xiàn)隊(duì)列。思路是這樣的棧 A 負(fù)責(zé)入隊(duì)push 直接壓入 A。棧 B 負(fù)責(zé)出隊(duì)當(dāng) B 為空時(shí)把 A 的所有元素依次 pop 并 push 進(jìn) B然后從 B 的棧頂彈出就等價(jià)于從隊(duì)頭出隊(duì)。這個(gè)技巧很有意思因?yàn)閮蓚€(gè) LIFO 結(jié)構(gòu)疊起來(lái)竟然能模擬出 FIFO 的行為。實(shí)測(cè)下來(lái)平均時(shí)間復(fù)雜度依然是 O(1)只有 A 往 B 倒數(shù)據(jù)的那一瞬間是 O(n) 的攤還下來(lái)完全可接受。理解了這篇實(shí)現(xiàn)的 stack再去做這道題會(huì)非常輕松這里先留給你自己試一試。5. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄5.1 淺拷貝導(dǎo)致的雙重釋放這是手寫(xiě)容器時(shí)最容易踩的坑?，F(xiàn)象是程序運(yùn)行到析構(gòu)時(shí)直接報(bào)double free or corruption。原因就是我前面說(shuō)的默認(rèn)的拷貝構(gòu)造是逐字節(jié)復(fù)制兩個(gè)對(duì)象的data_指針指向同一塊內(nèi)存析構(gòu)時(shí)兩次delete[]同一地址。排查技巧很簡(jiǎn)單在類里臨時(shí)禁用拷貝構(gòu)造和賦值運(yùn)算符如果崩潰消失基本可以斷定是淺拷貝問(wèn)題。修復(fù)方案也很唯一實(shí)現(xiàn)深拷貝。要么手動(dòng)寫(xiě)拷貝構(gòu)造和賦值運(yùn)算符要么用 copy-and-swap 一勞永逸。5.2 空容器上的 undefined behaviorSTL 的std::stack::top()在棧為空時(shí)是未定義行為不會(huì)幫你做檢查。但自己實(shí)現(xiàn)的容器如果也這樣照搬測(cè)試時(shí)很容易出現(xiàn)莫名其妙的崩潰。我推薦的做法是顯式拋異常比如throw std::runtime_error(stack empty)。雖然現(xiàn)場(chǎng)會(huì)多一次分支判斷但它能幫你快速暴露邏輯錯(cuò)誤。這個(gè)取舍在實(shí)際工程中很值得寧可慢一點(diǎn)也不能讓未定義行為蟄伏在代碼里。5.3 模板編譯報(bào)錯(cuò)的定位思路手寫(xiě)模板類時(shí)最常見(jiàn)的編譯錯(cuò)誤是“no default constructor exists for class X”或者“cannot assign”。原因往往不是你的邏輯錯(cuò)了而是你底層用的new T[]對(duì)類型提出了額外要求。當(dāng) T 沒(méi)有默認(rèn)構(gòu)造函數(shù)時(shí)new T[cap]無(wú)法編譯。遇到這種情況先別慌檢查兩個(gè)方向你是不是用了new T[]如果是換成::operator new placement new 方案參考 3.3 節(jié)。你的自定義類型是否缺少拷貝構(gòu)造或拷貝賦值模板實(shí)例化時(shí)所有用到的方法都會(huì)被編譯即使你沒(méi)調(diào)用編譯器也會(huì)檢查其合法性。這類報(bào)錯(cuò)信息往往很長(zhǎng)但真正的有效信息在第一個(gè)error位置往那兒找效率最高。5.4 性能對(duì)比自實(shí)現(xiàn) vs STL我用一個(gè)簡(jiǎn)單的程序壓了十萬(wàn)次 push/pop得出了幾個(gè)參考數(shù)據(jù)不同機(jī)器會(huì)有差異但趨勢(shì)一致容器10萬(wàn)次 push/pop 耗時(shí)內(nèi)存分配次數(shù)自實(shí)現(xiàn)動(dòng)態(tài)數(shù)組 stack較低擴(kuò)容僅十幾次STL stack (deque)略高但極穩(wěn)分批分配自實(shí)現(xiàn)鏈表 queue較高10萬(wàn)次 new/deleteSTL queue (deque)中等分批分配結(jié)論很明顯鏈表的單次操作雖然也是 O(1)但常數(shù)很大因?yàn)槊看?push 都涉及一次堆分配。這就是為什么 STL 的 stack/queue 默認(rèn)都用 deque 而不是 list——連續(xù)內(nèi)存的訪問(wèn)效率遠(yuǎn)高于零散的鏈表節(jié)點(diǎn)。自己做性能測(cè)試時(shí)記得把編譯器的優(yōu)化選項(xiàng)打開(kāi)比如-O2否則測(cè)出來(lái)的是調(diào)試模式的數(shù)據(jù)參考價(jià)值不大。一些實(shí)在的心得把這兩個(gè)容器從頭實(shí)現(xiàn)一遍之后我最大的感受是STL 看似簡(jiǎn)單的接口背后藏著相當(dāng)多的設(shè)計(jì)決策。比如為什么 queue 不用 vector因?yàn)?vector 在頭部刪除是 O(n)。為什么不用 list因?yàn)?list 每個(gè)節(jié)點(diǎn)單獨(dú)分配內(nèi)存緩存不友好。而 deque 通過(guò)分段連續(xù)存儲(chǔ)兼顧了兩端的操作效率和訪問(wèn)局部性。這些結(jié)論如果你只看教科書(shū)是記不牢的但親手寫(xiě)一遍代碼、壓一次性能就全通了。如果你想把練習(xí)再往上推一步我建議你試試這幾個(gè)方向給 stack 增加emplace接口用變參模板直接構(gòu)造元素給 queue 增加移動(dòng)構(gòu)造和移動(dòng)賦值減少拷貝開(kāi)銷或者把底層容器策略做成模板參數(shù)模擬 STL 容器適配器的設(shè)計(jì)方式。每做一個(gè)你都會(huì)對(duì) C 的泛型和對(duì)象模型有更深一層理解。最后說(shuō)一點(diǎn)實(shí)在的這篇里的代碼是為了教學(xué)清晰而精簡(jiǎn)過(guò)的用來(lái)面試和自學(xué)完全夠。如果你要在正式生產(chǎn)項(xiàng)目里用直接用std::stack和std::queue就好了不要重復(fù)造輪子。造輪子的意義在于弄懂輪子而不在于替換輪子。