c++ stack STL

### C++ STL 中 `stack` 的用法与实现 #### 1. 基本概念 C++ 标准模板库 (STL) 提供了一个容器适配器类 `std::stack`，它实现了栈的数据结构。栈是一种后进先出（Last In First Out, LIFO）的线性数据结构。 `std::stack` 是基于其他底层容器（如 `std::vector`, `std::deque`, 或 `std::list`）构建的，默认情况下使用的是 `std::deque`[^1]。 --- #### 2. 主要成员函数及其功能 以下是 `std::stack` 的主要成员函数： ##### （1）`size()` 函数 返回当前栈中元素的数量。如果栈为空，则返回值为零。 ```cpp #include <iostream> #include <stack> int main() { std::stack<int> st; st.push(1); st.push(2); std::cout << "Stack size: " << st.size() << std::endl; // 输出 Stack size: 2 } ``` 此操作的时间复杂度为 O(1)。 --- ##### （2）`top()` 函数 访问栈顶元素而不移除该元素。如果栈为空，则行为未定义。 ```cpp #include <iostream> #include <stack> int main() { std::stack<int> st; st.push(10); st.push(20); std::cout << "Top element is: " << st.top() << std::endl; // 输出 Top element is: 20 } ``` 时间复杂度同样为 O(1)[^2]。 --- ##### （3）`push(T value)` 函数 向栈顶部压入一个新的元素。 ```cpp #include <iostream> #include <stack> int main() { std::stack<int> st; st.push(5); // 向栈中压入元素 5 st.push(10); // 向栈中压入元素 10 while (!st.empty()) { // 当栈不为空时循环弹出并打印 std::cout << st.top() << ' '; st.pop(); } // 输出：10 5 } ``` 时间复杂度为 O(1)[^3]。 --- ##### （4）`pop()` 函数 删除栈顶元素。注意，这个方法不会返回被删除的元素；若需要获取栈顶元素，在调用 `pop()` 方法前应先调用 `top()`。 ```cpp #include <iostream> #include <stack> int main() { std::stack<int> st; st.push(1); st.push(2); st.pop(); // 移除栈顶元素 2 std::cout << "After pop, top element is: " << st.top() << std::endl; // 输出 After pop, top element is: 1 } ``` --- ##### （5）`empty()` 函数 判断栈是否为空。如果栈为空则返回 `true`，否则返回 `false`。 ```cpp #include <iostream> #include <stack> int main() { std::stack<int> st; if (st.empty()) std::cout << "The stack is empty." << std::endl; // 输出 The stack is empty. st.push(1); if (!st.empty()) std::cout << "The stack is not empty." << std::endl; // 输出 The stack is not empty. } ``` 时间复杂度为 O(1)[^5]。 --- #### 3. 自定义底层容器 默认情况下，`std::stack` 使用 `std::deque` 作为其底层容器。可以通过指定第二个模板参数来自定义底层容器类型： ```cpp #include <iostream> #include <stack> #include <vector> int main() { std::stack<int, std::vector<int>> custom_stack; // 使用 vector 作为底层容器 custom_stack.push(1); custom_stack.push(2); std::cout << "Custom stack top: " << custom_stack.top() << std::endl; // 输出 Custom stack top: 2 } ``` --- #### 4. 关于 C++11 特性的支持情况 Visual Studio 对 C++11 的支持程度较高，因此可以放心地在现代编译器环境下使用上述标准库的功能。对于较旧版本的编译器（如 VS2010），可能部分新特性尚未完全支持[^4]。 --- #### 5. 性能分析 由于 `std::stack` 实际上是对底层容器的操作封装，性能取决于所选的具体容器类型。通常推荐使用默认选项 `std::deque`，因为它提供了良好的平衡性和效率。 ---

C++ STL（标准模板库）中的 stack 是一种容器适配器，它提供了一种 LIFO（Last In First Out）数据结构。 stack 可以使用不同的底层容器实现，例如 vector、deque 和 list 等。默认情况下，stack 使用 deque 作为其底层容器。 以下是一些 stack 常用的操作： 1. push()：在 stack 的顶部插入一个元素。 2. pop()：从 stack 的顶部弹出元素。 3. top()：返回 stack 的顶部元素。 4. empty()：检查 stack 是否为空。 5. size()：返回 stack 中元素的数量。 以下是一个示例代码，展示如何使用 stack： ``` #include <iostream> #include <stack> using namespace std; int main() { stack<int> s; s.push(1); s.push(2); s.push(3); while (!s.empty()) { cout << s.top() << " "; s.pop(); } return 0; } ``` 输出结果为：3 2 1。