C++ `std::stack` 用法详解（2025 版，超详细）

std::stack 是 C++ 标准模板库（STL）提供的一种栈数据结构，遵循后进先出（LIFO, Last In First Out）原则，位于 <stack> 头文件。它基于适配器模式，默认底层容器为 std::deque，也可指定 std::vector 或 std::list。本教程从基础概念到高级应用，详细讲解 std::stack 的用法、原理和场景，结合代码示例，适合初学者到进阶开发者。内容基于 C++20 标准（截至 2025 年 10 月），参考 CPPReference 和社区资源（如 CSDN、GeeksforGeeks）。

第一阶段：`std::stack` 基础概念（初学者级别）

1.1 什么是 `std::stack`？

定义：std::stack 是 STL 提供的容器适配器，封装了底层容器（如 deque），提供栈操作接口：入栈（push）、出栈（pop）、访问栈顶（top）等。
核心特性：
LIFO：最后入栈的元素最先出栈。
限制访问：只能操作栈顶，无法直接访问中间元素。
无迭代器：不像 std::vector 支持随机访问，栈只提供栈顶操作。
头文件：

  #include <stack>

类模板：

  template <class T, class Container = std::deque<T>>
  class stack;

T：存储元素类型（如 int、std::string）。
Container：底层容器（默认 std::deque，支持 std::vector、std::list）。

类比：std::stack 像一叠盘子，只能从顶部放或取。

1.2 核心操作

函数	功能	时间复杂度
`push(value)`	入栈（添加元素到栈顶）	O(1)（均摊）
`pop()`	出栈（移除栈顶元素，无返回值）	O(1)
`top()`	访问栈顶元素	O(1)
`empty()`	检查栈是否为空	O(1)
`size()`	返回元素个数	O(1)
`swap(other)`	交换两个栈内容	O(1)（依赖底层容器）

注意：

pop() 不返回栈顶值，需先用 top() 获取。
访问空栈的 top() 或 pop() 导致未定义行为，需先检查 empty()。

1.3 基本示例

#include <iostream>
#include <stack>
int main() {
    std::stack<int> s;
    s.push(1); // 入栈 1
    s.push(2); // 入栈 2
    s.push(3); // 入栈 3
    std::cout << "Top: " << s.top() << std::endl; // 输出栈顶
    s.pop(); // 移除 3
    std::cout << "Top after pop: " << s.top() << std::endl;
    std::cout << "Size: " << s.size() << std::endl;
    std::cout << "Empty: " << (s.empty() ? "Yes" : "No") << std::endl;
    return 0;
}

输出：

Top: 3
Top after pop: 2
Size: 2
Empty: No

第二阶段：`std::stack` 原理与实现（中级）

2.1 底层容器

std::stack 是容器适配器，依赖底层容器实现操作。
默认容器：std::deque（双端队列，高效尾部操作）。
可选容器：
std::vector：适合动态扩展，但尾部插入稍慢。
std::list：适合频繁插入/删除，但无随机访问。
自定义容器：需满足 STL 容器要求（back()、push_back()、pop_back()）。
示例（指定容器）：

#include <stack>
#include <vector>
std::stack<int, std::vector<int>> s; // 使用 vector 作为底层容器

2.2 实现原理

适配器模式：std::stack 封装底层容器，仅暴露栈接口。
源码简化（参考 C++20）：

  template <class T, class Container = std::deque<T>>
  class stack {
  protected:
      Container c; // 底层容器
  public:
      void push(const T& value) { c.push_back(value); }
      void pop() { c.pop_back(); }
      T& top() { return c.back(); }
      bool empty() const { return c.empty(); }
      size_t size() const { return c.size(); }
  };

性能：
依赖底层容器：deque 和 vector 的尾部操作是 O(1)。
空间复杂度：O(n)，n 为元素个数。

2.3 异常安全

push：若底层容器分配失败，可能抛出 std::bad_alloc。
pop/top：不抛异常，但空栈操作导致未定义行为。
最佳实践：操作前检查 !s.empty()。

第三阶段：高级用法与优化（高级）

3.1 自定义类型栈

要求：类型需支持拷贝或移动构造。
示例（自定义类）：

