一、stack 的介绍和使用
1、stack 的介绍
https://cplusplus.com/reference/stack/stack/?kw=stack
1. stack 是一种容器适配器（container adapter ），专门用在具有 LIFO（ 后进先出 ）操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2. stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，元素从特定容器的尾部（即栈顶）被压入和弹出，这被称为堆栈的顶 。
3. stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
- empty：判空操作。
- back：获取尾部元素操作。
- push_back：尾部插入元素操作。
- pop_back：尾部删除元素操作。
4. 标准容器 vector、deque、list 均符合这些需求 ，默认情况下，如果没有为 stack 指定特定的底层容器，默认情况下使用 deque 。
2、stack 的使用
stack 是没有迭代器的，因为如果有了迭代器就可以随意访问元素了，就无法保证后进先出的性质了。
3、stack 的模拟实现
从栈的接口中可以看出，栈实际是一种特殊的 vector，因此使用 vector 完全可以模拟实现 stack 。
#pragma once //#include <vector> #include <deque> namespace xyl { // T: 堆栈中存储的数据的类型 // Container: 适配堆栈的容器类型，默认为deque template<class T, class Container = deque<T>> class stack { // stack 是一个Container适配(封装转换)出来的 把Contariner的尾部认为是栈顶 public: stack() {} bool empty() const // 判空 { return _con.empty(); } size_t size() const // 获取有效元素的个数 { return _con.size(); } T& top() { return _con.back(); } const T& top() const // 返回栈顶元素的引用 { return _con.back(); } void push(const T& x) // 压栈，尾插 { _con.push_back(x); } void pop() // 出栈，尾删 { _con.pop_back(); } // C++11 void swap(stack<T, Container>& st) // 交换两个容器的内容 { // 注意：底层调用的是非成员函数 std::swap 来交换底层容器 std::swap(_con, st._con); } private: //vector<T> _con; Container _con; // 适配的容器 }; void test() { //stack<int, std::vector<int>> st; // 用vector适配 //stack<int, std::list<int>> st; // 用list适配 stack<int> st; // 默认用deque适配 st.push(1); st.push(2); st.push(3); // 遍历堆栈中的元素 while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; } }
不需要写构造函数，因为在默认构造函数的初始化列表阶段，自定义类型成员 _con 会自动调用它的默认构造函数。
如果 _con 没有 push_back 接口怎么办呢？
没有就报错，说明不能适配。
二、queue 的介绍和使用
1、queue 的介绍
http://www.cplusplus.com/reference/queue/queue/
1. 队列是一种容器适配器（container adapter ），专门用于在 FIFO（ 先进先出 ）操作的上下文环境中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
- empty：检测队列是否为空。
- size：返回队列中有效元素的个数。
- front：返回队头元素的引用。
- back：返回队尾元素的引用。
- push_back：在队列尾部入队列。
- pop_front：在队列头部出队列。
4. 标准容器类 deque 和 list 满足了这些要求。 默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque。
2、queue 的使用
queue 是没有迭代器的，有了迭代器就可以随意访问元素了，就无法保证先进先出的性质了。
3、queue 的模拟实现
因为 queue 的接口中存在头删和尾插，因此使用 vector 来封装效率太低，故也可以借助 list 来模拟实现 queue。
#pragma once //#include <list> #include <deque> namespace xyl { // T: 队列中存储的数据的类型 // Container: 适配队列的容器类型，默认为deque template<class T, class Container = deque<T>> class queue { public: queue() {} bool empty() // 判空 { return _con.empty(); } size_t size() const // 获取有效元素的个数 { return _con.size(); } T& front() { return _con.front(); } T& back() { return _con.back(); } const T& front() const // 返回队头元素的引用 { return _con.front(); } const T& back() const // 返回队尾元素的引用 { return _con.back(); } void push(const T& val) // 入队，尾插 { _con.push_back(val); } void pop() // 出队，头删 { _con.pop_front(); } private: Container _con; // 适配的容器 }; void test() { //queue<int, std::list<int>> q; // 用list适配 queue<int> q; // 默认用deque适配 q.push(1); q.push(2); q.push(3); // 遍历队列中的元素 while (!q.empty()) { cout << q.front() << " "; q.pop(); } cout << endl; } }
不需要写构造函数，因为在默认构造函数的初始化列表阶段，自定义类型成员 _con 会自动调用它的默认构造函数。
三、priority_queue 的介绍和使用
1、priority_queue 的介绍
http://www.cplusplus.com/reference/queue/priority_queue/
1. 优先队列是一种容器适配器（container adapter），根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的（默认为大堆）。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素（优先队列中位于顶部的元素）。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类， queue 提供一组特定的成员函数来访问其元素。元素从特定容器的 “尾部” 弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
- empty()：检测容器是否为空。
- size()：返回容器中有效元素个数。
- front()：返回容器中第一个元素的引用。
- push_back()：在容器尾部插入元素。
- pop_back()：删除容器尾部元素。
5. 标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用 vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作。
7. 需要包含头文件。
2、priority_queue 的使用
priority_queue 的所有元素，进出有一定的规则，只有顶端的元素（权值最高者），才有机会被外界取用。priority_queue 不提供走访功能，所以也不提供迭代器。
优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority_queue 就是堆 ，所有需要用到堆的位置，都可以考虑使用 priority_queue。
注意 ：默认情况下 priority_queue 是 大堆 。
#include <vector> #include <queue> #include <functional> // greater算法的头文件 void TestPriorityQueue() { // 默认情况下，创建的是大堆，其底层按照小于符号(<)比较 vector<int> v{3, 2, 7, 6, 0, 4, 1, 9, 8, 5}; priority_queue<int> q1; for (auto& e : v) { q1.push(e); } cout << q1.top() << endl; // 如果要创建小堆，将第三个模板参数换成greater比较方式即可 priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end()); cout << q2.top() << endl; }
如果在 priority_queue 中放自定义类型的数据，用户需要在自定义类型中提供 > 或者< 的重载，或者通过用户提供的针对比较自定义类型对象大小的仿函数类，控制比较方式。
class Date { public: Date(int year = 2023, int month = 1, int day = 1) : _year(year) , _month(month) , _day(day) {} bool operator<(const Date& d) const // < 运算符重载 { return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day); } bool operator>(const Date& d) const // > 运算符重载 { return (_year > d._year) || (_year == d._year && _month > d._month) || (_year == d._year && _month == d._month && _day > d._day); } friend ostream& operator<<(ostream& _cout, const Date& d) // << 运算符重载 { _cout << d._year << "-" << d._month << "-" << d._day; return _cout; } friend struct DateLess; // 仿函数类声明为友元 private: int _year; int _month; int _day; }; void test_priority_queue1() { // 大堆，需要用户在自定义类型中提供<的重载 priority_queue<Date> q1; q1.push(Date(2023, 9, 29)); q1.push(Date(2023, 9, 28)); q1.push(Date(2023, 9, 30)); cout << q1.top() << endl; // 输出堆顶元素（最大日期） // 小堆，需要用户在自定义类型中提供>的重载 priority_queue<Date, vector<Date>, greater<Date>> q2; q2.push(Date(2023, 9, 29)); q2.push(Date(2023, 9, 28)); q2.push(Date(2023, 9, 30)); cout << q2.top() << endl; // 输出堆顶元素（最小日期） } // 定义按小于(<)比较自定义类型对象大小的仿函数类 struct DateLess { bool operator()(const Date& d1, const Date& d2) { return (d1._year < d2._year) || (d1._year == d2._year && d1._month < d2._month) || (d1._year == d2._year && d1._month == d2._month && d1._day < d2._day); } }; void test_priority_queue2() { // 大堆，第3个模板参数传针对比较自定义类型对象大小的仿函数类DateLess priority_queue<Date, vector<Date>, DateLess> q1; q1.push(Date(2023, 9, 29)); q1.push(Date(2023, 9, 28)); q1.push(Date(2023, 9, 30)); cout << q1.top() << endl; // 输出堆顶元素（最大日期） }
3、priority_queue 的模拟实现
通过对 priority_queue 的底层结构就是堆，因此此处只需对对进行通用的封装即可。
#pragma once #include <iostream> using namespace std; #include <vector> #include<functional> // priority_queue--->堆 namespace xyl { // Compare进行比较的仿函数 less->大堆 template<class T> struct less { bool operator()(const T& left, const T& right) { return left < right; } }; // Compare进行比较的仿函数 greater->小堆 template<class T> struct greater { bool operator()(const T& left, const T& right) { return left > right; } }; // T: 优先级队列中存储的数据的类型 // Container: 适配优先级队列的容器类型，默认为vector // Compare: 仿函数类型，默认是Less(<)，建大堆(也可以用库中的greater和less类模板) template<class T, class Container = vector<T>, class Compare = std::less<T>> class priority_queue { public: // 创造空的优先级队列 priority_queue() {} // 用迭代器区间[first,last)构造初始化 template <class InputIterator> priority_queue(InputIterator first, InputIterator last) { while (first != last) { _con.push_back(*first); // 插入数据 ++first; } // 建堆，从倒数第一个非叶子节点开始向下调整 int child = _con.size() - 1; int parent = (child - 1) / 2; for (int i = parent; i >= 0; i--) { adjust_down(i); } } // O(logN) // 向上调整，建大堆(小堆) void adjust_up(size_t child) { Compare com; // 仿函数对象 size_t parent = (child - 1) / 2; // 计算出父亲下标 while (child > 0) { //if (_con[child] > _con[parent]) //if (_con[parent] < _con[child]) // 如果父亲小于(大于)孩子，需要把孩子往上调 if (com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); // 交换孩子与父亲 child = parent; parent = (child - 1) / 2; } else // 如果父亲大于(小于)孩子，说明已经是大(小)堆，不需要调整了 { break; } } } // 向堆中插入一个元素 void push(const T& x) { _con.push_back(x); // 尾插 adjust_up(_con.size() - 1); // 从最后一个元素开始，向上调整 } // O(logN) // 向下调整，建大堆(小堆) // 前提条件：左右子树都是大(小)堆 void adjust_down(size_t parent) { Compare com; // 仿函数对象 size_t child = parent * 2 + 1; // 计算出左孩子下标，默认左孩子最大 while (child < _con.size()) // 孩子下标超过数组范围时结束 { // 1、选出左右孩子最小的那个，先判断右孩子是否存在 // 左孩子小于(大于)右孩子 if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { child++; // 右孩子最大 } // 2、最大的孩子与父亲比较 // 父亲小于(大于)最大的孩子，需要把父亲往下调 if (com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); // 交换父亲与孩子 parent = child; child = parent * 2 + 1; } else // 父亲大于(小于)最大的孩子，说明已经是大(小)堆，不需要调整了 { break; } } } // 删除堆顶元素 void pop() { std::swap(_con[0], _con[_con.size() - 1]); // 堆顶元素交换到尾部 _con.pop_back(); // 尾删 adjust_down(0); // 从堆顶开始，向下调整 } // 返回堆顶元素，堆顶元素不允许修改，因为堆顶元素修改会破坏堆的特性 const T& top() { return _con[0]; } // 判空 bool empty() const { return _con.empty(); } // 返回有效元素个数 size_t size() const { return _con.size(); } private: Container _con; // 成员变量，基础容器 }; } void test_queue_priority() { xyl::priority_queue<int> q1; q1.push(5); q1.push(1); q1.push(4); q1.push(2); q1.push(3); q1.push(6); cout << q1.top() << endl; q1.pop(); q1.pop(); cout << q1.top() << endl; vector<int> v{5, 1, 4, 2, 3, 6}; xyl::priority_queue<int, vector<int>, xyl::greater<int>> q2(v.begin(), v.end()); cout << q2.top() << endl; q2.pop(); q2.pop(); cout << q2.top() << endl; }
⚪【补充】
之前我们要让大堆 -> 小堆，都是直接去修改符号，那能不能在不修改符号的情况下就能达到该效果呢？
在 C 语言中其实可以利用函数指针来解决。但是 C++ 放弃用函数指针的方式，且非常不建议用函数指针，因为这样做比较复杂。可以说 C++ 里的仿函数 / 函数对象就是为了替代 C 语言里的函数指针。
" () " 的功能可以提高优先级、强制类型转换、函数名 (形参表)，仿函数用的是函数名 (形参表)。我们可以实现两个类，分别重载 " () " 完成比较大小功能，然后用 priority_queue 这个类来实例化控制。
【C++ STL】容器适配器（Stack & Queue & Priotity_Queue）-- 详解（下）https://developer.aliyun.com/article/1514696?spm=a2c6h.13148508.setting.22.4b904f0ejdbHoA
