現(xiàn)與避坑指南)
我見過太多人把 STL 里的stack和queue當(dāng)成“裝數(shù)據(jù)的盒子”push 一下、pop 一下用起來比誰都熟?？梢坏┍粏柕健斑@倆的底層到底是什么”“讓你自己實(shí)現(xiàn)一個(gè)能不能寫出來”不少人就卡住了。原因其實(shí)很統(tǒng)一我們習(xí)慣了站在使用者的角度去看容器卻很少站到實(shí)現(xiàn)者的角度去思考它的內(nèi)存布局、邊界條件、生命周期管理。這個(gè)項(xiàng)目不復(fù)雜但很值得認(rèn)真做一遍——從一個(gè)空類開始手寫 stack 和 queue 的全部關(guān)鍵操作把模板、動(dòng)態(tài)內(nèi)存、拷貝語義、邊界判斷這些東西一次性捋清楚。這篇文章就圍繞“從零實(shí)現(xiàn)”展開。我會(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。也就是說它們本身不管理內(nèi)存也不存儲(chǔ)數(shù)據(jù)而是通過包裝另一個(gè)容器默認(rèn)是std::deque來提供受限的接口。std::stack只讓你操作棧頂push 從頂入、pop 從頂出、top 看棧頂。std::queue只讓你操作兩端push 從隊(duì)尾入、pop 從隊(duì)頭出、front 看隊(duì)頭、back 看隊(duì)尾。你看它們把底層容器的“自由度”砍掉了——deque 能提供隨機(jī)訪問但 stack/queue 把這些能力鎖了起來只暴露出符合語義的那幾個(gè)操作。這是接口約束上的典型設(shè)計(jì)用最少的方法表達(dá)最清晰的數(shù)據(jù)結(jié)構(gòu)語義。從零實(shí)現(xiàn)的意義就在這里當(dāng)你自己動(dòng)手的時(shí)候你才會(huì)意識(shí)到實(shí)現(xiàn)一個(gè) stack 根本不需要從頭發(fā)明什么新東西——你只需要一個(gè)“能存東西、能按順序訪問”的底層結(jié)構(gòu)然后把外部接口限制起來。這個(gè)“把底層容器封裝成語義明確的適配器”的思路比單純背幾個(gè)函數(shù)名重要得多。1.2 從零實(shí)現(xiàn)能換來什么收獲我之所以推薦你親手寫一遍而不是直接打印源碼看是因?yàn)閷懙倪^程中你會(huì)被迫回答這幾類問題內(nèi)存管理問題棧的容量不夠了怎么辦是每次 push 都擴(kuò)容還是提前預(yù)留擴(kuò)容系數(shù)取多少生命周期問題pop 之后被移除的元素它的析構(gòu)函數(shù)是否被調(diào)用了對(duì)象持有的資源有沒有真正釋放拷貝語義問題容器被拷貝時(shí)是淺拷貝還是深拷貝如果直接復(fù)制指針兩份“獨(dú)立”的容器會(huì)不會(huì)在析構(gòu)時(shí)爭(zhēng)搶同一塊內(nèi)存邊界條件問題空棧上調(diào)用 top 會(huì)發(fā)生什么隊(duì)列只有一個(gè)元素時(shí) pop會(huì)不會(huì)把隊(duì)尾指針弄丟只調(diào)用現(xiàn)成 API 的人是永遠(yuǎn)不會(huì)思考這些的。但如果你要寫自己的容器這些問題一個(gè)個(gè)都會(huì)冒出來。正因如此“從零實(shí)現(xiàn) stack/queue”才是一個(gè)性價(jià)比極高的練習(xí)項(xiàng)目——它不大但足夠的細(xì)節(jié)密度讓你把 C 的內(nèi)存和對(duì)象模型真正串起來。2. 整體設(shè)計(jì)思路適配器語義與底層容器的取舍2.1 第一步不是寫代碼是列清楚操作清單動(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)把這些接口列出來再動(dòng)手后面寫代碼時(shí)會(huì)省力很多。因?yàn)槟阒雷约涸趯?shí)現(xiàn)什么而不是“寫一步看一步”。2.2 底層容器選型數(shù)組、鏈表還是分段連續(xù)stack 和 queue 的語義其實(shí)對(duì)底層結(jié)構(gòu)沒有硬性要求只要滿足兩端插入刪除的復(fù)雜度需求即可。常見的底層方案有四種底層方案入棧/入隊(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)差無擴(kuò)容但每節(jié)點(diǎn)有指針開銷較高環(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 并連接起來。這個(gè)設(shè)計(jì)精妙但實(shí)現(xiàn)起來非常復(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)帶來的內(nèi)存管理差異。兩種結(jié)構(gòu)都過一遍手比只盯著一種強(qiáng)太多。2.3 模板設(shè)計(jì)從一開始就支持泛型既然是模仿 STL模板是必須的。用模板的好處很直接一份代碼能承載 int、string、自定義對(duì)象等任意類型。類定義寫成template typename T class MyStack { // ... };但這也帶來一些代價(jià)。比如某些類型沒有默認(rèn)構(gòu)造函數(shù)或者拷貝成本很高這些都會(huì)影響底層內(nèi)存管理策略的選擇。所以我會(huì)在實(shí)現(xiàn)時(shí)重點(diǎn)考慮“如何避免對(duì) T 的額外要求”。換句話說只要 T 支持拷貝構(gòu)造和拷貝賦值我的容器就應(yīng)該能正常工作。另外一個(gè)細(xì)節(jié)成員命名。我習(xí)慣在成員變量后面加_后綴例如capacity_、size_用來區(qū)分形參和成員。這是很多 C 工程里的約定讓代碼一眼就能看出哪些是成員、哪些是局部變量。3. 從零實(shí)現(xiàn) stack完整代碼與關(guān)鍵操作拆解3.1 動(dòng)態(tài)數(shù)組版 MyStack 的整體框架我用動(dòng)態(tài)數(shù)組來實(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;這種寫法可能會(huì)誤導(dǎo)讀者加上explicit之后必須寫成MyStackint s(100);意圖更清晰。pop()只做了--size_沒有真正銷毀棧頂對(duì)象。原因很簡(jiǎn)單我們用new T[]分配數(shù)組時(shí)所有元素從一開始就構(gòu)造好了數(shù)組不銷毀它們的生命周期就不會(huì)結(jié)束。減少size_只是把它們“遮蔽”起來后續(xù) push 時(shí)會(huì)用賦值運(yùn)算符覆蓋舊值。這種寫法對(duì)常規(guī)類型完全沒問題但嚴(yán)格意義上對(duì)象占用的資源沒有被提前釋放。我后面會(huì)給出更嚴(yán)格的實(shí)現(xiàn)。top()有 const 版本和非 const 版本。非 const 版本允許調(diào)用方修改棧頂元素const 版本用于只讀場(chǎng)景。這是 STL 中非常常見的雙版本模式。3.2 擴(kuò)容機(jī)制與拷貝語義的坑grow()里我選擇了capacity_ * 2也就是每次翻倍。為什么是 2 而不是別的數(shù)這里有一個(gè)攤還復(fù)雜度的經(jīng)典論證假設(shè)從 1 開始按 2 倍擴(kuò)容到 n總共會(huì)拷貝1 2 4 ... n/2 n ≈ 2n次也就是說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)算符需要先處理“自賦值”和“異常安全”的問題。一個(gè)常見的寫法是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í)參拷貝出來的臨時(shí)對(duì)象swap 之后舊數(shù)據(jù)被裝進(jìn)了這個(gè)臨時(shí)對(duì)象函數(shù)結(jié)束時(shí)自動(dòng)析構(gòu)完成資源清理。如果實(shí)參拷貝過程中拋異常賦值操作就整體失敗原對(duì)象狀態(tài)不受影響。這就是 copy-and-swap 的優(yōu)雅之處用拷貝構(gòu)造來保證異常安全。3.3 進(jìn)階用 placement new 讓容器更嚴(yán)謹(jǐn)前面的實(shí)現(xiàn)雖然很好理解但有一個(gè)明顯的局限new T[cap]要求 T 必須支持默認(rèn)構(gòu)造。如果 T 沒有默認(rèn)構(gòu)造函數(shù)代碼就無法編譯。而且用賦值運(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ù)。這一套組合拳讓容器可以存放沒有默認(rèn)構(gòu)造函數(shù)的類型也讓 pop 真正釋放了對(duì)象持有的資源。代價(jià)是代碼復(fù)雜度明顯提高。我的建議是先把第一版搞懂、跑通再升級(jí)到這一版。學(xué)習(xí)路徑本身比直接抄一個(gè)“最強(qiáng)版本”更重要。3.4 測(cè)試 MyStack不只測(cè)功能更要測(cè)邊界寫測(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; }跑起來之后重點(diǎn)觀察幾件事擴(kuò)容是否正常、pop 后 size 是否正確遞減、空棧異常是否被拋出、拷貝出來的棧是否和原棧完全獨(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ì)面臨“前面空出來但后面滿了”的尷尬局面必須引入環(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ì)訪問懸空指針程序崩潰。這個(gè) bug 非常經(jīng)典我見過不少人在手寫隊(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)。這樣寫異常安全和自賦值問題一次全解決。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)都要通過new單獨(dú)分配內(nèi)存這些零散的堆分配導(dǎo)致內(nèi)存碎片化而且訪問節(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í)把元素寫到tail_然后tail_ (tail_ 1) % capacity_pop 時(shí)讀取head_然后head_ (head_ 1) % capacity_。這個(gè)取模操作讓索引到數(shù)組末尾時(shí)自動(dòng)回到開頭形成“環(huán)”。環(huán)形緩沖區(qū)最頭疼的地方是擴(kuò)容。數(shù)組滿了之后你不能直接把數(shù)組翻倍復(fù)制就完事——因?yàn)楫?dāng)前隊(duì)列的頭可能在任意位置元素在邏輯上是“繞圈”排列的。擴(kuò)容時(shí)必須把舊元素重新排列到新數(shù)組的前面邏輯上仍然保持隊(duì)頭在前、隊(duì)尾在后。結(jié)合上一章提到的 placement new 知識(shí)你可以寫出一個(gè)能支持任意類型的 RingQueue但代碼量會(huì)比鏈表方案多不少。從實(shí)際取舍來看如果是教學(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ì)列既然手寫了 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)疊起來竟然能模擬出 FIFO 的行為。實(shí)測(cè)下來平均時(shí)間復(fù)雜度依然是 O(1)只有 A 往 B 倒數(shù)據(jù)的那一瞬間是 O(n) 的攤還下來完全可接受。理解了這篇實(shí)現(xiàn)的 stack再去做這道題會(huì)非常輕松這里先留給你自己試一試。5. 常見問題與排查技巧實(shí)錄5.1 淺拷貝導(dǎo)致的雙重釋放這是手寫容器時(shí)最容易踩的坑?，F(xiàn)象是程序運(yùn)行到析構(gòu)時(shí)直接報(bào)double free or corruption。原因就是我前面說的默認(rèn)的拷貝構(gòu)造是逐字節(jié)復(fù)制兩個(gè)對(duì)象的data_指針指向同一塊內(nèi)存析構(gòu)時(shí)兩次delete[]同一地址。排查技巧很簡(jiǎn)單在類里臨時(shí)禁用拷貝構(gòu)造和賦值運(yùn)算符如果崩潰消失基本可以斷定是淺拷貝問題。修復(fù)方案也很唯一實(shí)現(xiàn)深拷貝。要么手動(dòng)寫拷貝構(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ò)的定位思路手寫模板類時(shí)最常見的編譯錯(cuò)誤是“no default constructor exists for class X”或者“cannot assign”。原因往往不是你的邏輯錯(cuò)了而是你底層用的new T[]對(duì)類型提出了額外要求。當(dāng) T 沒有默認(rèn)構(gòu)造函數(shù)時(shí)new T[cap]無法編譯。遇到這種情況先別慌檢查兩個(gè)方向你是不是用了new T[]如果是換成::operator new placement new 方案參考 3.3 節(jié)。你的自定義類型是否缺少拷貝構(gòu)造或拷貝賦值模板實(shí)例化時(shí)所有用到的方法都會(huì)被編譯即使你沒調(diào)用編譯器也會(huì)檢查其合法性。這類報(bào)錯(cuò)信息往往很長(zhǎng)但真正的有效信息在第一個(gè)error位置往那兒找效率最高。5.4 性能對(duì)比自實(shí)現(xiàn) vs STL我用一個(gè)簡(jiǎn)單的程序壓了十萬次 push/pop得出了幾個(gè)參考數(shù)據(jù)不同機(jī)器會(huì)有差異但趨勢(shì)一致容器10萬次 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萬次 new/deleteSTL queue (deque)中等分批分配結(jié)論很明顯鏈表的單次操作雖然也是 O(1)但常數(shù)很大因?yàn)槊看?push 都涉及一次堆分配。這就是為什么 STL 的 stack/queue 默認(rèn)都用 deque 而不是 list——連續(xù)內(nèi)存的訪問效率遠(yuǎn)高于零散的鏈表節(jié)點(diǎn)。自己做性能測(cè)試時(shí)記得把編譯器的優(yōu)化選項(xiàng)打開比如-O2否則測(cè)出來的是調(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 通過分段連續(xù)存儲(chǔ)兼顧了兩端的操作效率和訪問局部性。這些結(jié)論如果你只看教科書是記不牢的但親手寫一遍代碼、壓一次性能就全通了。如果你想把練習(xí)再往上推一步我建議你試試這幾個(gè)方向給 stack 增加emplace接口用變參模板直接構(gòu)造元素給 queue 增加移動(dòng)構(gòu)造和移動(dòng)賦值減少拷貝開銷或者把底層容器策略做成模板參數(shù)模擬 STL 容器適配器的設(shè)計(jì)方式。每做一個(gè)你都會(huì)對(duì) C 的泛型和對(duì)象模型有更深一層理解。最后說一點(diǎn)實(shí)在的這篇里的代碼是為了教學(xué)清晰而精簡(jiǎn)過的用來面試和自學(xué)完全夠。如果你要在正式生產(chǎn)項(xiàng)目里用直接用std::stack和std::queue就好了不要重復(fù)造輪子。造輪子的意義在于弄懂輪子而不在于替換輪子。 從零手寫C++ STL容器：stack與queue的底層實(shí)現(xiàn)與避坑指南
我見過太多人把 STL 里的stack和queue當(dāng)成“裝數(shù)據(jù)的盒子”push 一下、pop 一下用起來比誰都熟?？梢坏┍粏柕健斑@倆的底層到底是什么”“讓你自己實(shí)現(xiàn)一個(gè)能不能寫出來”不少人就卡住了。原因其實(shí)很統(tǒng)一我們習(xí)慣了站在使用者的角度去看容器卻很少站到實(shí)現(xiàn)者的角度去思考它的內(nèi)存布局、邊界條件、生命周期管理。這個(gè)項(xiàng)目不復(fù)雜但很值得認(rèn)真做一遍——從一個(gè)空類開始手寫 stack 和 queue 的全部關(guān)鍵操作把模板、動(dòng)態(tài)內(nèi)存、拷貝語義、邊界判斷這些東西一次性捋清楚。這篇文章就圍繞“從零實(shí)現(xiàn)”展開。我會(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。也就是說它們本身不管理內(nèi)存也不存儲(chǔ)數(shù)據(jù)而是通過包裝另一個(gè)容器默認(rèn)是std::deque來提供受限的接口。std::stack只讓你操作棧頂push 從頂入、pop 從頂出、top 看棧頂。std::queue只讓你操作兩端push 從隊(duì)尾入、pop 從隊(duì)頭出、front 看隊(duì)頭、back 看隊(duì)尾。你看它們把底層容器的“自由度”砍掉了——deque 能提供隨機(jī)訪問但 stack/queue 把這些能力鎖了起來只暴露出符合語義的那幾個(gè)操作。這是接口約束上的典型設(shè)計(jì)用最少的方法表達(dá)最清晰的數(shù)據(jù)結(jié)構(gòu)語義。從零實(shí)現(xiàn)的意義就在這里當(dāng)你自己動(dòng)手的時(shí)候你才會(huì)意識(shí)到實(shí)現(xiàn)一個(gè) stack 根本不需要從頭發(fā)明什么新東西——你只需要一個(gè)“能存東西、能按順序訪問”的底層結(jié)構(gòu)然后把外部接口限制起來。這個(gè)“把底層容器封裝成語義明確的適配器”的思路比單純背幾個(gè)函數(shù)名重要得多。1.2 從零實(shí)現(xiàn)能換來什么收獲我之所以推薦你親手寫一遍而不是直接打印源碼看是因?yàn)閷懙倪^程中你會(huì)被迫回答這幾類問題內(nèi)存管理問題棧的容量不夠了怎么辦是每次 push 都擴(kuò)容還是提前預(yù)留擴(kuò)容系數(shù)取多少生命周期問題pop 之后被移除的元素它的析構(gòu)函數(shù)是否被調(diào)用了對(duì)象持有的資源有沒有真正釋放拷貝語義問題容器被拷貝時(shí)是淺拷貝還是深拷貝如果直接復(fù)制指針兩份“獨(dú)立”的容器會(huì)不會(huì)在析構(gòu)時(shí)爭(zhēng)搶同一塊內(nèi)存邊界條件問題空棧上調(diào)用 top 會(huì)發(fā)生什么隊(duì)列只有一個(gè)元素時(shí) pop會(huì)不會(huì)把隊(duì)尾指針弄丟只調(diào)用現(xiàn)成 API 的人是永遠(yuǎn)不會(huì)思考這些的。但如果你要寫自己的容器這些問題一個(gè)個(gè)都會(huì)冒出來。正因如此“從零實(shí)現(xiàn) stack/queue”才是一個(gè)性價(jià)比極高的練習(xí)項(xiàng)目——它不大但足夠的細(xì)節(jié)密度讓你把 C 的內(nèi)存和對(duì)象模型真正串起來。2. 整體設(shè)計(jì)思路適配器語義與底層容器的取舍2.1 第一步不是寫代碼是列清楚操作清單動(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)把這些接口列出來再動(dòng)手后面寫代碼時(shí)會(huì)省力很多。因?yàn)槟阒雷约涸趯?shí)現(xiàn)什么而不是“寫一步看一步”。2.2 底層容器選型數(shù)組、鏈表還是分段連續(xù)stack 和 queue 的語義其實(shí)對(duì)底層結(jié)構(gòu)沒有硬性要求只要滿足兩端插入刪除的復(fù)雜度需求即可。常見的底層方案有四種底層方案入棧/入隊(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)差無擴(kuò)容但每節(jié)點(diǎn)有指針開銷較高環(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 并連接起來。這個(gè)設(shè)計(jì)精妙但實(shí)現(xiàn)起來非常復(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)帶來的內(nèi)存管理差異。兩種結(jié)構(gòu)都過一遍手比只盯著一種強(qiáng)太多。2.3 模板設(shè)計(jì)從一開始就支持泛型既然是模仿 STL模板是必須的。用模板的好處很直接一份代碼能承載 int、string、自定義對(duì)象等任意類型。類定義寫成template typename T class MyStack { // ... };但這也帶來一些代價(jià)。比如某些類型沒有默認(rèn)構(gòu)造函數(shù)或者拷貝成本很高這些都會(huì)影響底層內(nèi)存管理策略的選擇。所以我會(huì)在實(shí)現(xiàn)時(shí)重點(diǎn)考慮“如何避免對(duì) T 的額外要求”。換句話說只要 T 支持拷貝構(gòu)造和拷貝賦值我的容器就應(yīng)該能正常工作。另外一個(gè)細(xì)節(jié)成員命名。我習(xí)慣在成員變量后面加_后綴例如capacity_、size_用來區(qū)分形參和成員。這是很多 C 工程里的約定讓代碼一眼就能看出哪些是成員、哪些是局部變量。3. 從零實(shí)現(xiàn) stack完整代碼與關(guān)鍵操作拆解3.1 動(dòng)態(tài)數(shù)組版 MyStack 的整體框架我用動(dòng)態(tài)數(shù)組來實(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;這種寫法可能會(huì)誤導(dǎo)讀者加上explicit之后必須寫成MyStackint s(100);意圖更清晰。pop()只做了--size_沒有真正銷毀棧頂對(duì)象。原因很簡(jiǎn)單我們用new T[]分配數(shù)組時(shí)所有元素從一開始就構(gòu)造好了數(shù)組不銷毀它們的生命周期就不會(huì)結(jié)束。減少size_只是把它們“遮蔽”起來后續(xù) push 時(shí)會(huì)用賦值運(yùn)算符覆蓋舊值。這種寫法對(duì)常規(guī)類型完全沒問題但嚴(yán)格意義上對(duì)象占用的資源沒有被提前釋放。我后面會(huì)給出更嚴(yán)格的實(shí)現(xiàn)。top()有 const 版本和非 const 版本。非 const 版本允許調(diào)用方修改棧頂元素const 版本用于只讀場(chǎng)景。這是 STL 中非常常見的雙版本模式。3.2 擴(kuò)容機(jī)制與拷貝語義的坑grow()里我選擇了capacity_ * 2也就是每次翻倍。為什么是 2 而不是別的數(shù)這里有一個(gè)攤還復(fù)雜度的經(jīng)典論證假設(shè)從 1 開始按 2 倍擴(kuò)容到 n總共會(huì)拷貝1 2 4 ... n/2 n ≈ 2n次也就是說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)算符需要先處理“自賦值”和“異常安全”的問題。一個(gè)常見的寫法是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í)參拷貝出來的臨時(shí)對(duì)象swap 之后舊數(shù)據(jù)被裝進(jìn)了這個(gè)臨時(shí)對(duì)象函數(shù)結(jié)束時(shí)自動(dòng)析構(gòu)完成資源清理。如果實(shí)參拷貝過程中拋異常賦值操作就整體失敗原對(duì)象狀態(tài)不受影響。這就是 copy-and-swap 的優(yōu)雅之處用拷貝構(gòu)造來保證異常安全。3.3 進(jìn)階用 placement new 讓容器更嚴(yán)謹(jǐn)前面的實(shí)現(xiàn)雖然很好理解但有一個(gè)明顯的局限new T[cap]要求 T 必須支持默認(rèn)構(gòu)造。如果 T 沒有默認(rèn)構(gòu)造函數(shù)代碼就無法編譯。而且用賦值運(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ù)。這一套組合拳讓容器可以存放沒有默認(rèn)構(gòu)造函數(shù)的類型也讓 pop 真正釋放了對(duì)象持有的資源。代價(jià)是代碼復(fù)雜度明顯提高。我的建議是先把第一版搞懂、跑通再升級(jí)到這一版。學(xué)習(xí)路徑本身比直接抄一個(gè)“最強(qiáng)版本”更重要。3.4 測(cè)試 MyStack不只測(cè)功能更要測(cè)邊界寫測(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; }跑起來之后重點(diǎn)觀察幾件事擴(kuò)容是否正常、pop 后 size 是否正確遞減、空棧異常是否被拋出、拷貝出來的棧是否和原棧完全獨(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ì)面臨“前面空出來但后面滿了”的尷尬局面必須引入環(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ì)訪問懸空指針程序崩潰。這個(gè) bug 非常經(jīng)典我見過不少人在手寫隊(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)。這樣寫異常安全和自賦值問題一次全解決。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)都要通過new單獨(dú)分配內(nèi)存這些零散的堆分配導(dǎo)致內(nèi)存碎片化而且訪問節(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í)把元素寫到tail_然后tail_ (tail_ 1) % capacity_pop 時(shí)讀取head_然后head_ (head_ 1) % capacity_。這個(gè)取模操作讓索引到數(shù)組末尾時(shí)自動(dòng)回到開頭形成“環(huán)”。環(huán)形緩沖區(qū)最頭疼的地方是擴(kuò)容。數(shù)組滿了之后你不能直接把數(shù)組翻倍復(fù)制就完事——因?yàn)楫?dāng)前隊(duì)列的頭可能在任意位置元素在邏輯上是“繞圈”排列的。擴(kuò)容時(shí)必須把舊元素重新排列到新數(shù)組的前面邏輯上仍然保持隊(duì)頭在前、隊(duì)尾在后。結(jié)合上一章提到的 placement new 知識(shí)你可以寫出一個(gè)能支持任意類型的 RingQueue但代碼量會(huì)比鏈表方案多不少。從實(shí)際取舍來看如果是教學(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ì)列既然手寫了 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)疊起來竟然能模擬出 FIFO 的行為。實(shí)測(cè)下來平均時(shí)間復(fù)雜度依然是 O(1)只有 A 往 B 倒數(shù)據(jù)的那一瞬間是 O(n) 的攤還下來完全可接受。理解了這篇實(shí)現(xiàn)的 stack再去做這道題會(huì)非常輕松這里先留給你自己試一試。5. 常見問題與排查技巧實(shí)錄5.1 淺拷貝導(dǎo)致的雙重釋放這是手寫容器時(shí)最容易踩的坑?，F(xiàn)象是程序運(yùn)行到析構(gòu)時(shí)直接報(bào)double free or corruption。原因就是我前面說的默認(rèn)的拷貝構(gòu)造是逐字節(jié)復(fù)制兩個(gè)對(duì)象的data_指針指向同一塊內(nèi)存析構(gòu)時(shí)兩次delete[]同一地址。排查技巧很簡(jiǎn)單在類里臨時(shí)禁用拷貝構(gòu)造和賦值運(yùn)算符如果崩潰消失基本可以斷定是淺拷貝問題。修復(fù)方案也很唯一實(shí)現(xiàn)深拷貝。要么手動(dòng)寫拷貝構(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ò)的定位思路手寫模板類時(shí)最常見的編譯錯(cuò)誤是“no default constructor exists for class X”或者“cannot assign”。原因往往不是你的邏輯錯(cuò)了而是你底層用的new T[]對(duì)類型提出了額外要求。當(dāng) T 沒有默認(rèn)構(gòu)造函數(shù)時(shí)new T[cap]無法編譯。遇到這種情況先別慌檢查兩個(gè)方向你是不是用了new T[]如果是換成::operator new placement new 方案參考 3.3 節(jié)。你的自定義類型是否缺少拷貝構(gòu)造或拷貝賦值模板實(shí)例化時(shí)所有用到的方法都會(huì)被編譯即使你沒調(diào)用編譯器也會(huì)檢查其合法性。這類報(bào)錯(cuò)信息往往很長(zhǎng)但真正的有效信息在第一個(gè)error位置往那兒找效率最高。5.4 性能對(duì)比自實(shí)現(xiàn) vs STL我用一個(gè)簡(jiǎn)單的程序壓了十萬次 push/pop得出了幾個(gè)參考數(shù)據(jù)不同機(jī)器會(huì)有差異但趨勢(shì)一致容器10萬次 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萬次 new/deleteSTL queue (deque)中等分批分配結(jié)論很明顯鏈表的單次操作雖然也是 O(1)但常數(shù)很大因?yàn)槊看?push 都涉及一次堆分配。這就是為什么 STL 的 stack/queue 默認(rèn)都用 deque 而不是 list——連續(xù)內(nèi)存的訪問效率遠(yuǎn)高于零散的鏈表節(jié)點(diǎn)。自己做性能測(cè)試時(shí)記得把編譯器的優(yōu)化選項(xiàng)打開比如-O2否則測(cè)出來的是調(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 通過分段連續(xù)存儲(chǔ)兼顧了兩端的操作效率和訪問局部性。這些結(jié)論如果你只看教科書是記不牢的但親手寫一遍代碼、壓一次性能就全通了。如果你想把練習(xí)再往上推一步我建議你試試這幾個(gè)方向給 stack 增加emplace接口用變參模板直接構(gòu)造元素給 queue 增加移動(dòng)構(gòu)造和移動(dòng)賦值減少拷貝開銷或者把底層容器策略做成模板參數(shù)模擬 STL 容器適配器的設(shè)計(jì)方式。每做一個(gè)你都會(huì)對(duì) C 的泛型和對(duì)象模型有更深一層理解。最后說一點(diǎn)實(shí)在的這篇里的代碼是為了教學(xué)清晰而精簡(jiǎn)過的用來面試和自學(xué)完全夠。如果你要在正式生產(chǎn)項(xiàng)目里用直接用std::stack和std::queue就好了不要重復(fù)造輪子。造輪子的意義在于弄懂輪子而不在于替換輪子。