目录
一，栈_刷题必备
二，stack实现
1.什么是容器适配器
2.STL标准库中stack和queue的底层结构
了解补充：容器——deque
1. deque的缺陷
2. 为什么选择deque作为stack和queue的底层默认容器
三，queue实现
1. 普通queue
2,优先级队列（有难度）
<1>. 功能
<2>. 模拟实现
1). 利用迭代器_构造
2).仿函数
sort函数中的仿函数使用理解
结语
一，栈_刷题必备
常见接口：
stack() 造空的栈empty() 检测 stack 是否为空size() 返回 stack 中元素的个数top() 返回栈顶元素的引用push() 将元素 val 压入 stack 中pop() 将 stack 中尾部的元素弹出
简单应用，刷点题：
155. 最小栈
栈的压入、弹出序列_牛客题霸_牛客网
150. 逆波兰表达式求值
二，stack实现
思路：在C语言期间，我们可以通过链表，数组形式实现过stack，而数组形式效率更高，所以stack的实现可以直接复用vector接口，包装成栈先进后出的特性。
#pragma once
#include <iostream>
#include <vector>
#include <list>
using namespace std;
namespace my_s_qu
{
template <class T >
class stack
{
public:
void push_back(const T& x)
{
Data.push_back(x);
}
void Pop()
{
Data.pop_back();
}
T& top()
{
return Data.back();
}
const T& top() const
{
return Data.back();
}
bool empty() const
{
return Data.empty();
}
size_t size() const
{
return Data.size();
}
private:
vector<T> Data;
};
}很简单不是吗？ 到这里并没有结束，我们发现，我们的栈只能通过vector实现。根据c++标准库，我们还差个适配器的实现，换句话说，我们实现的栈不支持容器适配器。
1.什么是容器适配器
2.STL标准库中stack和queue的底层结构
回到我们栈的实现，我们仅支持vector模式设计，优化为成容器适配器支持所有容器，都能支持栈的先进后出的特性。（在我看来这中思想更为重要）
namespace my_s_qu
{
template <class T, class container = deque<T> > // 添加容器模板
{
public:
void push_back(const T& x)
{
Data.push_back(x);
}
......
private:
container Data; // 容器换成模板
};
}其中deque又是什么？
了解补充：容器——deque
那deque是如何借助其迭代器维护其假想连续的结构呢？
1. deque的缺陷
优势：
与vector比较，deque的 优势是： 头部插入和删除效率高。 不需要搬移元素，效率特别高，而且在 扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较， 优势： 支持随机访问。其底层是连续空间， 空间利用率比较高，不需要存储额外字段。
缺陷：
不适合遍历。因为在遍历时，deque的迭代器要 频繁的去 计算每个数据的位置，导致 效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list， deque的应用并不多，而目前能看到的一个应用就是， STL用其作为stack和queue的底层数据结构。
2. 为什么选择deque作为stack和queue的底层默认容器
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。
三，queue实现
1. 普通queue
queue实现，我们这次以容器适配器进行。
template <class T, class container = deque<T>>
class queue
{
public:
void push_back(const T& x)
{
Data.push_back(x);
}
void Pop()
{
Data.pop_front();
}
T& back()
{
return Data.back();
}
const T& back() const
{
return Data.back();
}
T& front()
{
return Data.front();
}
const T& front() const
{
return Data.front();
}
bool empty() const
{
return Data.empty();
}
size_t size() const
{
return Data.size();
}
private:
container Data;
};2,优先级队列（有难度）
简介：
<1>. 功能
priority_queue()/priority_queue(fifirst, last) 构造一个空的优先级队列empty( ) 检测优先级队列是否为空，是返回true，否则返回falsetop( ) 返回优先级队列中最大(最小元素)，即堆顶元素push(x) 在优先级队列中插入元素xpop() 删除优先级队列中最大(最小)元素，即堆顶元素pop_back() 删除容器尾部元素
<2>. 模拟实现
完成优先级队列，需要用到堆方面的知识，如果堆大家不太熟悉了，建议将堆实现内容复习一遍：
详解树与二叉树的概念，结构，及实现（上篇）_花果山~~程序猿的博客-CSDN博客
利用堆方面知识，完成最基础的框架：
namespace my_priority_queue
{
template <class T, class container = vector<T>>
class priority_queue
{
public:
// 自定义类型，不需要给他初始化
void ajust_up(size_t child)
{
int parent;
while (child > 0)
{
parent = child / 2;
if (_pri_queue[child] > _pri_queue[parent]) // 写大堆
{
std::swap(_pri_queue[child], _pri_queue[parent]);
child = parent;
parent = child / 2;
}
else
{
break;
}
}
}
T& top()
{
return _pri_queue[0];
}
bool empty()
{
return _pri_queue.empty();
}
void push(const T& x)
{
_pri_queue.push_back(x);
// 向上调整
ajust_up(_pri_queue.size() - 1);
}
size_t size()
{
return _pri_queue.size();
}
void ajust_down()
{
size_t parent = 0;
size_t child = 2 * parent + 1;
while (child < _pri_queue.size())
{
if (child + 1 < _pri_queue.size() && _pri_queue[child + 1] > _pri_queue[child])
{
child++;
}
if (_pri_queue[parent] < _pri_queue[child])
{
std::swap(_pri_queue[parent], _pri_queue[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
std::swap(_pri_queue[0], _pri_queue[size() - 1]);
// 向下调整
_pri_queue.pop_back();
ajust_down();
}
private:
container _pri_queue;
};
}这里我们会有一个疑问，那我们要构建升序怎么办？ 仿函数会解释
1). 利用迭代器_构造
// 自定义类型，不需要给他初始化
priority_queue()
{}
template <class newiterator>
priority_queue(newiterator begin, newiterator end)
: _pri_queue()
{
while (begin != end)
{
push(*begin);
begin++;
}
}2).仿函数
在该场景下，我们的优先级队列已经实现了降序的功能，那我们如何实现升序？ 什么你说再写一段，改一下符号？？
这里仿函数就得引出了，仿函数，那么它并不是函数，那是什么？ （仿函数比如：less, greater）
仿函数本质是一个类，根据上图中，compare 模板，说明这里的仿函数，就是用来灵活改变大小堆符号的。
我们直接实现结果：
template <class T>
struct less
{
bool operator()(const T& left, const T& right)const
{
return left < right;
}
};
template <class T>
struct greater
{
bool operator()(const T& left, const T& right)const
{
return left > right;
}
};这个两个类都是重载了operator(),因此我们在实例化对象后，使用：
template <class T,class compare = less<T>>
compare t;
cout << t(1, 2) << endl;
从外表来看，就像一个函数调用，但实际是，一个类的成员函数的调用
t.operator(1,2)
这样我们就可以直接改变仿函数的类，来控制大小堆了。
sort函数中的仿函数使用理解
函数模板中：
sort函数作为行参中使用：
sort(s.begin, s.end, greater<int> () ); // 函数中是要做参数的，我们加个括号就是一个匿名对象了文章来源：https://www.toymoban.com/news/detail-636047.html
结语
本小节就到这里了，感谢小伙伴的浏览，如果有什么建议，欢迎在评论区评论，如果给小伙伴带来一些收获请留下你的小赞，你的点赞和关注将会成为博主创作的动力。文章来源地址https://www.toymoban.com/news/detail-636047.html
到了这里，关于【STL】优先级队列&反向迭代器详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
