当前位置：首页 > article >正文

c++ std::stack总结

article 2024/11/23 16:28:05

概念

std::stack 是 C++ 标准库中的一个容器适配器（Container Adapter）。它通常是基于其他容器（如 std::deque 或 std::vector）实现的，提供了一个后进先出（LIFO，Last In First Out）的元素访问顺序。栈只能在栈顶（top）进行插入和删除操作，因此它只暴露了有限的接口，操作简单高效。

特点

后进先出（LIFO）：栈总是从栈顶访问元素，栈顶的元素总是最新的。
动态大小：栈的大小可以动态增长和缩小，当有元素压入或弹出时栈的大小会相应改变。
封装性强：std::stack 不允许直接访问底层容器的数据（除了栈顶元素），保证了栈操作的封装性。

成员函数

push(): 向栈顶插入元素。

stack.push(value);  // 将元素 value 压入栈顶

pop(): 弹出栈顶元素。

stack.pop();  // 移除栈顶元素

top(): 获取栈顶元素，但不移除它。

stack.top();  // 返回栈顶元素

empty(): 检查栈是否为空。

stack.empty();  // 如果栈为空返回 true，否则返回 false

size(): 返回栈中的元素数量。

stack.size();  // 返回栈的元素数量

底层容器

std::stack 是一个容器适配器，意味着它依赖于底层容器来存储数据。默认情况下，std::stack 使用 std::deque 作为底层容器，也可以显式选择使用 std::vector 或 std::list。

std::stack 是一个模板类，它可以接受两个模板参数：

元素类型（T）：栈中存储的元素类型。
底层容器类型（Container）：用于存储元素的底层容器类型，默认是 std::deque<T>。

第二个参数允许我们指定底层容器，如 std::vector 或 std::list。底层容器必须支持以下操作：

push_back()
pop_back()
back()
empty()
size()

示例一：常规用法

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    // 向栈中压入元素
    s.push(10);
    s.push(20);
    s.push(30);

    // 输出栈顶元素
    std::cout << "Top element: " << s.top() << std::endl;  // 输出 30

    // 弹出栈顶元素
    s.pop();
    
    // 输出新的栈顶元素
    std::cout << "New top element: " << s.top() << std::endl;  // 输出 20

    // 检查栈是否为空
    if (s.empty()) {
        std::cout << "The stack is empty" << std::endl;
    } else {
        std::cout << "The stack is not empty" << std::endl;  // 输出栈不为空
    }

    // 输出栈的大小
    std::cout << "Stack size: " << s.size() << std::endl;  // 输出 2

    return 0;
}

示例二：使用 std::vector作为底层容器

#include <iostream>
#include <stack>
#include <vector>

int main() {
    // 使用 std::vector 作为底层容器
    std::stack<int, std::vector<int>> s;

    s.push(10);
    s.push(20);
    s.push(30);

    // 输出栈顶元素
    std::cout << "Top element: " << s.top() << std::endl;  // 输出 30

    s.pop();

    std::cout << "New top element: " << s.top() << std::endl;  // 输出 20
    std::cout << "Stack size: " << s.size() << std::endl;      // 输出 2

    return 0;
}

示例三：使用 std::list作为底层容器

#include <iostream>
#include <stack>
#include <list>

int main() {
    // 使用 std::list 作为底层容器
    std::stack<int, std::list<int>> s;

    s.push(100);
    s.push(200);
    s.push(300);

    // 输出栈顶元素
    std::cout << "Top element: " << s.top() << std::endl;  // 输出 300

    s.pop();

    std::cout << "New top element: " << s.top() << std::endl;  // 输出 200
    std::cout << "Stack size: " << s.size() << std::endl;      // 输出 2

    return 0;
}

示例四：自定义容器

#include <iostream>
#include <stack>
#include <deque>

// 自定义容器（必须支持 push_back, pop_back, back, size, empty）
template<typename T>
class CustomContainer {
private:
    std::deque<T> data;  // 使用 deque 存储数据
public:
    void push_back(const T& value) { data.push_back(value); }
    void pop_back() { data.pop_back(); }
    T& back() { return data.back(); }
    const T& back() const { return data.back(); }
    bool empty() const { return data.empty(); }
    size_t size() const { return data.size(); }
};

int main() {
    // 使用自定义容器作为底层容器
    std::stack<int, CustomContainer<int>> s;

    s.push(42);
    s.push(84);
    s.push(126);

    std::cout << "Top element: " << s.top() << std::endl;  // 输出 126

    s.pop();

    std::cout << "New top element: " << s.top() << std::endl;  // 输出 84
    std::cout << "Stack size: " << s.size() << std::endl;      // 输出 2

    return 0;
}

适用场景

表达式求值（后缀表达式，逆波兰表示法）：栈常用于计算后缀表达式或中缀表达式的转换。
括号匹配：栈常用于检查表达式中的括号是否匹配。
深度优先搜索（DFS）：在图的遍历中，栈用于模拟递归的调用栈。
回溯算法：栈可以用于回溯算法的状态追踪。
撤销操作：栈可用于实现撤销操作的功能，在需要回退到上一步的场景中非常有用。

性能

时间复杂度：push()、pop()、top()、empty()、size() 操作都是常数时间 O(1)。
空间复杂度：std::stack 使用底层容器存储数据，因此其空间复杂度取决于底层容器的实现（std::deque 或 std::vector）。