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

C++ STL模板库12-容器4-容器适配器-堆栈(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 ← BOTTOM
    print(s_list);   //TOP → 3.14 ← BOTTOM
    
    
    std::stack<std::string> s;
    s.push("天津");
    s.push("上海");
    // s.emplace(3, "深圳");  //错误！ 底层没有匹配的函数
    s.emplace(std::string(" 深圳"));  // 等效于 push 
    s.emplace(" 深圳");    // 直接构造字符串

    print(s);      // TOP → " 深圳" → " 深圳" → "上海" → "天津" ← BOTTOM
    
    return 0;
}