目录
引言
容器适配器
一、什么是容器适配器
二、底层容器的选择
标准库中的stack
一、stack的基本概念
二、stack的常用接口
三、stack的模拟实现
标准库中的queue
一、queue的基本概念
二、queue的常用接口
三、queue的模拟实现
标准库中的priority_queue
一、priority_queue的基本概念
二、priority_queue的常用接口
三、priority_queue的使用
结束语
引言
在之前的博客中，我们学习了栈（Stack）与队列（Queue）并尝试使用C语言实现其功能，同时我们在C++的学习中对STL中的string vector等容器也进行了学习，接下来我们来学习C++中的栈和队列。
可以先看看这两篇文章，更有助于我们学习：
数据结构——顺序栈和链式栈
数据结构——链式队列和循环队列
容器适配器
在学习stack和queue之前，我们先来了解一下容器适配器。
一、什么是容器适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
我们可以点开下面两个文档来查看一下：
stack文档
queue文档
priority_queue文档
我们可以看到：在stack容器适配器和queue容器适配器默认使用deque作为其底层容器。priority_queue默认使用vector作为底层容器。
二、底层容器的选择
那么为什么stack和deque会默认使用deque作为底层容器呢，priority_queue会使用vector作为底层容器呢？
我们之前学习过deque，我们也清楚deque的作用：deque支持在头尾两端进行高效的插入和删除操作，这与stack和queue的需求一致。相比之下，vector虽然提供高效的随机访问，但其插入和删除操作只在末尾高效；而list则在任何位置插入和删除都高效，但不提供随机访问。因此，deque是兼顾性能和灵活性的最佳选择。
而priority_queue需要随机访问和堆操作，因此它选择vector作为底层容器。虽然deque也支持这些操作，但vector在内存布局和性能优化方面更适合priority_queue的需求。
标准库中的stack
一、stack的基本概念
在之前的学习中我们已经对stack有所了解，它遵循后进先出（Last In First Out，LIFO）的原则。具体来说就就是STL对与栈这个数据结构的封装，使用时需要包含头文件#include<stack>。
二、stack的常用接口
| 函数说明 | 接口说明 |
| stack() | 构造空的栈 |
| empty() | 检测stack是否为空 |
| size() | 返回stack中的元素个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素val压入stack中 |
| pop() | 将stack中尾部的元素弹出 |
这些接口也十分简单，这里就不过多解释了。直接来看使用实例：
int main()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);cout << "容量大小为：" << st.size() << endl;cout << "出栈顺序为：";while (!st.empty()){int top = st.top();st.pop();cout << top << " ";}cout << endl;return 0;
}
三、stack的模拟实现
我们接下来可以试着模拟实现stack：
#include<deque>
namespace Stack
{template<class T, class Con=deque<T>>// template<class T, class Con=vector<T>>// template<class T, class Con = list<T>>class stack{public:stack(){// ...}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_back();}T& top(){return _c.back();}const T& top() const{return _c.back();}size_t size() const{return _c.size();}bool empty() const{return _c.empty();}private:Con _c;};
}
来个简单的测试代码：
int main()
{Stack::stack<int> st;st.push(10);st.push(20);st.push(30);st.push(40);st.push(50);cout << st.top() << endl;cout << st.size() << endl;st.pop();cout << st.top() << endl;cout << "Is stack empty? " << (st.empty() ? "Yes" : "No") << endl;while (!st.empty()){st.pop();}cout << "Is stack empty? " << (st.empty() ? "Yes" : "No") << endl;return 0;
}输出结果如下：
标准库中的queue
一、queue的基本概念
队列是一种线性表，其特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。这种数据结构遵循“先进先出”（FIFO，First In First Out）的原则。
二、queue的常用接口
| 函数说明 | 接口说明 |
| queue() | 构造空的队列 |
| empty() | 检测queue是否为空 |
| size() | 返回queue中的元素个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素val入队列 |
| pop() | 将队头元素出队列 |
三、queue的模拟实现
我们来借助deque来模拟实现一下：
namespace Queue
{template<class T,class Con=deque<T>>// template<class T,class Con=lsit<T>>class queue{public:queue(){// ...}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_front();}T& back(){return _c.back();}const T& back() const{return _c.back();}T& front(){return _c.front();}const T& front() const{return _c.front();}size_t size() const{return _c.size();}bool empty() const{return _c.empty();}private:Con _c;};
}
同样我们来个简单测试示例：
int main()
{Queue::queue<int> q;q.push(10);q.push(20);q.push(30);q.push(40);q.push(50);cout << "队列大小：" << q.size() << endl;cout << "队列首元素：" << q.front() << endl;cout << "队列尾元素：" << q.back() << endl;q.pop();cout << "队列大小：" << q.size() << endl;cout << "队列首元素：" << q.front() << endl;cout << "队列尾元素：" << q.back() << endl;cout << "Is queue empty? " << (q.empty() ? "Yes" : "No") << endl;while (!q.empty()){q.pop();}cout << "Is queue empty? " << (q.empty() ? "Yes" : "No") << endl;return 0;
}输出结果为：
标准库中的priority_queue
一、priority_queue的基本概念
priority_queue（优先级队列）是C++标准库中的一个容器适配器，它提供了一种以堆（heap）为底层结构的优先队列，支持高效的插入和最大（或最小）元素的提取操作。
priority_queue中的元素按照一定的优先级进行排序，每次取出的元素都是优先级最高的。它的底层实现通常使用堆数据结构，堆是一种具有特定性质的二叉树，可以高效地插入新元素和取出优先级最高的元素。 在priority_queue中，默认情况下采用最大堆实现，即优先级最高的元素（最大值）存储在根节点。但也可以通过自定义比较函数，将其转化为最小堆等其他形式。
二、priority_queue的常用接口
| 函数说明 | 接口说明 |
| priority_queue()/priority_queue(first,last) | 构造空的优先级队列 |
| empty() | 检测优先级队列是否为空 |
| size() | 返回queue中的元素个数 |
| top() | 返回优先级队列中的最大（最小）元素，堆顶元素 |
| push(x) | 在优先级队列中插入元素x |
| pop() | 删除优先级队列中的最大（最小）元素，即堆顶元素 |
三、priority_queue的使用
1.默认情况下，priority_queue是大堆。
#include<iostream>
#include<vector>
#include<queue>
#include<functional> // greater模板类所需要包含的头文件
using namespace std;
int main()
{// 默认创建的是大堆vector<int> v{ 3,1,5,2,9,8,7,0,6,4 };priority_queue<int> Q;for (auto& ele : v){Q.push(ele);}cout << Q.top() << endl;// 创建小堆priority_queue<int, vector<int>, greater<int>>q(v.begin(), v.end());cout << q.top() << endl;return 0;
}std::greater是一个模板类，它实现了一个仿函数（function object），用于比较两个对象的大小。通过重载()操作符，greater可以接受两个参数，并返回第一个参数是否大于第二个参数的布尔值。如果第一个参数大于第二个参数，则返回true；否则返回false。
输出结果为：
2.如果需要在priority_queue中存放自定义类型的数据，则需要在自定义类型中提供>或者<的重载。
class Date
{
public:Date(int year = 2000, 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;}
private:int _year;int _month;int _day;
};int main()
{// 大堆，需要用户在自定义类型中提供<的重载priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout << q1.top() << endl;// 如果要创建小堆，需要用户提供>的重载priority_queue<Date, vector<Date>, greater<Date>> q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout << q2.top() << endl;return 0;
}输出结果为：
结束语
我们简单的学习了一下stack和queue的内容，希望能对友友们有所帮助！！！
求点赞收藏评论关注！！！
感谢各位大佬！！！
)