#include <iostream>
#include <stack>
#include <string>
struct Student {
    std::string name;
    int id;
    Student(std::string n, int i) : name(n), id(i) {}
    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        return os << s.name << ": " << s.id;
    }
};
int main() {
    std::stack<Student> s;
    s.push({"Alice", 1});
    s.push({"Bob", 2});
    std::cout << "Top: " << s.top() << std::endl;
    s.pop();
    std::cout << "Top after pop: " << s.top() << std::endl;
    return 0;
}

输出：

Top: Bob: 2
Top after pop: Alice: 1

3.2 自定义容器

示例（用 std::list）：

#include <stack>
#include <list>
std::stack<int, std::list<int>> s; // 使用 list
s.push(1); // 底层调用 list::push_back

3.3 性能优化

选择容器：
std::deque（默认）：适合大多数场景，尾部操作高效。
std::vector：若需要连续内存（缓存友好），但扩容可能导致拷贝。
std::list：若频繁插入/删除，但内存开销稍大。
预分配（间接）：
std::stack 无 reserve，但可通过自定义容器预分配：
cpp std::vector<int> vec; vec.reserve(1000); // 预分配 std::stack<int, std::vector<int>> s(std::move(vec));
避免空栈操作：

  if (!s.empty()) {
      s.pop();
  }

3.4 比较与交换

比较：支持 ==、!= 等（比较底层容器）。
交换：s1.swap(s2)，高效交换底层容器。

std::stack<int> s1, s2;
s1.swap(s2); // O(1)

第四阶段：实际应用场景 + 举例

4.1 场景 1：表达式求值（后缀表达式）

栈常用于解析表达式（如 3 + 4 * 2 转为后缀 3 4 2 * +）。

#include <iostream>
#include <stack>
#include <string>
int evaluate_postfix(const std::string& expr) {
    std::stack<int> s;
    for (char c : expr) {
        if (isdigit(c)) {
            s.push(c - '0');
        } else {
            int b = s.top(); s.pop();
            int a = s.top(); s.pop();
            if (c == '+') s.push(a + b);
            else if (c == '*') s.push(a * b);
        }
    }
    return s.top();
}
int main() {
    std::string expr = "342*+"; // (3 + 4 * 2)
    std::cout << "Result: " << evaluate_postfix(expr) << std::endl;
    return 0;
}

输出：Result: 11

4.2 场景 2：括号匹配

检查括号是否匹配（如 ({[]})）。

#include <iostream>
#include <stack>
#include <string>
bool is_valid_parentheses(const std::string& s) {
    std::stack<char> stack;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.empty()) return false;
            char top = stack.top(); stack.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.empty();
}
int main() {
    std::string expr = "{[()]}";
    std::cout << "Valid: " << (is_valid_parentheses(expr) ? "Yes" : "No") << std::endl;
    return 0;
}

输出：Valid: Yes

4.3 场景 3：任务撤销（Undo）

栈记录操作历史，支持撤销。

#include <iostream>
#include <stack>
#include <string>
int main() {
    std::stack<std::string> undo_stack;
    undo_stack.push("Edit 1");
    undo_stack.push("Edit 2");
    std::cout << "Undo: " << undo_stack.top() << std::endl; // Edit 2
    undo_stack.pop();
    std::cout << "Undo: " << undo_stack.top() << std::endl; // Edit 1
    return 0;
}

输出：

Undo: Edit 2
Undo: Edit 1

第五阶段：常见问题与最佳实践

5.1 常见问题

问题	原因	解决方案
未定义行为	空栈调用 `top()` 或 `pop()`	检查 `!s.empty()`。
性能瓶颈	底层容器扩容	用 `std::vector` 预分配（`reserve`）。
头文件缺失	未包含 `<stack>`	添加 `#include <stack>`。
自定义类型失败	无拷贝/移动构造	实现构造/赋值运算符。

5.2 最佳实践

检查空栈：操作前用 s.empty()。
选择容器：默认 std::deque 适合大多数场景。
异常安全：捕获 push 的 std::bad_alloc。
调试：打印栈内容（需临时 pop 并 push）。

  while (!s.empty()) {
      std::cout << s.top() << " "; s.pop();
  }

替代：若需先进先出，考虑 std::queue。

5.3 性能测试

