在C++標(biāo)準(zhǔn)模板庫(kù)（STL）中，stack（棧）是一種遵循“后進(jìn)先出”（LIFO, Last In First Out）規(guī)則的容器適配器。它并非獨(dú)立的容器，而是基于其他基礎(chǔ)容器（如deque、vector、list）封裝實(shí)現(xiàn)，屏蔽了部分基礎(chǔ)容器的接口，僅暴露符合棧邏輯的操作。stack在日常開(kāi)發(fā)中應(yīng)用廣泛，例如表達(dá)式求值、函數(shù)調(diào)用棧模擬、括號(hào)匹配等場(chǎng)景。本文將從stack的底層實(shí)現(xiàn)出發(fā)，詳細(xì)講解其核心特性、常用接口，結(jié)合實(shí)戰(zhàn)案例演示具體用法，并梳理使用注意事項(xiàng)，幫助大家徹底掌握這一基礎(chǔ)容器適配器。

一、stack 核心原理與特性

要理解stack的行為邏輯，首先需要明確其“容器適配器”的本質(zhì)——它不直接管理內(nèi)存，而是復(fù)用基礎(chǔ)容器的內(nèi)存管理和核心操作，僅對(duì)外提供統(tǒng)一的棧操作接口。

1.1 底層實(shí)現(xiàn)：基于基礎(chǔ)容器的適配

stack的底層默認(rèn)依賴deque容器實(shí)現(xiàn)（C++標(biāo)準(zhǔn)推薦，大部分編譯器默認(rèn)如此）。這是因?yàn)閐eque支持高效的尾部插入/刪除操作（push_back、pop_back），且內(nèi)存分配靈活，能很好地匹配棧的核心需求。同時(shí)，C++也支持指定其他符合要求的基礎(chǔ)容器（需支持push_back、pop_back、back、empty、size這5個(gè)核心接口），例如vector、list等。

stack的適配邏輯非常簡(jiǎn)單：將棧的“壓棧”對(duì)應(yīng)基礎(chǔ)容器的push_back（尾部插入），“出棧”對(duì)應(yīng)基礎(chǔ)容器的pop_back（尾部刪除），“棧頂元素訪問(wèn)”對(duì)應(yīng)基礎(chǔ)容器的back（訪問(wèn)尾部元素）。通過(guò)這種適配，屏蔽了基礎(chǔ)容器的頭部操作、隨機(jī)訪問(wèn)等接口，嚴(yán)格保證“后進(jìn)先出”的規(guī)則。

1.2 核心特性總結(jié)

• 后進(jìn)先出（LIFO）：最后插入的元素最先被訪問(wèn)，僅允許在棧頂進(jìn)行插入和刪除操作；
• 容器適配器：不獨(dú)立管理內(nèi)存，依賴基礎(chǔ)容器（默認(rèn)deque）實(shí)現(xiàn)核心功能；
• 接口受限：僅暴露棧相關(guān)接口（壓棧、出棧、訪問(wèn)棧頂、判空、獲取大?。?，不支持迭代器遍歷，無(wú)法直接訪問(wèn)棧中間的元素；
• 高效操作：壓棧（push）、出棧（pop）、訪問(wèn)棧頂（top）的時(shí)間復(fù)雜度均為O(1)（依賴基礎(chǔ)容器的尾部操作效率）；
• 無(wú)默認(rèn)初始化元素：創(chuàng)建空stack時(shí)無(wú)默認(rèn)元素，需手動(dòng)壓棧添加元素。

1.3 支持的基礎(chǔ)容器

stack可指定的基礎(chǔ)容器需滿足“支持尾部插入/刪除、訪問(wèn)尾部元素、判空、獲取大小”這5個(gè)核心接口，STL中符合要求的容器有3個(gè)：

#include <stack>
  #include <vector>
    #include <list>
      // 基于vector的stack
      std::stack<int, std::vector<int>> stack_vec;
        // 基于list的stack
        std::stack<int, std::list<int>> stack_list;
          // 基于默認(rèn)deque的stack（最常用）
          std::stack<int> stack_deque;
            }

二、C++ stack 常用接口詳解

stack的接口設(shè)計(jì)簡(jiǎn)潔直觀，僅包含與棧邏輯相關(guān)的核心操作。使用stack前，需包含頭文件 <stack>，并使用std命名空間（或顯式指定std::stack）。

2.1 構(gòu)造與析構(gòu)

