43 C++ STL模板库12-容器4-容器适配器-堆栈(stack)

C++ STL模板库12-容器4-容器适配器-堆栈(stack)

stack是一个容器适配器，它基于其他容器实现.

一、模板参数与底层容器

头文件与命名空间

#include <stack>
using namespace std; // 或显式使用 std::stack 

模板声明

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

T：元素类型。
Container：底层容器类型（需满足以下操作）：
back()：访问末尾元素。
push_back()：在末尾添加元素。
pop_back()：移除末尾元素。
支持的容器：deque（默认）、vector、list。
示例：stack<int, vector<int>> s; 使用 vector 作为底层容器。

二、成员函数列表

1. push(const T& value)
   将元素压入栈顶，通过复制或移动构造（时间复杂度：O(1)）。
2. emplace(Args&&... args) (C++11)
   直接在栈顶构造元素，参数传递给元素的构造函数（更高效，避免临时对象）。
3. pop()
   移除栈顶元素（必须先检查栈非空，否则未定义行为；时间复杂度：O(1)）。
4. top()
   返回栈顶元素的引用（允许修改值，如 s.top() = 10;，需保证栈非空）。
5. empty()
   返回布尔值，判断栈是否为空（时间复杂度：O(1)）。
6. size()
   返回当前栈中元素的数量（时间复杂度：O(1)）。
7. swap(stack& other) (C++11)
   交换两个栈的内容（要求底层容器类型相同；时间复杂度：O(1)）。

三、非成员函数

1. swap(stack& a, stack& b) (C++11)
   交换两个栈的内容（等效于 a.swap(b)）。

2. 比较运算符 (==, !=, <, <=, >, >=)
   按字典序比较两个栈的内容（委托到底层容器的比较操作，要求容器类型相同）。

四、特性与注意事项

1. LIFO原则：后进先出，仅允许操作栈顶元素。
2. 无迭代器：不支持遍历，只能通过 top() 访问栈顶。
3. 性能依赖底层容器：
   • 默认使用 deque，平衡内存分配效率。
   • 使用 vector 时需注意扩容开销。
4. 错误处理：
   • pop() 或 top() 前必须用 empty() 检查栈非空。
   • 未定义行为风险：如空栈调用 pop()。

五、示例代码片段

示例1：基本操作（push/top/pop/empty/size）

#include <stack>
#include <vector>int main() {std::stack<int, std::vector<int>> s;s.push(1);          // 栈顶元素为 1 s.emplace(2);       // 栈顶元素为 2 s.top() = 3;        // 修改栈顶为 3 s.pop();            // 移除 3，栈顶变为 1 return 0;
}

示例2：高效构造（emplace代替push）

#include <stack>
#include <string>int main() {std::stack<std::string> s;s.push("abc");              // 通过临时对象构造 s.emplace(3, 'x');          // 直接构造字符串"xxx"（避免复制）return 0;
}

示例3：更换底层容器（vector/list）

#include <stack>
#include <vector>
#include <list>int main() {// 使用 vector 作为底层容器（需包含头文件 <vector>）std::stack<int, std::vector<int>> s_vec;s_vec.push(5);  // 实际调用 vector::push_back()// 使用 list 作为底层容器（需包含头文件 <list>）std::stack<double, std::list<double>> s_list;s_list.push(3.14);  // 实际调用 list::push_back()return 0;
}

示例4：交换两个栈（swap）

#include <stack>int main() {std::stack<int> s1, s2;s1.push(100); s2.push(200);s1.swap(s2);        // 成员函数交换 // swap(s1, s2);    // 非成员函数等效操作（C++11起）// 此时 s1.top() = 200，s2.top() = 100 return 0;
}

示例5：安全访问与错误处理

#include <stack>void processStack(std::stack<int>& s) {if (!s.empty()) {   // 必须检查非空！int val = s.top();s.pop();// 处理val...}
}int main() {std::stack<int> s;processStack(s);    // 安全处理空栈 return 0;
}

示例6：比较两个栈（运算符重载）

#include <stack>int main() {std::stack<int> a, b;a.push(1); a.push(2);  // a: [1,2]b.push(1); b.push(3);  // b: [1,3]bool isEqual = (a == b);   // false（元素不同）bool isLess = (a < b);     // true（2 < 3）return 0;
}

示例7：作为函数的参数类型传递

#include <iostream>
#include <stack>
#include <vector>
#include <list>
#include <string>template <typename T, typename Container>
void print(std::stack<T, Container> s) {std::cout << "TOP → ";while (!s.empty())  {if constexpr (std::is_same_v<T, std::string>) std::cout << "\"" << s.top()  << "\"";else std::cout << s.top(); s.pop(); if (!s.empty())  std::cout << " → ";}std::cout << " ← BOTTOM\n";
}int main() {// 使用 vector 作为底层容器（需包含头文件 <vector>）std::stack<int, std::vector<int>> s_vec;s_vec.push(5);  // 实际调用 vector::push_back()// 使用 list 作为底层容器（需包含头文件 <list>）std::stack<double, std::list<double>> s_list;s_list.push(3.14);  // 实际调用 list::push_back()print(s_vec);    //TOP → 5 ← BOTTOMprint(s_list);   //TOP → 3.14 ← BOTTOMstd::stack<std::string> s;s.push("天津");s.push("上海");// s.emplace(3, "深圳");  //错误！ 底层没有匹配的函数s.emplace(std::string(" 深圳"));  // 等效于 push s.emplace(" 深圳");    // 直接构造字符串print(s);      // TOP → " 深圳" → " 深圳" → "上海" → "天津" ← BOTTOMreturn 0;
}