•  支持操作：push（入栈）、pop（出栈）、top（访问栈顶元素）、empty（判断是否为空）、size（返回元素个数）。
• 底层容器：默认使用deque，也可指定为vector或list。可在第二个参数给出。

2. queue（队列）

• 特点：先进先出（FIFO）的数据结构。
• 支持操作：push（入队）、pop（出队）、front（访问队首元素）、back（访问队尾元素）、empty、size。
• 底层容器：默认使用deque，也可指定为list。

3. priority_queue（优先队列）

• 特点：元素按优先级排序，优先级高的元素先出队。
• 支持操作：push（插入元素）、pop（删除优先级最高的元素）、top（访问优先级最高的元素）、empty、size。
• 底层容器：默认使用vector，结合heap算法实现。
• 默认排序：最大堆（大顶堆），即元素按降序排列。

底层容器选择

容器适配器可通过模板参数指定底层容器：

代码语言：javascript

AI代码解释

// 使用vector作为stack的底层容器
stack<int, vector<int>> stackWithVector;

// 使用list作为queue的底层容器
queue<int, list<int>> queueWithList;

总结

容器适配器	数据结构特点	默认底层容器	适用场景
stack	LIFO	deque	递归模拟、表达式求值
queue	FIFO	deque	任务调度、广度优先搜索
priority_queue	优先级排序	vector+heap	任务调度（按优先级）、贪心算法

选择合适的容器适配器可以提高代码的可读性和性能。

一、C++ Stack 介绍

（一）定义

在 C++ 中，stack 是一种容器适配器，它提供了一种后进先出（Last In First Out，LIFO）的数据结构。它基于底层容器（默认是 std::deque，也可以是 std::vector 或 std::list 等）来存储元素，但只允许在容器的一端（称为栈顶）进行操作。

（二）主要操作

1. 构造和析构
   • 默认构造函数会创建一个空的栈。
   • 析构函数会销毁栈中的所有元素。
2. 元素访问
   • top()：返回栈顶元素的引用。如果栈为空，调用 top() 是未定义行为。
3. 容量
   • empty()：检查栈是否为空，如果为空返回 true，否则返回 false。
   • size()：返回栈中元素的数量。
4. 修改器
   • push(const T& value)：将一个新元素压入栈顶。
   • pop()：移除栈顶元素。注意，pop() 不返回被移除的元素，如果栈为空，调用 pop() 是未定义行为。
   • emplace(Args&&... args)：在栈顶构造一个新元素，避免了额外的拷贝或移动操作。

（三）底层容器

stack 的底层容器默认是 std::deque，但可以通过模板参数指定其他容器，如 std::vector 或 std::list。底层容器的选择会影响 stack 的性能和内存使用方式。

二、C++ Stack 的使用

（一）包含头文件

在使用 stack 之前，需要包含头文件 <stack>：

代码语言：javascript

AI代码解释

#include <stack>

（二）基本操作示例

代码语言：javascript

AI代码解释

#include <iostream>
#include <stack>

int main() {
    // 创建一个空的栈
    std::stack<int> mystack;

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

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

    // 检查栈是否为空
    std::cout << "栈是否为空: " << (mystack.empty() ? "是" : "否") << std::endl;

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

    // 弹出栈顶元素
    mystack.pop();

    // 再次访问栈顶元素
    std::cout << "弹出一个元素后，栈顶元素是: " << mystack.top() << std::endl;

    return 0;
}

（三）使用自定义类型

stack 可以存储任何类型的元素，包括自定义类型。自定义类型需要满足底层容器的要求，例如提供默认构造函数、拷贝构造函数等。

代码语言：javascript

AI代码解释

#include <iostream>
#include <stack>

struct Person {
    std::string name;
    int age;

    Person(const std::string& n, int a) : name(n), age(a) {}
};

int main() {
    std::stack<Person> personStack;

    personStack.push(Person("Alice", 25));
    personStack.push(Person("Bob", 30));

    std::cout << "栈顶元素是: " << personStack.top().name << ", 年龄: " << personStack.top().age << std::endl;

    return 0;
}

（四）底层容器的选择

可以通过模板参数指定底层容器。例如，使用 std::vector 作为底层容器：

代码语言：javascript

AI代码解释

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

int main() {
    std::stack<int, std::vector<int>> mystack;

    mystack.push(10);
    mystack.push(20);

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

    return 0;
}

不同的底层容器会影响 stack 的性能和内存使用。例如：

• std::deque（默认）：支持快速的插入和删除操作，内存分配相对灵活。
• std::vector：内存连续，访问速度快，但插入和删除操作可能涉及内存重新分配。
• std::list：支持双向迭代，插入和删除操作非常高效，但访问速度相对较慢。