1. 從“盤子”到“容器”理解棧的核心哲學(xué)如果你寫過C或者哪怕只是聽說過數(shù)據(jù)結(jié)構(gòu)大概率都繞不開“?！边@個(gè)概念。教科書上會(huì)告訴你棧是一種“后進(jìn)先出”LIFO, Last In First Out的線性數(shù)據(jù)結(jié)構(gòu)就像一摞盤子你只能從最上面放也只能從最上面取。這個(gè)比喻很形象但它只告訴了你“是什么”沒告訴你“為什么”以及“怎么用”。在實(shí)際的C開發(fā)中std::stack絕不僅僅是一個(gè)“放盤子的架子”它是管理具有特定生命周期和訪問順序的數(shù)據(jù)的利器其設(shè)計(jì)哲學(xué)深深植根于計(jì)算機(jī)科學(xué)的底層邏輯比如函數(shù)調(diào)用、表達(dá)式求值、撤銷操作等場景。為什么C標(biāo)準(zhǔn)庫要專門提供std::stack為什么不直接用std::vector或std::deque然后自己約定只從尾部操作原因就在于“封裝”和“語義”。std::stack是一個(gè)容器適配器它基于某個(gè)底層序列容器默認(rèn)是std::deque但只暴露了棧應(yīng)有的操作接口push,pop,top,empty,size。這種設(shè)計(jì)強(qiáng)制了你遵循棧的訪問規(guī)則避免了誤操作讓代碼的意圖更加清晰。當(dāng)你看到std::stack時(shí)你立刻就知道這里的數(shù)據(jù)訪問模式是LIFO的這對(duì)于代碼的閱讀者和維護(hù)者來說是一種重要的語義提示。在C的生態(tài)中棧的身影無處不在。你寫的每一個(gè)函數(shù)調(diào)用其局部變量、返回地址等信息都保存在一個(gè)被稱為“調(diào)用?！钡膬?nèi)存區(qū)域中這就是棧數(shù)據(jù)結(jié)構(gòu)最經(jīng)典的應(yīng)用。當(dāng)你使用遞歸算法時(shí)本質(zhì)上也是系統(tǒng)在幫你管理一個(gè)調(diào)用棧。而在應(yīng)用層瀏覽器的前進(jìn)后退、文本編輯器的撤銷重做、編譯器中括號(hào)匹配檢查、乃至游戲中的狀態(tài)管理?xiàng)６际潜澈蟮暮诵臄?shù)據(jù)結(jié)構(gòu)。因此深入理解std::stack的用法不僅是學(xué)習(xí)一個(gè)STL組件更是理解一種廣泛適用的程序設(shè)計(jì)模式。2.std::stack的里里外外定義、初始化與底層容器在C中使用std::stack首先需要包含頭文件stack。它的類模板聲明看起來是這樣的template class T, class Container dequeT class stack;這里有兩個(gè)模板參數(shù)T是棧中存儲(chǔ)元素的類型Container是底層容器的類型它默認(rèn)是std::dequeT。2.1 如何定義一個(gè)棧定義一個(gè)棧非常簡單最常見的方式就是直接使用默認(rèn)的底層容器。#include stack #include string std::stackint s1; // 一個(gè)存儲(chǔ)int的棧底層使用deque std::stackstd::string, std::vectorstd::string s2; // 存儲(chǔ)string底層指定為vector std::stackdouble, std::listdouble s3; // 存儲(chǔ)double底層指定為list第一行s1是最常用的形式。后兩行展示了如何顯式指定底層容器。為什么可以指定不同的容器因?yàn)閟td::stack只要求底層容器支持back(),push_back(),pop_back()這幾個(gè)操作以及標(biāo)準(zhǔn)的empty()和size()。std::vector,std::deque,std::list都滿足這些要求。2.2 底層容器的選擇deque、vector還是list默認(rèn)選擇std::deque是標(biāo)準(zhǔn)委員會(huì)經(jīng)過權(quán)衡的結(jié)果它是對(duì)棧操作的一個(gè)“通用且性能均衡”的選擇。我們來分析一下各自的優(yōu)劣std::deque雙端隊(duì)列默認(rèn)優(yōu)點(diǎn)在頭部和尾部進(jìn)行插入/刪除操作的時(shí)間復(fù)雜度都是O(1)。對(duì)于棧只操作尾部來說這很完美。同時(shí)deque不需要像vector那樣在容量不足時(shí)進(jìn)行大量的元素拷貝內(nèi)存增長是分塊的對(duì)大規(guī)模數(shù)據(jù)更友好。缺點(diǎn)元素訪問的內(nèi)存局部性可能不如vector因?yàn)樗膬?nèi)存不是完全連續(xù)的。適用場景默認(rèn)選擇適用于絕大多數(shù)通用場景特別是當(dāng)棧中元素?cái)?shù)量變化較大或元素本身較大時(shí)。std::vector優(yōu)點(diǎn)內(nèi)存連續(xù)緩存命中率高遍歷和隨機(jī)訪問雖然棧用不到速度極快。push_back的均攤時(shí)間復(fù)雜度也是O(1)。缺點(diǎn)pop_back時(shí)vector通常只減少size不釋放內(nèi)存capacity不變。更重要的是vector在擴(kuò)容時(shí)需要重新分配內(nèi)存并移動(dòng)所有元素這個(gè)操作的時(shí)間復(fù)雜度是O(N)在棧增長過程中可能帶來不可預(yù)測的性能抖動(dòng)。適用場景當(dāng)你非常確定棧的最大容量并且能通過reserve()預(yù)分配內(nèi)存避免擴(kuò)容開銷時(shí)或者棧中元素是POD類型且需要極致的訪問速度時(shí)。std::list雙向鏈表優(yōu)點(diǎn)任何位置的插入刪除都是O(1)且不會(huì)導(dǎo)致迭代器失效除了被刪除的元素。缺點(diǎn)內(nèi)存開銷大每個(gè)元素都需要額外的指針緩存不友好訪問速度慢。適用場景棧中元素非常大且拷貝成本極高或者你需要頻繁地在棧的中部進(jìn)行訪問和修改但這違反了棧的LIFO原則此時(shí)或許不該用棧。個(gè)人經(jīng)驗(yàn)除非有非常明確的性能瓶頸和優(yōu)化目標(biāo)否則堅(jiān)持使用默認(rèn)的std::deque。它避免了vector擴(kuò)容的潛在風(fēng)險(xiǎn)又在絕大多數(shù)情況下提供了接近vector的性能。我曾在一個(gè)高頻交易模擬系統(tǒng)中將底層容器從vector換成deque僅僅因?yàn)楸苊饬伺紶柕臄U(kuò)容卡頓整體吞吐量就提升了約5%。2.3 棧的初始化std::stack本身沒有提供直接用初始化列表構(gòu)造的構(gòu)造函數(shù)C11之后其底層容器有但stack適配器沒有直接暴露。常見的初始化方式有幾種默認(rèn)構(gòu)造創(chuàng)建一個(gè)空棧。std::stackint stk;通過拷貝另一個(gè)棧構(gòu)造std::stackint stk1; stk1.push(1); stk1.push(2); std::stackint stk2(stk1); // stk2現(xiàn)在是 {1, 2}棧頂是2通過底層容器構(gòu)造這是最靈活的方式。你可以先構(gòu)造一個(gè)滿足要求的容器然后用它來初始化棧。std::vectorint vec {3, 1, 4, 1, 5}; // 注意容器中元素的順序 std::stackint, std::vectorint stk(vec); // 棧的初始化順序與容器順序一致 // 現(xiàn)在stk的棧底是3然后是1,4,1棧頂是5。 // 第一個(gè)push進(jìn)棧的元素是容器起始端的元素。這一點(diǎn)非常重要用容器初始化棧時(shí)容器begin()指向的元素會(huì)成為棧底end()-1指向的元素成為棧頂。你可以理解為把容器從左到右的元素依次壓入了棧中。3. 棧的核心操作壓入、彈出與訪問std::stack的接口非常簡潔主要就是五個(gè)核心操作這也是棧數(shù)據(jù)結(jié)構(gòu)的所有能力體現(xiàn)。3.1 壓入元素push與emplace向棧頂添加新元素。void push(const T value)將value的一個(gè)拷貝壓入棧頂。std::stackstd::string stk; std::string name Alice; stk.push(name); // 調(diào)用std::string的拷貝構(gòu)造函數(shù)void push(T value)C11移動(dòng)語義如果傳入的是右值如臨時(shí)對(duì)象則會(huì)移動(dòng)資源避免拷貝。stk.push(std::string(Bob)); // 構(gòu)造臨時(shí)string然后移動(dòng)進(jìn)棧template class... Args void emplace(Args... args)C11這是更推薦的方式。它直接在棧頂構(gòu)造對(duì)象傳入的是構(gòu)造對(duì)象所需的參數(shù)包完全避免了任何額外的拷貝或移動(dòng)操作。stk.emplace(Charlie); // 直接在棧頂調(diào)用 std::string(const char*) 構(gòu)造函數(shù) // 對(duì)比 push(Charlie) 編譯器需要先根據(jù)字面量構(gòu)造一個(gè)臨時(shí)string對(duì)象然后再壓棧。實(shí)操心得對(duì)于非平凡類型如std::string, 自定義類優(yōu)先使用emplace。它不僅是性能最優(yōu)的選擇而且代碼意圖更清晰——明確表示“在容器內(nèi)構(gòu)造一個(gè)對(duì)象”。這在小對(duì)象上差異不大但在處理包含動(dòng)態(tài)內(nèi)存或文件句柄等資源的對(duì)象時(shí)能有效避免不必要的拷貝開銷。3.2 訪問棧頂元素topT top()和const T top() const返回棧頂元素的引用。這是一個(gè)非常高效的操作時(shí)間復(fù)雜度O(1)。std::stackint stk; stk.push(42); int topRef stk.top(); // 獲取引用可以修改棧頂元素 topRef 100; std::cout stk.top(); // 輸出 100 const std::stackint constStk stk; // int badRef constStk.top(); // 錯(cuò)誤不能通過const引用獲取非const引用 const int constRef constStk.top(); // 正確獲取const引用重要警告在調(diào)用top()或pop()之前必須確保棧非空。對(duì)空棧調(diào)用top()是未定義行為通常會(huì)導(dǎo)致程序崩潰。std::stackint emptyStk; // int val emptyStk.top(); // 危險(xiǎn)未定義行為 if (!emptyStk.empty()) { int val emptyStk.top(); // 安全 }3.3 彈出棧頂元素popvoid pop()移除棧頂元素。注意pop()函數(shù)不返回被移除的元素。這是C標(biāo)準(zhǔn)庫設(shè)計(jì)的一個(gè)歷史性決定主要是出于異常安全性的考慮。如果pop()返回元素那么在返回過程中如果拷貝構(gòu)造函數(shù)拋出異常元素就已經(jīng)從棧中移除了但調(diào)用者可能沒拿到導(dǎo)致數(shù)據(jù)丟失。std::stackint stk; stk.push(1); stk.push(2); stk.push(3); // 錯(cuò)誤用法int val stk.pop(); // pop()返回void編譯錯(cuò)誤 // 正確用法 int topValue stk.top(); // 先獲取棧頂元素的值 stk.pop(); // 再將其彈出這種top()pop()的組合是操作棧的標(biāo)準(zhǔn)模式。3.4 容量查詢empty和sizebool empty() const檢查棧是否為空。這是進(jìn)行top()或pop()操作前的安全檢查哨兵。size_t size() const返回棧中當(dāng)前元素的數(shù)量。一個(gè)典型的安全棧操作循環(huán)如下std::stackint stk; // ... 向stk中添加一些元素 ... while (!stk.empty()) { // 安全的循環(huán)條件 std::cout stk.top() ; // 訪問棧頂 stk.pop(); // 彈出棧頂 } // 循環(huán)結(jié)束后stk為空4. 棧的進(jìn)階用法、坑點(diǎn)與經(jīng)典算法實(shí)戰(zhàn)掌握了基本操作我們來看看棧在實(shí)際項(xiàng)目中更深入的用法和需要注意的陷阱。4.1 棧的遍歷與“破壞性”訪問棧的設(shè)計(jì)初衷是LIFO所以它不提供迭代器。你不能用for (auto it stk.begin(); ...)這樣的方式來遍歷。這是因?yàn)樘峁┑鲿?huì)暴露底層容器的結(jié)構(gòu)破壞棧的封裝性和LIFO語義。那么如何遍歷棧呢唯一安全的方式就是通過pop操作但這是破壞性的遍歷完棧就空了。std::stackint stk({1, 2, 3, 4, 5}); std::cout Stack elements (from top to bottom): ; // 方法1直接pop遍歷棧會(huì)被清空 while (!stk.empty()) { std::cout stk.top() ; stk.pop(); } std::cout std::endl; // 輸出: 5 4 3 2 1 // 此時(shí)stk為空如果你需要非破壞性地查看棧中所有元素比如調(diào)試一個(gè)常見的技巧是利用其底層容器。但請(qǐng)注意這破壞了封裝性應(yīng)僅用于調(diào)試。#include stack #include vector #include iostream // 這是一個(gè)專門用于調(diào)試的輔助函數(shù)生產(chǎn)環(huán)境慎用 templatetypename T, typename Container void debug_print_stack(const std::stackT, Container stk) { // 通過友元或繼承獲取底層容器是未定義行為。這里用一個(gè)取巧但有限制的方法 // 我們創(chuàng)建一個(gè)棧的副本然后通過pop來打印。 auto copy stk; std::cout [DEBUG] Stack (top-bottom): ; while (!copy.empty()) { std::cout copy.top() ; copy.pop(); } std::cout std::endl; } // 更直接但“黑科技”的方法是使用繼承不推薦因?yàn)閟td::stack的底層容器c是protected成員。 // templatetypename T, typename Container std::dequeT // class DebugStack : public std::stackT, Container { // public: // void print() const { // for (auto it this-c.rbegin(); it ! this-c.rend(); it) // std::cout *it ; // } // };4.2 經(jīng)典算法實(shí)戰(zhàn)括號(hào)匹配這是棧最經(jīng)典的面試題和應(yīng)用場景之一。問題給定一個(gè)只包含()[]{}的字符串判斷括號(hào)是否匹配有效。#include stack #include string #include unordered_map bool isValidParentheses(const std::string s) { std::stackchar stk; std::unordered_mapchar, char pairs { {), (}, {], [}, {}, {} }; for (char ch : s) { if (pairs.count(ch)) { // 當(dāng)前字符是右括號(hào) // 如果棧為空或者棧頂?shù)淖罄ㄌ?hào)不匹配當(dāng)前右括號(hào) if (stk.empty() || stk.top() ! pairs[ch]) { return false; } stk.pop(); // 匹配成功彈出左括號(hào) } else { // 當(dāng)前字符是左括號(hào) stk.push(ch); } } // 最后棧必須為空所有左括號(hào)都被匹配了 return stk.empty(); }算法解析遍歷字符串遇到左括號(hào)就壓棧遇到右括號(hào)就去檢查棧頂?shù)淖罄ㄌ?hào)是否與之匹配。匹配則彈出不匹配或?？談t直接失敗。遍歷結(jié)束后棧必須為空。這個(gè)算法的時(shí)間復(fù)雜度是O(n)空間復(fù)雜度在最壞情況下全是左括號(hào)也是O(n)。4.3 經(jīng)典算法實(shí)戰(zhàn)單調(diào)棧單調(diào)棧是棧的一種特殊用法它保持棧內(nèi)元素單調(diào)遞增或遞減常用于解決“下一個(gè)更大/更小元素”類問題。例如給定一個(gè)數(shù)組為每個(gè)元素找到其右邊第一個(gè)比它大的元素。#include vector #include stack using namespace std; vectorint nextGreaterElement(const vectorint nums) { int n nums.size(); vectorint res(n, -1); // 初始化結(jié)果數(shù)組為-1 stackint stk; // 棧里存放的是數(shù)組元素的索引而不是值 for (int i 0; i n; i) { // 當(dāng)前元素nums[i]比棧頂索引對(duì)應(yīng)的元素大 while (!stk.empty() nums[stk.top()] nums[i]) { int idx stk.top(); // 棧頂索引 stk.pop(); res[idx] nums[i]; // 找到了nums[idx]右邊第一個(gè)比它大的數(shù)nums[i] } stk.push(i); // 將當(dāng)前索引入棧 } // 循環(huán)結(jié)束后棧中剩下的索引對(duì)應(yīng)的元素其右邊沒有更大的元素結(jié)果保持為-1 return res; } // 示例輸入 [2, 1, 2, 4, 3] // 輸出 [4, 2, 4, -1, -1] // 解釋2右邊第一個(gè)比2大的是41右邊第一個(gè)比1大的是2第二個(gè)2右邊是44和3右邊沒有更大的。算法解析我們維護(hù)一個(gè)棧棧內(nèi)元素索引對(duì)應(yīng)的值是單調(diào)遞減的。遍歷數(shù)組對(duì)于當(dāng)前元素nums[i]它可能就是棧中某些元素的“下一個(gè)更大元素”。我們不斷彈出棧頂比nums[i]小的元素并更新它們的結(jié)果為nums[i]。最后將當(dāng)前索引入棧。這個(gè)算法的精妙之處在于每個(gè)元素最多入棧一次、出棧一次時(shí)間復(fù)雜度是O(n)。4.4 常見“坑點(diǎn)”與注意事項(xiàng)對(duì)空棧調(diào)用top()或pop()這是最經(jīng)典的運(yùn)行時(shí)錯(cuò)誤。務(wù)必養(yǎng)成習(xí)慣在調(diào)用前用empty()判斷。誤以為pop()會(huì)返回值牢記pop()返回void需要先top()再pop()。迭代器失效的錯(cuò)覺std::stack本身沒有迭代器所以不存在迭代器失效問題。但如果你通過非正規(guī)手段獲取了底層容器的迭代器那么任何push或pop操作都可能導(dǎo)致這些迭代器失效特別是底層容器是vector時(shí)。性能陷阱與底層容器選擇如果使用vector作為底層容器且頻繁push導(dǎo)致多次擴(kuò)容性能會(huì)急劇下降。可以通過reserve預(yù)分配空間來緩解。如果棧內(nèi)元素是復(fù)雜對(duì)象且使用push而非emplace可能會(huì)產(chǎn)生不必要的拷貝構(gòu)造開銷。棧的生命周期與對(duì)象析構(gòu)當(dāng)棧對(duì)象離開作用域被銷毀時(shí)它會(huì)自動(dòng)調(diào)用其內(nèi)部所有元素的析構(gòu)函數(shù)。如果棧中存放的是原始指針如int*,MyClass*棧的析構(gòu)不會(huì)釋放指針?biāo)赶虻膬?nèi)存這會(huì)導(dǎo)致內(nèi)存泄漏。這種情況下應(yīng)該使用智能指針std::unique_ptr或std::shared_ptr。// 錯(cuò)誤示例內(nèi)存泄漏 std::stackMyClass* ptrStack; ptrStack.push(new MyClass()); // ... 當(dāng)ptrStack析構(gòu)時(shí)指針被銷毀但new出來的MyClass對(duì)象沒有被delete // 正確示例使用智能指針 std::stackstd::unique_ptrMyClass safeStack; safeStack.push(std::make_uniqueMyClass()); // safeStack析構(gòu)時(shí)unique_ptr會(huì)自動(dòng)釋放內(nèi)存5. 棧在C項(xiàng)目中的典型應(yīng)用場景理解了原理和操作我們來看看棧在真實(shí)C項(xiàng)目中是如何大顯身手的。5.1 函數(shù)調(diào)用與遞歸實(shí)現(xiàn)這是棧最本質(zhì)的應(yīng)用。每次函數(shù)調(diào)用系統(tǒng)都會(huì)在調(diào)用棧上壓入一個(gè)“棧幀”包含返回地址、參數(shù)、局部變量等信息。函數(shù)返回時(shí)對(duì)應(yīng)的棧幀彈出。遞歸函數(shù)不過是這種機(jī)制的重復(fù)利用。當(dāng)你寫一個(gè)深度遞歸算法時(shí)本質(zhì)上是在消耗?？臻g。?？臻g是有限的通常幾MB過深的遞歸會(huì)導(dǎo)致“棧溢出”Stack Overflow這也是那個(gè)著名程序員問答網(wǎng)站名字的由來。int factorial(int n) { if (n 1) return 1; // 遞歸基 return n * factorial(n - 1); // 遞歸調(diào)用 } // 計(jì)算 factorial(5) 時(shí)調(diào)用棧會(huì)依次壓入 factorial(5), factorial(4), ..., factorial(1)5.2 深度優(yōu)先搜索DFS在圖和樹的遍歷中DFS天然適合用棧來實(shí)現(xiàn)遞歸版本的DFS也是利用了系統(tǒng)調(diào)用棧。void dfs_iterative(Node* root) { if (!root) return; std::stackNode* stk; stk.push(root); while (!stk.empty()) { Node* cur stk.top(); stk.pop(); process(cur); // 處理當(dāng)前節(jié)點(diǎn) // 將子節(jié)點(diǎn)逆序壓棧以保證遍歷順序這里假設(shè)先右后左以達(dá)到類似前序的效果 for (auto it cur-children.rbegin(); it ! cur-children.rend(); it) { if (*it) stk.push(*it); } } }5.3 表達(dá)式求值與語法分析編譯器前端處理算術(shù)表達(dá)式如3 4 * (2 - 1)時(shí)需要將其從中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式逆波蘭表達(dá)式或者直接求值。這個(gè)過程完全依賴于棧。中綴轉(zhuǎn)后綴使用一個(gè)操作符棧。遇到數(shù)字直接輸出遇到操作符則與棧頂操作符比較優(yōu)先級(jí)決定是入棧還是出棧。后綴表達(dá)式求值使用一個(gè)運(yùn)算數(shù)棧。遇到數(shù)字就入棧遇到操作符就從棧頂彈出兩個(gè)數(shù)字進(jìn)行運(yùn)算結(jié)果再入棧。5.4 撤銷Undo與重做Redo功能許多編輯器、圖形軟件都支持撤銷操作。這通常通過兩個(gè)棧來實(shí)現(xiàn)一個(gè)“操作?！盪ndo Stack和一個(gè)“重做?！盧edo Stack。用戶執(zhí)行一個(gè)操作將其壓入U(xiǎn)ndo棧并清空Redo棧。當(dāng)用戶觸發(fā)Undo時(shí)從Undo棧頂彈出操作并執(zhí)行其逆操作然后將該操作壓入Redo棧。當(dāng)用戶觸發(fā)Redo時(shí)從Redo棧頂彈出操作并執(zhí)行再將其壓回Undo棧。5.5 回溯算法在解決八皇后、迷宮尋路、數(shù)獨(dú)等問題時(shí)回溯算法需要記錄當(dāng)前的嘗試路徑。當(dāng)某條路徑走不通時(shí)需要回退到上一個(gè)決策點(diǎn)。這個(gè)“路徑記錄”和“回退”的過程用棧來實(shí)現(xiàn)非常直觀。// 偽代碼迷宮回溯 bool solveMaze(std::stackPosition path, Position current) { if (current is exit) return true; if (current is invalid or visited) return false; mark current as visited; path.push(current); // 記錄當(dāng)前位置 for (each direction dir) { Position next move(current, dir); if (solveMaze(path, next)) { return true; // 找到出口 } } // 所有方向都走不通回溯 path.pop(); // 從路徑中移除當(dāng)前位置 return false; }6. 自定義棧與性能考量雖然std::stack足夠優(yōu)秀但在某些極端性能敏感的場景如高頻交易、游戲引擎核心循環(huán)或者為了教學(xué)目的我們可能需要自己實(shí)現(xiàn)一個(gè)棧。6.1 基于數(shù)組的簡單棧實(shí)現(xiàn)這是一個(gè)固定容量的棧實(shí)現(xiàn)簡單性能極高連續(xù)內(nèi)存緩存友好。template typename T, size_t Capacity class ArrayStack { private: T data[Capacity]; size_t topIndex; // 指向棧頂元素的下一個(gè)位置 public: ArrayStack() : topIndex(0) {} bool empty() const { return topIndex 0; } size_t size() const { return topIndex; } bool full() const { return topIndex Capacity; } // 固定容量棧特有的方法 void push(const T value) { if (full()) { throw std::overflow_error(Stack is full!); } data[topIndex] value; // 在topIndex位置構(gòu)造然后遞增 } void pop() { if (empty()) { throw std::underflow_error(Stack is empty!); } --topIndex; // 只需遞減索引析構(gòu)由后續(xù)的push或析構(gòu)函數(shù)處理 // 注意對(duì)于非平凡類型這里可能需要調(diào)用 data[topIndex].~T() } T top() { if (empty()) { throw std::underflow_error(Stack is empty!); } return data[topIndex - 1]; } const T top() const { // const版本同上 if (empty()) throw std::underflow_error(Stack is empty!); return data[topIndex - 1]; } };優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)極致性能無動(dòng)態(tài)內(nèi)存分配內(nèi)存局部性極佳。缺點(diǎn)容量固定不夠靈活。如果Capacity預(yù)估不準(zhǔn)要么浪費(fèi)內(nèi)存要么容易溢出。6.2 基于動(dòng)態(tài)數(shù)組的棧實(shí)現(xiàn)更接近std::stack基于vector的實(shí)現(xiàn)支持動(dòng)態(tài)擴(kuò)容。template typename T class VectorStack { private: std::vectorT data; public: bool empty() const { return data.empty(); } size_t size() const { return data.size(); } void push(const T value) { data.push_back(value); } void push(T value) { data.push_back(std::move(value)); } template class... Args void emplace(Args... args) { data.emplace_back(std::forwardArgs(args)...); } void pop() { if (empty()) throw std::underflow_error(Stack is empty!); data.pop_back(); } T top() { if (empty()) throw std::underflow_error(Stack is empty!); return data.back(); } const T top() const { if (empty()) throw std::underflow_error(Stack is empty!); return data.back(); } // 可以添加一些額外功能比如預(yù)分配內(nèi)存 void reserve(size_t new_cap) { data.reserve(new_cap); } };這個(gè)實(shí)現(xiàn)幾乎就是std::stackT, std::vectorT的簡化版。通過自己實(shí)現(xiàn)你可以更深刻地理解std::stack作為容器適配器的設(shè)計(jì)思路它只是對(duì)底層序列容器back,push_back,pop_back等接口的一層薄包裝。6.3 性能對(duì)比與選型建議在實(shí)際項(xiàng)目中如何選擇99%的情況直接使用std::stack。它的性能、安全性和通用性已經(jīng)過千錘百煉。對(duì)性能有極致要求且棧容量上限明確考慮使用固定大小的數(shù)組棧如ArrayStack或者使用std::stack并指定std::vector作為底層容器并提前調(diào)用reserve()。需要避免內(nèi)存分配抖動(dòng)使用std::stack并指定std::deque默認(rèn)或者使用內(nèi)存池自定義分配器。棧中元素生命周期特殊或需要復(fù)雜管理考慮在棧中存儲(chǔ)智能指針或者自定義具有特定析構(gòu)邏輯的包裝器。一個(gè)容易被忽略的性能點(diǎn)是對(duì)于小對(duì)象如int,doublestd::deque由于內(nèi)存分塊其push_back和pop_back的常數(shù)時(shí)間開銷可能略高于std::vector。但在對(duì)象較大或數(shù)量變化劇烈時(shí)deque的優(yōu)勢(shì)就體現(xiàn)出來了。我的經(jīng)驗(yàn)法則是先使用默認(rèn)的std::deque只有在性能分析工具如perf, VTune明確指向棧操作是瓶頸且瓶頸在于內(nèi)存分配時(shí)才考慮更換底層容器或自定義實(shí)現(xiàn)。