#include <iostream>
#include <stack>
#include <chrono>
int main() {
    std::stack<int> s;
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000000; i++) {
        s.push(i);
    }
    while (!s.empty()) {
        s.pop();
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Time: " 
              << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() 
              << " us" << std::endl;
    return 0;
}

输出（示例，i7-12700）：Time: ~5000 us（100 万次 push/pop）。

第六阶段：资源与进阶学习

学习路径：
1 天：掌握基本操作（push/pop/top）。
2-3 天：实践场景（表达式、括号匹配）。
1 周：自定义类型、容器优化。
资源：
官方：CPPReference (std::stack, https://en.cppreference.com/w/cpp/container/stack).
英文：GeeksforGeeks (https://www.geeksforgeeks.org/stack-in-cpp-stl/).
中文：CSDN (https://blog.csdn.net/weixin_43883374/article/details/106926058) – STL 容器。
书籍：《C++ Primer》（Lippman），第 9 章。
视频：YouTube “C++ STL Stack” by The Cherno。
工具：GCC 14+、Clang 17+、MSVC 2022、VS Code。

总结：std::stack 是高效的 LIFO 数据结构，基于 std::deque，提供简单接口。适合表达式求值、撤销操作等场景。优先使用 STL 实现，注意空栈检查和容器选择。若有具体问题（如性能优化），欢迎提供代码，我可进一步指导！

include

bool is_valid_parentheses(const std::string& s) {
std::stack stack;
for (char c : s) {
if (c == ‘(‘ || c == ‘{‘ || c == ‘[‘) {
stack.push(c);
} else {
if (stack.empty()) return false;
char top = stack.top(); stack.pop();
if ((c == ‘)’ && top != ‘(‘) ||
(c == ‘}’ && top != ‘{‘) ||
(c == ‘]’ && top != ‘[‘)) {
return false;
}
}
}
return stack.empty();
}

int main() {
std::string expr = “{[()]}”;
std::cout << “Valid: ” << (is_valid_parentheses(expr) ? “Yes” : “No”) << std::endl; return 0; }

c++ stack用法详解

C++ `std::stack` 用法详解（2025 版，超详细）

第一阶段：`std::stack` 基础概念（初学者级别）

1.1 什么是 `std::stack`？

1.2 核心操作

1.3 基本示例

第二阶段：`std::stack` 原理与实现（中级）

2.1 底层容器

2.2 实现原理

2.3 异常安全

第三阶段：高级用法与优化（高级）

3.1 自定义类型栈

3.2 自定义容器

3.3 性能优化

3.4 比较与交换

第四阶段：实际应用场景 + 举例

4.1 场景 1：表达式求值（后缀表达式）

4.2 场景 2：括号匹配

4.3 场景 3：任务撤销（Undo）

第五阶段：常见问题与最佳实践

5.1 常见问题

5.2 最佳实践

5.3 性能测试

第六阶段：资源与进阶学习

include

include

include

C++ 简介

C++ 容器类 unordered_set

C++ 标准库typeinfo

C++ 标准库

C++ 排序函数 sort(),qsort()的用法

C++ 接口（抽象类）

发表回复取消回复

C++ std::stack 用法详解（2025 版，超详细）

第一阶段：std::stack 基础概念（初学者级别）

1.1 什么是 std::stack？

1.2 核心操作

1.3 基本示例

第二阶段：std::stack 原理与实现（中级）

2.1 底层容器

2.2 实现原理

2.3 异常安全

第三阶段：高级用法与优化（高级）

3.1 自定义类型栈

3.2 自定义容器

3.3 性能优化

3.4 比较与交换

第四阶段：实际应用场景 + 举例

4.1 场景 1：表达式求值（后缀表达式）

4.2 场景 2：括号匹配

4.3 场景 3：任务撤销（Undo）

第五阶段：常见问题与最佳实践

5.1 常见问题

5.2 最佳实践

5.3 性能测试

第六阶段：资源与进阶学习

include

include

include

类似文章

发表回复 取消回复

C++ `std::stack` 用法详解（2025 版，超详细）

第一阶段：`std::stack` 基础概念（初学者级别）

1.1 什么是 `std::stack`？

第二阶段：`std::stack` 原理与实现（中级）

发表回复取消回复