目录
正文：
一、stack和queue的底层结构
在STL中stack和queue并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：
二、容器适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
三、deque
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
3.1 Deque（融合怪）原理：
之所以叫融合怪，是因为结合了数组和链表的优点：
在栈和队列底层是普通动态数组结构时：扩容时需要分配更大的新数组（如 2 倍扩容），拷贝旧数据，释放旧数组，预分配的空间可能未被完全利用造成浪费；当底层是链表结构时：每个节点单独申请内存，导致内存碎片化，每个节点需存储指针（双向链表为两个指针），空间利用率低。当底层是Deque时：通常由多个固定大小的内存块组成，通过一个中控表（或指针数组）管理这些块，只有在当前块满时才分配新块，避免一次性分配大空间。扩容时只需新增一个块，无需拷贝现有数据（均摊 O(1) 时间），而且每个内存块内部是连续的，缓存友好。
Deque 既不是简单的“一大段数组”（避免浪费），也不是链表（避免碎片化），而是通过分块策略在内存效率和操作效率之间取得平衡。
deque是通过中控器进行管理，本质是一个动态分配的指针数组（如T**或T*[]），每个指针指向一个固定大小的数据块。然后再通过迭代器的方式遍历缓冲区内的数据。
迭代器有start和finish本质又是对指针数组的封装，当start不等于finish时就可以不断++插入删除数据，start指向第一块缓冲区，finish指向最后一块缓冲区。
3.2 deque的缺陷：
与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看 到的一个应用就是，STL用其作为stack和queue的底层数据结构。
3.3 为何选择deque作为底层默认容器
stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
（1） stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
（2）在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。
四、优先级队列
优先级队列（Priority Queue）是一种特殊的队列，其中每个元素都有一个关联的优先级，出队时总是优先移除优先级最高（或最低）的元素。它的核心实现通常基于堆（Heap）数据结构，但也可以使用其他方式（如平衡二叉搜索树）。
4.1 实现优先级队列
按原本C++中优先级队列的格式，以下是类的基本书写格式，Container默认底层是数组结构也可以是list结构！它的成员变量直接是一个vector数组。
（1）入队列
一个队列最基本的就是入队列，由于底层是堆的数据结构，当在末尾插入一个数据后可能破坏原本堆结构，所以要根据建大堆还是小堆进行向下调整或上向上调整算法，使其符合堆结构。
（2）出队列
出队列不能直接pop掉第一个数据，不然会导致整个堆混乱。最佳方式是头尾互换，使第一个数据到数组的末尾，再删除最后一个数据，最后对堆进行调整算法使其再次满足堆结构！
（3）取队头
由于底层封装的是STL已有的vector数组结构，所以接下来全部操作可以直接调用vector的方法。
（4）队列个数
（5）队列判空
4.2 仿函数
在优先级队列中，反函数通常指改变优先级的比较方式。
比如一般情况下我们不能同时存在升序队列和降序队列，但可以在模板声明处添加第三个参数实现自定义控制它的顺序。这就叫做反函数（只是目前仿函数的一个用法）
仿函数是一个行为类似函数的对象，它通过重载 operator() 来实现。仿函数可以像普通函数一样调用，但可以携带状态（成员变量），比普通函数更灵活。
STL 提供了两个标准仿函数：
std::less<T>：默认使用 < 运算符，表示升序。
std::greater<T>：默认使用 > 运算符，表示降序。
为什么它要用<表示升序，>表示降序是人家原本语言设计就这样，虽然很奇怪但作为使用者也只能这样用了。
默认是Less：
（1）仿函数类
（2）优先级队列调整
因为引入了仿函数所以要对原本优先级队列做一下比较部分的微调
向上调整算法：
向下调整算法：
以上就是本节的全部内容，，下面附上优先级队列完整代码：
#pragma once
#include<vector>
#include<iostream>
using namespace std;
namespace zss
{
//反函数——一个类重载了（）
template <class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template <class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
//优先级队列
template<class T,class Container = vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
//2.向上调整算法
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[child] > _con[parent])
if (com(_con[parent], _con[child])) //_con[parent] < _con[child]
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//1.入队列
void push(const T& x)
{
_con.push_back(x);
//优先级队列的底层结构是堆，尾部插入数据后要调整为堆结构
adjust_up(_con.size() - 1);
}
//4.向下调整算法
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
//if (child + 1 < _con.size() && _con[child + 1] > _con[child])
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
//_con[child] < _con[child + 1]
{
++child;
}
//if (_con[child] > _con[parent])
if (com(_con[parent], _con[child])) //_con[parent] < _con[child]
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//3.出队列
void pop()
{
swap(_con[0], _con.size() - 1);
_con.pop_back();
//向下调整确保符合堆结构
adjust_down(0);
}
//5.取队头
const T& top()
{
return _con[0];
}
//6.队列个数
size_t size()
{
return _con.size();
}
//7.判空
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}完~期待下次的一起学习
有任何错误欢迎留言