C++之stack容器

stack 是 C++ STL (Standard Template Library) 中的一种容器适配器，用于实现后进先出（LIFO, Last In First Out）的数据结构。stack 提供了一组基本的操作来管理栈顶元素的插入和移除。stack 的底层可以基于不同的容器（如 vector、deque 或 list）实现，默认情况下使用 deque。

主要特点

1. 后进先出：最后插入的元素最先被移除。
2. 基本操作：提供 push、pop、top、empty 和 size 等基本操作。
3. 容器适配器：stack 是一个容器适配器，可以基于不同的底层容器实现。

常用操作

定义和初始化

#include <stack>

std::stack<int> s; // 创建一个空的 stack 容器
std::stack<int, std::vector<int>> s_vec; // 使用 vector 作为底层容器的 stack
std::stack<int, std::deque<int>> s_deque; // 使用 deque 作为底层容器的 stack（默认）
std::stack<int, std::list<int>> s_list; // 使用 list 作为底层容器的 stack

插入元素

s.push(1); // 将 1 插入栈顶
s.push(2); // 将 2 插入栈顶

移除元素

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

访问栈顶元素

if (!s.empty()) {
    std::cout << "Top element: " << s.top() << std::endl;
} else {
    std::cout << "Stack is empty." << std::endl;
}

检查栈是否为空

if (s.empty()) {
    std::cout << "Stack is empty." << std::endl;
} else {
    std::cout << "Stack is not empty." << std::endl;
}

获取栈的大小

std::cout << "Stack size: " << s.size() << std::endl;

示例代码

以下是一个完整的示例，展示了如何使用 stack：

#include <iostream>
#include <stack>

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

    // 插入元素
    s.push(1);
    s.push(2);
    s.push(3);

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

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

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

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

    // 获取栈的大小
    std::cout << "Stack size: " << s.size() << std::endl;

    return 0;
}

总结

stack 是一个非常有用的数据结构，适用于需要后进先出操作的场景。常见的应用场景包括表达式求值、回溯算法、函数调用栈等。由于 stack 是一个容器适配器，你可以选择不同的底层容器来实现它，以适应不同的性能需求。默认情况下，stack 使用 deque 作为底层容器，因为它在大多数情况下提供了良好的性能。