考研复试，stack

在 C++ 中，std::stack 是标准模板库（STL）提供的一个容器适配器，它实现了后进先出（Last-In-First-Out，LIFO）的数据结构，就像一摞盘子，最后放上去的盘子会最先被拿走。下面从定义、基本操作、实现原理、使用示例、应用场景等方面进行详细介绍。

定义与头文件包含

std::stack 定义在 <stack> 头文件中，其定义形式如下：

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

• T：表示栈中存储元素的类型。
• Container：是一个可选参数，指定用于存储栈元素的底层容器，默认使用 std::deque<T>。也可以使用其他支持 back()、push_back()、pop_back() 操作的容器，如 std::vector 或 std::list。

基本操作

• push()：将一个元素压入栈顶。
• pop()：移除栈顶元素，但不返回该元素。
• top()：返回栈顶元素的引用，但不移除该元素。
• empty()：检查栈是否为空，如果栈为空则返回 true，否则返回 false。
• size()：返回栈中元素的数量。

实现原理

std::stack 是一个容器适配器，它本身并不直接存储元素，而是通过封装另一个容器（如 std::deque、std::vector 或 std::list）来实现栈的功能。std::stack 对底层容器的操作进行了限制，只允许在容器的一端（即栈顶）进行插入和删除操作，从而保证了后进先出的特性。

使用示例

#include <iostream>
#include <stack>

int main() {
    // 创建一个存储整数的栈
    std::stack<int> myStack;

    // 压入元素
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

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

    // 访问栈顶元素
    std::cout << "栈顶元素: " << myStack.top() << std::endl;

    // 弹出栈顶元素
    myStack.pop();
    std::cout << "弹出栈顶元素后，新的栈顶元素: " << myStack.top() << std::endl;

    // 检查栈是否为空
    if (myStack.empty()) {
        std::cout << "栈为空" << std::endl;
    } else {
        std::cout << "栈不为空" << std::endl;
    }

    return 0;
}

代码解释

1. 创建栈：std::stack<int> myStack; 创建了一个存储整数的栈。
2. 压入元素：使用 push() 方法将元素 10、20、30 依次压入栈顶。
3. 获取栈的大小：使用 size() 方法获取栈中元素的数量。
4. 访问栈顶元素：使用 top() 方法获取栈顶元素。
5. 弹出栈顶元素：使用 pop() 方法移除栈顶元素。
6. 检查栈是否为空：使用 empty() 方法检查栈是否为空。

自定义底层容器

可以通过指定第二个模板参数来使用不同的底层容器，例如使用 std::vector：

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

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

    myStack.push(1);
    myStack.push(2);
    myStack.push(3);

    std::cout << "栈顶元素: " << myStack.top() << std::endl;

    return 0;
}

应用场景

• 表达式求值：在计算表达式（如后缀表达式）时，可以使用栈来存储操作数和运算符，方便进行计算。
• 函数调用栈：在程序执行过程中，函数调用的上下文信息（如局部变量、返回地址等）会被压入栈中，当函数返回时，这些信息会从栈中弹出。
• 回溯算法：在回溯算法中，栈可以用来记录搜索路径，方便在需要时进行回溯操作。