适配器：
虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为 容器适配器 ，这是因为 stack 和队列只是对其他容器的接口进行了包装， STL 中 stack 和 queue 默认使用deque
换种生活上的理解：
我国家用电的电压标准一般是220V，现在大家既然看到这篇博客了，那应该自己也是有一条充电器了。充电器，顾名思义，就是用来给电池充电的设备，它通常包括一个电源适配器和一根充电线。而电源适配器，则是充电器的一个重要组成部分，它的主要功能是将交流电（AC）转换成直流电（DC），并调整电压和电流以满足不同设备的充电需求。 这里电源适配器就是一种适配器，防止了220V的电压与我们接触，保证了我们的人身安全
STL 中 stack 和 queue 默认使用deque作为适配器(Container)：
可以简单理解为：站和队列就是一个包装(一个比较特别的包装)
stack：
queue：
priority_queue:
stack与queue：(简单回忆)
栈：一种后进先出的数据结构：(表层的印象理解：)
队列：一种先进先出的数据结构：(表层的印象理解：)
deque的简单介绍：
原理介绍：
deque( 双端队列 ) ：是一种双开口的 " 连续 " 空间的数据结构 ，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1) ，与 vector 比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
deque其实就是vector和list的缝合怪
| vector | list |
| 优点： | 优点： |
| 尾插尾删效率不错，支持高效的下标随机访问 | 按需申请释放空间，不需要扩容 |
| 物理空间连续，所以高速缓存利用率高 | 任意位置插入删除 |
| 缺点： | 缺点： |
| 空间需要扩容，扩容有一些代价(效率和空间的浪费) | 不支持下标随机访问 |
| 头部和中间位置插入和删除效率低 |
deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个 动态的二维数组 ，其底层结构如下图所示：
看STL_deque原码理解更佳：
总结：
- deque头插尾插效率很高，更甚于vector和list
- deque下标随机访问也还不错，但是相比于vector，vector更胜一筹
- deque的中间插入删除效率很低
这也是为什么STL中stack和queue的适配器是给deque作为缺省值，因为stack和queue的主要实现功能还是出现在头部与尾部，deque在头尾的操作有着比vector和list更加高效的能力，因此，deque作为stack和queue的Cantainer是更适合不过的了，但是在其他情况就该考虑是否vector/list会不会更好呢？
STL中stack的实现：
功能介绍：
函数声明 |
接口说明 |
|---|---|
|
构造空的栈
|
|
|
检测 stack 是否为空
|
|
|
返回 stack 中元素的个数
|
|
|
返回栈顶元素的引用
|
|
|
将元素 val 压入 stack 中
|
|
|
将 stack 中尾部的元素弹出
|
底层实现：
#pragma once
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
using namespace std;
//template<class T>
//class stack
//{
//private:
// T* _a;
// size_t _top;
// size_t _capacity;
//};
namespace home
{
template<class T,class Container = deque<T>>
class stack
{
public:
//Container是一个自定义类型，会自动调用其构造函数，我们无需在此实现
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;//容器的适配转换出的stack
};
}STL中queue的实现：
功能介绍：
函数声明 |
接口说明 |
|---|---|
|
构造空的队列
|
|
|
检测队列是否为空，是返回 true ，否则返回 false
|
|
|
返回队列中有效元素的个数
|
|
|
返回队头元素的引用
|
|
|
返回队尾元素的引用
|
|
|
在队尾将元素 val 入队列
|
|
|
将队头元素出队列
|
底层实现：
#pragma once
#include<iostream>
#include<deque>
#include<list>
using namespace std;
namespace home
{
template<class T, class Container = deque<T>>
class queue
{
public:
//Container是一个自定义类型，会自动调用其构造函数，我们无需在此实现
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
const T& front() const
{
return _con.front();
}
const T& back() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;//容器的适配转换出的stack
};
}
STL中priority_queue的实现：
功能介绍：
1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的；
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素 ( 优先队列中位于顶部的元素)；
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类， queue提供一组特定的成员函数来访问其元素。元素从特定容器的“ 尾部 ” 弹出，其称为优先队列的顶部；
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
- empty()：检测容器是否为空
- size()：返回容器中有效元素个数
- front()：返回容器中第一个元素的引用
- push_back()：在容器尾部插入元素
- pop_back()：删除容器尾部元素
5. 标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue类实例化指定容器类，则使用vector；
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap 、 push_heap 和 pop_heap 来自动完成此操作；
优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中 元素构造成堆的结构，因此 priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue 。注意：默认情况下 priority_queue 是大堆
函数声明 |
接口说明 |
|---|---|
|
构造一个空的优先级队列
|
|
|
检测优先级队列是否为空，是返回 true ，否则返回 false
|
|
|
返回优先级队列中最大 ( 最小元素 ) ，即堆顶元 素
|
|
|
在优先级队列中插入元素 x
|
|
|
删除优先级队列中最大 ( 最小 ) 元素，即堆顶元 素
|
在默认情况下priority_queue是大堆，我们可以利用仿函数进行对priority_queue修改成小堆：
仿函数在冒泡排序的使用（参照）（本质一样）：（下面有相关的实现代码）
在相关文档中，就体现了仿函数：
仿函数用于回调，又是一个类，可以使用模板参数
底层实现：
#pragma once
#include<vector>
//仿函数，本质是一个类，这个类重载operator(),他的对象可以像仿函数一样来使用
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;
}
};
//仿函数用于回调，又是一个类，可以使用模板参数
//注意：常常用匿名对象
namespace home
{
template<class T, class Container = std::vector<T>, class Compare = Less<T>>
class priority_stack
{
//优先级队列其实就是默认按照大堆来top与pop
public:
void AdjustUp(int child)//向上调整
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[parent] < _con[child])
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(int parent)//向下调整
{
//假设法：先设左孩子小
size_t child = parent * 2 + 1;
Compare com;
while (child < _con.size())//child>=n说明孩子不存在，调整到叶子了
{
//孩子的正真调整
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
{
++child;
}
//if (_con[parent] < _con[child])
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()
{
return _con[0];
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}