2.2 核心操作（壓棧、出棧、訪問(wèn)棧頂）

這是stack最常用的接口，直接對(duì)應(yīng)棧的核心邏輯：

2.3 容量相關(guān)

2.4 賦值操作

2.5 接口綜合示例

#include <stack>
  #include <iostream>
    using namespace std;
    int main() {
    // 1. 構(gòu)造空stack（默認(rèn)deque為基礎(chǔ)容器）
    stack<int> s;
      // 2. 壓棧操作
      s.push(10);
      s.push(20);
      s.emplace(30); // 直接構(gòu)造，效率更高
      cout << "棧大小：" << s.size() << endl; // 輸出：3
      cout << "棧頂元素：" << s.top() << endl; // 輸出：30（最后壓入的元素）
      // 3. 修改棧頂元素（非const情況下）
      s.top() = 35;
      cout << "修改后棧頂元素：" << s.top() << endl; // 輸出：35
      // 4. 出棧操作
      s.pop();
      cout << "出棧后棧頂元素：" << s.top() << endl; // 輸出：20
      cout << "出棧后棧大?。? << s.size() << endl; // 輸出：2
      // 5. 判空與清空（stack無(wú)clear接口，需通過(guò)pop循環(huán)清空）
      while (!s.empty()) {
      cout << "出棧元素：" << s.top() << endl;
      s.pop();
      }
      cout << "清空后棧是否為空：" << (s.empty() ? "是" : "否") << endl; // 輸出：是
      // 6. 拷貝構(gòu)造與賦值
      stack<int> s1;
        s1.push(1);
        s1.push(2);
        stack<int> s2(s1); // 拷貝構(gòu)造
          cout << "s2棧頂元素：" << s2.top() << endl; // 輸出：2
          stack<int> s3;
            s3 = s1; // 拷貝賦值
            cout << "s3棧大?。? << s3.size() << endl; // 輸出：2
            return 0;
            }

輸出結(jié)果：

棧大?。?
棧頂元素：30
修改后棧頂元素：35
出棧后棧頂元素：20
出棧后棧大?。?
出棧元素：20
出棧元素：10
清空后棧是否為空：是
s2棧頂元素：2
s3棧大?。?

三、stack 實(shí)戰(zhàn)案例

stack的“后進(jìn)先出”特性使其在多個(gè)經(jīng)典場(chǎng)景中不可或缺，以下通過(guò)3個(gè)實(shí)戰(zhàn)案例演示其實(shí)際應(yīng)用：

3.1 場(chǎng)景1：括號(hào)匹配驗(yàn)證

需求：給定一個(gè)只包含括號(hào)（‘(’、‘)’、‘{’、‘}’、‘[’、‘]’）的字符串，判斷字符串中的括號(hào)是否完全匹配（左右括號(hào)類型一致、順序正確、無(wú)多余括號(hào)）。

思路：

