C++为什么要学习stack、queue和优先级队列
学习C++中的栈（stack）、队列（queue）和优先级队列（priority queue）对开发者来说非常重要，因为它们是常用的数据结构，在解决各种编程问题时提供了高效的方法。
以下是它们的核心作用和特点：
1. 栈（Stack）：
特点：后进先出（LIFO），即最后入栈的元素最先出栈。
应用：适用于函数调用、表达式求值、撤销操作等场景。例如，程序在执行递归调用时会用栈来存储函数状态。
2. 队列（Queue）：
特点：先进先出（FIFO），即最先进入队列的元素最先被处理。
应用：适用于任务调度、消息处理、广度优先搜索等需要按顺序处理数据的场景。
3. 优先级队列（Priority Queue）：
特点：元素按优先级排序，每次取出的是优先级最高的元素，而不是按插入顺序。
应用：适用于任务管理（例如操作系统中的任务调度）、最短路径算法（如Dijkstra算法）、数据流中找出Top K元素等场景。
这些数据结构在C++中有标准库支持（如`<stack>`、`<queue>`和`<priority_queue>`），可以帮助开发者更高效地处理特定类型的问题，提高程序的可读性和性能。
stack类
stack类的介绍
stack是 C++ 标准模板库（STL）中的一个容器适配器，用于实现后进先出（LIFO）数据结构。它基于其他序列容器（如
deque、vector或list）构建，默认使用deque作为底层容器stack<int, vector<int>> st;注：
1、定义了一个名为 st 的栈（stack）
其中包含 int 类型的元素，并使用 vector<int> 作为其底层容器
2、
stack默认使用deque作为底层容器，但可以通过这种方式替换成其他容器3、特点 & 好处
- 该栈
st仍然保持stack的 后进先出 特性。- 使用
vector作为底层容器意味着栈的元素实际上存储在一个vector中，但只能通过stack提供的接口（如push()、pop()、top()等）访问。这样做的优势在于，如果对底层容器的特性（如内存管理或其他特定操作）有特殊需求，可以灵活选择适合的容器
stack的基本操作
push()：将元素压入栈顶。pop()：移除栈顶元素。top()：返回栈顶元素的引用。只能访问栈顶元素（通过top()），无法直接访问其他位置的元素empty()：判断栈是否为空。size()：返回栈中元素的个数
stack的模拟实现
namespace sky { template<class T, class Container = vector<int>> class Stack { public: void push(const T& val) { _con.push_back(val); // 压栈插入数据 } void pop() { _con.pop_back(); // 删除用尾删 } const T& top() { return _con.back(); // 后进先出 } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: Container _con; }; } int main() { sky::Stack<int,vector<int>> st; st.push(1); st.push(2); st.push(3); st.push(4); st.push(5); cout << st.size() << endl; while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; return 0; }
queue类
queue类的介绍
1、queue是标准库容器适配器，用于实现先进先出（FIFO）队列。它基于底层容器（如
deque或list）进行封装2、默认使用
deque作为存储容器，也可以指定其他符合双端操作要求的容器。
queue适用于需要按顺序处理数据的场景，如任务调度或广度优先搜索等
queue的基本操作
push()：向队尾添加元素。pop()：移除队头元素。front()：返回队头元素的引用。back()：返回队尾元素的引用。empty()：检查队列是否为空。size()：返回队列中元素的数量
queue的模拟实现
namespace sky { template<class T, class Container = list<int>> class Queue { public: void push(const T& val) { _con.push_back(val); } void pop() { _con.pop_front(); } T& front() { return _con.front(); } T& back() { return _con.back(); } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: Container _con; }; } int main() { sky::Queue<int> q; q.push(1); q.push(2); q.push(3); q.push(4); cout << q.back() << endl; cout << q.size() << endl; while (!q.empty()) { cout << q.front() << " "; q.pop(); } return 0; }
优先级队列
优先级队列的介绍
priority_queue是标准库容器适配器，用于实现优先级队列，其元素根据优先级自动排序。默认情况下，它使用最大堆结构，使得队头元素总是优先级最高的元素
priority_queue适用于需要动态维护最大（或最小）元素的场景，如任务调度、路径规划等注：需要包头文件<queue>
仿函数
什么是仿函数
priority_queue的函数原型比queue和stack多了一个参数，用于指定比较函数，这个参数决定了元素在priority_queue中的排序方式。比较函数（仿函数）：priority_queue需要一个比较函数（通常是仿函数）来定义元素之间的优先级顺序。默认情况下，它使用std::less<T>，这意味着它将按照从小到大的顺序排列，形成一个最大堆
这是priority_queue与queue和stack最显著的区别，因为priority_queue需要根据元素的优先级来组织数据，而queue和stack仅需要遵循基本的先进先出或后进先出原则
为什么要有仿函数
- 自定义比较逻辑：优先级队列默认情况下是一个最大堆，即最大的元素具有最高的优先级。但有时我们可能需要根据不同的标准来排序元素，比如最小堆或者基于对象的某个成员函数。通过使用仿函数，我们可以自定义比较逻辑，使得优先级队列能够按照我们期望的顺序排列元素。
- 状态保持：仿函数可以保持状态，这意味着它们可以在调用之间保留信息，这在某些复杂的比较逻辑中非常有用。
- 类型安全：使用仿函数可以保证类型安全，因为编译器会在编译时检查传递给仿函数的参数类型是否正确。
优先级队列的使用
成员函数
push()：插入元素，并自动调整位置。pop()：移除优先级最高的元素（队头）。top()：访问优先级最高的元素。empty()：检查队列是否为空。size()：返回元素的数量
排序准则
默认使用 std::less（大顶堆），可以通过自定义比较函数来实现小顶堆或其他排序
优先级队列的模拟实现
namespace sky { template<class T> class less { public: bool operator()(const T& x, const T& y) { // 在构建堆时，x < y 的意思是：如果 x 比 y 小， // 那么 x 的优先级低于 y，所以 y 应该排在 x 前面 return x < y; } }; template<class T> class greater { public: // 当使用 greater 作为比较器时，较小的元素会排在前面，因此可以创建一个"最小优先队列" bool operator()(const T& x, const T& y) { return x > y; } }; template<class T, class Container = vector<int>, class Compare = less<T>> class priority_queue { public: void adjust_up(int child) { Compare com; int parent = (child - 1) / 2; while (child > 0) { // 如果父节点的值比子节点的值小，则交换（基于比较器的定义） if (com(_con[parent], _con[child])) { swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(int parent) { Compare com; int child = parent * 2 + 1; while (child < _con.size()) { // 如果有右子节点且右子节点比左子节点大，则选择右子节点 if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { child++; } // 如果父节点比选定的子节点小，则交换 if (com(_con[parent], _con[child])) { swap(_con[parent], _con[child]); parent = child; child = parent * 2 + 1; } else { break; } } } // 插入元素并调整堆 void push(const T& val) { _con.push_back(val); adjust_up(_con.size() - 1); } // 删除堆顶元素并调整堆 void pop() { if (!_con.empty()) { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } } const T& top() const { return _con[0]; } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; }; } int main() { sky::priority_queue<int> pq; pq.push(3); pq.push(1); pq.push(5); pq.push(4); pq.push(2); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; return 0; }
关于容器适配器
