苏州园区疫情_web前端开发怎么学_全网营销方案_推广app

std::stack、std::queue 和 std::priority_queue 是 C++ 标准库中的容器适配器，它们基于底层容器（如 std::deque 或 std::vector）提供特定的数据结构接口。以下是它们的详细说明和使用方法。

---

1. std::stack

std::stack 是一个后进先出（LIFO, Last In First Out）的容器适配器，通常基于 std::deque 实现。

特点

• 后进先出：最后插入的元素最先被访问。
• 底层容器：默认使用 std::deque，但可以指定其他容器（如 std::vector 或 std::list）。
• 操作受限：只允许在栈顶进行插入和删除操作。

常用操作

• push(): 将元素压入栈顶。
• pop(): 移除栈顶元素。
• top(): 访问栈顶元素。
• 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 << "Top element after pop: " << s.top() << std::endl; // 输出 20// 检查栈是否为空if (!s.empty()) {std::cout << "Stack size: " << s.size() << std::endl; // 输出 2}return 0;
}

使用场景

• 需要后进先出的场景，如函数调用栈、撤销操作等。
• 递归算法的非递归实现。

---

2. std::queue

std::queue 是一个先进先出（FIFO, First In First Out）的容器适配器，通常基于 std::deque 实现。

特点

• 先进先出：最先插入的元素最先被访问。
• 底层容器：默认使用 std::deque，但可以指定其他容器（如 std::list）。
• 操作受限：只允许在队尾插入元素，在队头删除元素。

常用操作

• push(): 将元素插入队尾。
• pop(): 移除队头元素。
• front(): 访问队头元素。
• back(): 访问队尾元素。
• empty(): 检查队列是否为空。
• size(): 返回队列中元素的数量。

示例代码

#include <iostream>
#include <queue>int main() {std::queue<int> q;// 插入元素q.push(10);q.push(20);q.push(30);// 访问队头元素std::cout << "Front element: " << q.front() << std::endl; // 输出 10// 访问队尾元素std::cout << "Back element: " << q.back() << std::endl; // 输出 30// 移除队头元素q.pop();std::cout << "Front element after pop: " << q.front() << std::endl; // 输出 20// 检查队列是否为空if (!q.empty()) {std::cout << "Queue size: " << q.size() << std::endl; // 输出 2}return 0;
}

使用场景

• 需要先进先出的场景，如任务调度、消息队列等。
• 广度优先搜索（BFS）算法。

---

3. std::priority_queue

std::priority_queue 是一个优先级队列，通常基于 std::vector 实现，并使用堆（heap）数据结构维护元素的优先级。

特点

• 优先级排序：元素按优先级排序，默认是最大堆（最大元素在队头）。
• 底层容器：默认使用 std::vector，但可以指定其他容器（如 std::deque）。
• 操作受限：只允许访问队头元素（优先级最高的元素），插入和删除操作会自动维护堆结构。

常用操作

• push(): 插入元素。
• pop(): 移除队头元素（优先级最高的元素）。
• top(): 访问队头元素。
• empty(): 检查队列是否为空。
• size(): 返回队列中元素的数量。

示例代码

#include <iostream>
#include <queue>int main() {// 默认是最大堆std::priority_queue<int> pq;// 插入元素pq.push(30);pq.push(10);pq.push(20);// 访问队头元素（最大元素）std::cout << "Top element: " << pq.top() << std::endl; // 输出 30// 移除队头元素pq.pop();std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 20// 自定义比较函数，实现最小堆std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;min_pq.push(30);min_pq.push(10);min_pq.push(20);std::cout << "Top element in min heap: " << min_pq.top() << std::endl; // 输出 10return 0;
}

使用场景

• 需要按优先级处理元素的场景，如任务调度、Dijkstra 算法等。
• 需要快速获取最大或最小元素的场景。

---

对比总结

特性	std::stack	std::queue	std::priority_queue
数据结构	后进先出（LIFO）	先进先出（FIFO）	优先级队列（堆）
默认底层容器	std::deque	std::deque	std::vector
插入操作	push()（栈顶）	push()（队尾）	push()（自动排序）
删除操作	pop()（栈顶）	pop()（队头）	pop()（队头）
访问操作	top()（栈顶）	front()（队头）	top()（队头）
使用场景	递归、撤销操作	任务调度、BFS	任务调度、Dijkstra 算法

---

注意事项

1. 底层容器选择：
   • std::stack 和 std::queue 默认使用 std::deque，但可以指定其他容器。
   • std::priority_queue 默认使用 std::vector，但可以指定其他容器。
2. 性能：
   • std::stack 和 std::queue 的插入和删除操作是 O(1)。
   • std::priority_queue 的插入和删除操作是 O(log n)。
3. 自定义比较函数：
   • std::priority_queue 可以通过自定义比较函数实现最小堆或其他优先级规则。