C++——stack与queue
目录
引言
在之前的博客中，我们学习了栈（Stack）与队列（Queue）并尝试使用C语言实现其功能，同时我们在C++的学习中对STL中的string vector等容器也进行了学习，接下来我们来学习C++中的栈和队列。
可以先看看这两篇文章，更有助于我们学习：
容器适配器
在学习stack和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的内容，希望能对友友们有所帮助！！！
求点赞收藏评论关注！！！
感谢各位大佬！！！