• 遍歷字符串，遇到左括號(hào)（‘(’、‘{’、‘[’）時(shí)，將其壓入棧中；
• 遇到右括號(hào)時(shí)，判斷棧是否為空（為空則無(wú)匹配的左括號(hào)，返回false），或棧頂左括號(hào)與當(dāng)前右括號(hào)類型不匹配（返回false）；若匹配，則彈出棧頂左括號(hào)；
• 遍歷結(jié)束后，棧需為空（否則存在未匹配的左括號(hào)，返回false），否則返回true。

#include <stack>
  #include <iostream>
    #include <vector>
      #include <string>
        using namespace std;
        int evalRPN(vector<string>& tokens) {
          stack<int> st;
            for (const string& token : tokens) {
            // 遇到運(yùn)算符
            if (token == "+" || token == "-" || token == "*" || token == "/") {
            // 彈出兩個(gè)操作數(shù)（注意順序：先彈右操作數(shù)，后彈左操作數(shù)）
            int right = st.top();
            st.pop();
            int left = st.top();
            st.pop();
            // 計(jì)算結(jié)果并壓棧
            if (token == "+") {
            st.push(left + right);
            } else if (token == "-") {
            st.push(left - right);
            } else if (token == "*") {
            st.push(left * right);
            } else if (token == "/") {
            // 除法向下取整（C++中負(fù)數(shù)除法需注意，此處按題目要求處理）
            st.push(left / right);
            }
            } else {
            // 遇到數(shù)字，轉(zhuǎn)換為整數(shù)壓棧
            st.push(stoi(token));
            }
            }
            // 棧中僅剩結(jié)果
            return st.top();
            }
            int main() {
            vector<string> tokens1 = {"2","1","+","3","*"}; // 等價(jià)于 (2+1)*3 = 9
              vector<string> tokens2 = {"4","13","5","/","+"}; // 等價(jià)于 4 + (13/5) = 6
                vector<string> tokens3 = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"}; // 等價(jià)于 ((10*(6/(9+3*-11)))+17)+5 = 22
                  cout << "表達(dá)式1結(jié)果：" << evalRPN(tokens1) << endl; // 9
                  cout << "表達(dá)式2結(jié)果：" << evalRPN(tokens2) << endl; // 6
                  cout << "表達(dá)式3結(jié)果：" << evalRPN(tokens3) << endl; // 22
                  return 0;
                  }

3.2 場(chǎng)景2：逆波蘭表達(dá)式求值

需求：逆波蘭表達(dá)式（后綴表達(dá)式）是一種不含括號(hào)的表達(dá)式，運(yùn)算符位于兩個(gè)操作數(shù)之后，計(jì)算規(guī)則簡(jiǎn)單。給定一個(gè)逆波蘭表達(dá)式的字符串?dāng)?shù)組，求其結(jié)果（假設(shè)表達(dá)式合法，僅包含數(shù)字和+、-、*、/四種運(yùn)算符，除法向下取整）。

思路：

• 遍歷字符串?dāng)?shù)組，遇到數(shù)字時(shí)，將其轉(zhuǎn)換為整數(shù)壓入棧中；
• 遇到運(yùn)算符時(shí)，彈出棧頂兩個(gè)元素（注意：先彈出的是右操作數(shù)，后彈出的是左操作數(shù)）；
• 計(jì)算兩個(gè)操作數(shù)與運(yùn)算符的結(jié)果，將結(jié)果壓入棧中；
• 遍歷結(jié)束后，棧中僅剩一個(gè)元素，即為表達(dá)式的結(jié)果。

#include <stack>
  #include <iostream>
    #include <string>
      using namespace std;
      // 模擬函數(shù)調(diào)用（壓棧）
      void callFunction(stack<string>& callStack, const string& funcName) {
        callStack.push(funcName);
        cout << "調(diào)用函數(shù)：" << funcName << endl;
        }
        // 模擬函數(shù)返回（出棧）
        void returnFunction(stack<string>& callStack) {
          if (callStack.empty()) {
          cout << "無(wú)正在執(zhí)行的函數(shù)，無(wú)法返回！" << endl;
          return;
          }
          string funcName = callStack.top();
          callStack.pop();
          cout << "返回函數(shù)：" << funcName << endl;
          }
          int main() {
          stack<string> callStack;
            // 模擬函數(shù)調(diào)用流程
            callFunction(callStack, "main()");
            callFunction(callStack, "funcA()");
            callFunction(callStack, "funcB()");
            returnFunction(callStack); // funcB返回
            callFunction(callStack, "funcC()");
            returnFunction(callStack); // funcC返回
            returnFunction(callStack); // funcA返回
            returnFunction(callStack); // main返回
            returnFunction(callStack); // 無(wú)函數(shù)可返回
            return 0;
            }

3.3 場(chǎng)景3：模擬函數(shù)調(diào)用棧

需求：模擬程序的函數(shù)調(diào)用過(guò)程，記錄函數(shù)的調(diào)用順序和返回順序（函數(shù)調(diào)用時(shí)壓棧，函數(shù)返回時(shí)出棧）。

#include <stack>
  #include <iostream>
    #include <string>
      using namespace std;
      // 模擬函數(shù)調(diào)用（壓棧）
      void callFunction(stack<string>& callStack, const string& funcName) {
        callStack.push(funcName);
        cout << "調(diào)用函數(shù)：" << funcName << endl;
        }
        // 模擬函數(shù)返回（出棧）
        void returnFunction(stack<string>& callStack) {
          if (callStack.empty()) {
          cout << "無(wú)正在執(zhí)行的函數(shù)，無(wú)法返回！" << endl;
          return;
          }
          string funcName = callStack.top();
          callStack.pop();
          cout << "返回函數(shù)：" << funcName << endl;
          }
          int main() {
          stack<string> callStack;
            // 模擬函數(shù)調(diào)用流程
            callFunction(callStack, "main()");
            callFunction(callStack, "funcA()");
            callFunction(callStack, "funcB()");
            returnFunction(callStack); // funcB返回
            callFunction(callStack, "funcC()");
            returnFunction(callStack); // funcC返回
            returnFunction(callStack); // funcA返回
            returnFunction(callStack); // main返回
            returnFunction(callStack); // 無(wú)函數(shù)可返回
            return 0;
            }

