| 容器适配器 | 头文件 | 特性 | 基础容器筛选条件 | 默认使用的基础容器 |
|---|---|---|---|---|
| stack | <stack > | 在同一端插入和删除元素, 先进后出（first-in,last-out,FILO)的特性 | 基础容器需包含以下成员函数： empty() size() back() push_back() pop_back() 满足条件的基础容器有 vector、deque、list。 | deque |
| queue | <queue > | 在一端插入元素，在另一端取出元素, 先进先出（first-in,first-out,FIFO),插入和删除都较快 | 基础容器需包含以下成员函数： empty() size() front() back() push_back() pop_front() 满足条件的基础容器有 deque、list。 | deque |
| priority_queue | <priority_queue> | 也是一种队列，每个元素被给定了一个优先级， 以此来控制元素可被访问的顺序 | 基础容器需包含以下成员函数： empty() size() front() push_back() pop_back() 满足条件的基础容器有vector、deque。 | vector |
stack 适配器的开头端通常称为栈顶。由于数据的存和取只能从栈顶处进行操作，因此对于存取数据，stack 适配器有这样的特性，即每次只能访问适配器中位于最顶端的元素，也只有移除 stack 顶部的元素之后，才能访问位于栈中的元素。
template<
class T,
class Container = std::deque<T>
> class stack
T - 存储的元素类型。
Container - 用于存储元素的底层容器类型。
| 成员函数 | 功能 |
|---|---|
| top | 访问栈顶元素 |
| 成员函数 | 功能 |
|---|---|
| empty | 检查底层容器是否为空 |
| size | 返回容纳的元素数 |
| 成员函数 | 功能 |
|---|---|
| push | 向栈顶插入元素 |
| emplace(C++11) | 在顶部原位构造元素 |
| pop | 删除栈顶元素 |
| swap(C++11) | 交换内容 |
#include <iostream>
#include <stack>
#include <list>
using namespace std;
int main()
{
//构建 stack 容器适配器
list<int> values{ 1, 2, 3 };
stack<int, list<int>> my_stack(values);
//查看 my_stack 存储元素的个数
cout << "size of my_stack: " << my_stack.size() << endl;
//将 my_stack 中存储的元素依次弹栈，直到其为空
while (!my_stack.empty())
{
cout << my_stack.top() << endl;
//将栈顶元素弹栈
my_stack.pop();
}
return 0;
}
输出
size of my_stack: 3
3
2
1
STL queue 容器适配器模拟的就是队列这种存储结构，因此对于任何需要用队列进行处理的序列来说，使用 queue 容器适配器都是好的选择
template<
class T,
class Container = std::deque<T>
> class queue
T - 存储的元素类型。
Container - 用于存储元素的底层容器
| 成员函数 | 功能 |
|---|---|
| front | 访问第一个元素 |
| back | 访问最后一个元素 |
| 成员函数 | 功能 |
|---|---|
| empty | 检查底层容器是否为空 |
| size | 返回容纳的元素数 |
| 成员函数 | 功能 |
|---|---|
| push | 向队列尾部插入元素 |
| emplace(C++11) | 在尾部原位构造元素 |
| pop | 删除首个元素 |
| swap | 交换内容 |
#include <iostream>
#include <queue>
#include <list>
using namespace std;
int main()
{
//构建 queue 容器适配器
std::deque<int> values{ 1,2,3 };
// 使用dqueue对 queue 进行初始化
std::queue<int> my_queue(values);//{1,2,3}
//查看 my_queue 存储元素的个数
cout << "size of my_queue: " << my_queue.size() << endl;
//访问 my_queue 中的元素
while (!my_queue.empty())
{
cout << my_queue.front() << endl;
//访问过的元素出队列
my_queue.pop();
}
return 0;
}
输出
size of my_queue: 3
1
2
3
priority_queue 容器适配器中元素的存和取，遵循的并不是 “First in,First out”（先入先出）原则，而是“First in，Largest out”原则。直白的翻译，指的就是先进队列的元素并不一定先出队列，而是优先级最大的元素最先出队列。
那么，priority_queue 容器适配器中存储的元素，优先级是如何评定的呢？很简单，每个 priority_queue 容器适配器在创建时，都制定了一种排序规则。根据此规则，该容器适配器中存储的元素就有了优先级高低之分。
举个例子，假设当前有一个 priority_queue 容器适配器，其制定的排序规则是按照元素值从大到小进行排序。根据此规则，自然是 priority_queue 中值最大的元素的优先级最高。
priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素，每当有新元素进入，它都会根据既定的排序规则找到优先级最高的元素，并将其移动到队列的队头；同样，当 priority_queue 从队头移除出一个元素之后，它也会再找到当前优先级最高的元素，并将其移动到队头。
基于 priority_queue 的这种特性，因此该容器适配器有被称为优先级队列.
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;
typename T：指定存储元素的具体类型；
typename Container：指定 priority_queue 底层使用的基础容器，默认使用 vector 容器。
typename Compare：指定容器中评定元素优先级所遵循的排序规则，默认使用std::less按照元素值从大到小进行排序，还可以使用std::greater按照元素值从小到大排序，但更多情况下是使用自定义的排序规则。
其中，std::less 和 std::greater 都是以函数对象的方式定义在 头文件中。关于如何自定义排序规则，后续章节会做详细介绍。
| 成员函数 | 功能 |
|---|---|
| top | 访问栈顶元素 |
| 成员函数 | 功能 |
|---|---|
| empty | 检查底层容器是否为空 |
| size | 返回容纳的元素数 |
| 成员函数 | 功能 |
|---|---|
| push | 向队列尾部插入元素 |
| emplace(C++11) | 在尾部原位构造元素 |
| pop | 删除首个元素 |
| swap | 交换内容 |
#include <iostream>
#include <queue>
#include <array>
#include <functional>
using namespace std;
int main()
{
//创建一个空的priority_queue容器适配器
std::priority_queue<int>values;
//使用 push() 成员函数向适配器中添加元素
values.push(3);//{3}
values.push(1);//{3,1}
values.push(4);//{4,1,3}
values.push(2);//{4,2,3,1}
//遍历整个容器适配器
while (!values.empty())
{
//输出第一个元素并移除。
std::cout << values.top()<<" ";
values.pop();//移除队头元素的同时，将剩余元素中优先级最大的移至队头
}
return 0;
}
demo
4 3 2 1
参考：
1、C++ STL 容器库 中文文档
2、STL教程：C++ STL快速入门
3、https://www.apiref.com/cpp-zh/cpp/header.html
4、https://en.cppreference.com/w/cpp/container
5、哔哩哔哩——侠姐聊算法——8.2.1 适配器与迭代器