輸出結(jié)果：

調(diào)用函數(shù)：main()
調(diào)用函數(shù)：funcA()
調(diào)用函數(shù)：funcB()
返回函數(shù)：funcB()
調(diào)用函數(shù)：funcC()
返回函數(shù)：funcC()
返回函數(shù)：funcA()
返回函數(shù)：main()
無(wú)正在執(zhí)行的函數(shù)，無(wú)法返回！

四、stack 使用注意事項(xiàng)

• 棧為空時(shí)禁止調(diào)用pop()和top()：stack的pop()和top()接口在棧為空時(shí)調(diào)用會(huì)導(dǎo)致未定義行為（程序崩潰或異常）。因此，在調(diào)用這兩個(gè)接口前，必須通過(guò)empty()判斷棧是否為空。
• stack無(wú)迭代器，無(wú)法遍歷：stack的設(shè)計(jì)初衷是嚴(yán)格遵循LIFO規(guī)則，因此未暴露迭代器接口，無(wú)法直接遍歷棧中的所有元素。若需遍歷，需通過(guò)pop()將元素依次彈出并記錄（但會(huì)清空棧），或自定義基于基礎(chǔ)容器的棧結(jié)構(gòu)。
• stack無(wú)clear()接口，清空需手動(dòng)循環(huán)pop()：與vector、deque等容器不同，stack未提供clear()接口。若需清空棧，需通過(guò)while循環(huán)調(diào)用pop()，直到棧為空。
• 選擇合適的基礎(chǔ)容器：
  • 默認(rèn)的deque基礎(chǔ)容器適用于大多數(shù)場(chǎng)景，兼顧效率和靈活性；
  • 若棧元素?cái)?shù)量穩(wěn)定，無(wú)需頻繁擴(kuò)容，可選擇vector作為基礎(chǔ)容器（內(nèi)存連續(xù)，緩存命中率高）；
  • 若需頻繁插入/刪除且元素?cái)?shù)量波動(dòng)大，可選擇list作為基礎(chǔ)容器（無(wú)擴(kuò)容開(kāi)銷）。
• top()返回的是引用，可修改棧頂元素：stack的top()返回棧頂元素的非const引用，因此可以通過(guò)top()修改棧頂元素的值。若需禁止修改，可使用const stack。
• 元素類型需支持拷貝/移動(dòng)：stack的push()接口會(huì)拷貝/移動(dòng)元素到基礎(chǔ)容器中，因此元素類型必須支持拷貝構(gòu)造或移動(dòng)構(gòu)造。若元素為自定義類型，需確保正確實(shí)現(xiàn)拷貝/移動(dòng)語(yǔ)義。
• 線程安全性：與所有STL容器一致，stack不保證線程安全。多線程環(huán)境下并發(fā)讀寫棧時(shí)，需手動(dòng)加鎖（如使用std::mutex）保護(hù)棧的操作。

五、總結(jié)

stack是C++ STL中基于基礎(chǔ)容器封裝的“后進(jìn)先出”容器適配器，核心優(yōu)勢(shì)是接口簡(jiǎn)潔、操作高效（壓棧、出棧、訪問(wèn)棧頂均為O(1)）。它不獨(dú)立管理內(nèi)存，而是復(fù)用deque、vector、list等基礎(chǔ)容器的功能，嚴(yán)格屏蔽了非LIFO相關(guān)的接口，確保數(shù)據(jù)操作的規(guī)范性。

stack的經(jīng)典應(yīng)用場(chǎng)景包括括號(hào)匹配、表達(dá)式求值、函數(shù)調(diào)用棧模擬等，掌握其核心接口和使用注意事項(xiàng)，能幫助我們快速解決這類“后進(jìn)先出”相關(guān)的問(wèn)題。使用時(shí)需注意：調(diào)用pop()和top()前先判空、無(wú)迭代器無(wú)法遍歷、清空需手動(dòng)循環(huán)pop()等細(xì)節(jié)，避免出現(xiàn)未定義行為。

到此這篇關(guān)于C++ stack 全面解析與實(shí)戰(zhàn)指南 - 指南的文章就介紹到這了,更多相關(guān)C++ stack實(shí)戰(zhàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論