容器适配器

C++顺序容器的底层能够模拟一些常见的数据结构，方法是通过容器适配器。

队列(queue)只允许在一端插入数据操作，在另一端进行删除数据操作的特殊线性表；进行插入操作的一端称为队尾（入队列），进行删除操作的一端称为队头（出队列）；队列具有先进先出（FIFO）的特性。（插入和删除操作在不同端口）;

堆栈(stack)插入和删除操作都在同一端进行，像是容器，只允许在顶部进行操作，因此操作端口也被称为栈顶（top）。其特点是后进先出（LIFO）;

优先队列(priority_queue)中的每个元素都有优先级，而优先级高（或者低）的将会先出队，而优先级相同的则按照其在优先队列中的顺序依次出队。

队列插入删除分属两个不同的端口，堆栈则是同一端口。

顺序容器中有些容器对pop_back和pop_front支持度不一样，有些只支持其中的一种，或者一个都不支持（array），需要注意的是，他们都不返回被处理的元素，有些事物可能需要在弹出的同时返回这个数据，这就让用户提前存好这个数据的额外操作，那么有没有一种更加简单的方法？有的，那就是容器适配器！

标准库定义了三个顺序容器适配器stackqueuepriority_queue。适配器是标准库中的一个通用概念。容器、迭代器和函数都有适配器。适配器就是数据结构，数据结构需要建立在容器之上。所以要求容器能够满足适配器抽象需求的功能

适配器有以下操作：

操作 含义 empty() 是否为空 size() 适配器大小 swap() swap(a,b) 交换 A a 默认构造 A a(b) 拷贝构造

对于适配器支持的顺序容器：

适配器类/顺序容器类型 array vector deque list forward_list stack × \boldsymbol \times × ✓ \checkmark ✓ ✓ \checkmark ✓(默认) ✓ \checkmark ✓ × \boldsymbol \times × queue × \boldsymbol \times × × \boldsymbol \times × ✓ \checkmark ✓(默认) ✓ \checkmark ✓ × \boldsymbol \times × priority_queue × \boldsymbol \times × ✓ \checkmark ✓(默认) × \boldsymbol \times × × \boldsymbol \times × × \boldsymbol \times × 一、栈适配器

栈（stack）是限定只在表尾进行插入和删除操作的一种线性表。允许插入或删除的那一端称为栈顶（top），另一端叫做栈底（bottom）。后进先出（Last In First out，LIFO）最能形容栈的特点。通常意义上说，栈支持以下操作：

• 压入栈顶（push）
• 删除栈顶（pop）
• 访问栈顶（top）

C++可以直接使用vector进行等价实现，push_back(push)，top(back())，pop_back(pop)看上去非常不直观，而且用户可能会利用vector的其他操作破坏这种栈机制。头文件#include

适配器会限制一些功能以达到用户想要的数据结构，为什么叫做适配器，因为它将一个通用容器，适配成我们想要的结构。不是所有的顺序容器都能适配，stack需要满足以下条件：

• push_back
• pop_back
• back

stack适配器有两个构造函数，一是默认构造函数，二是接受一个容器，拷贝初始化这个stack.

定义stack适配器实例:

#include  #include  #include  using namespace std; int main() { std::stack<double> s;//默认构造 s.push(3); s.push(4); s.push(5); s.pop(); std::cout<<s.top()<<std::endl; std::vector<double> v{ 1,2,3,4,5 }; std::stack<double, std::vector<double>> ss(v);//拷贝初始化 } 

接受一个顺序容器，这个顺序容器必须要满足这个适配器的抽象需要，所有适配器都必须具有添加和删除的能力，所以array永远不可能构造一个适配器。对于有一些其特有操作:

操作 含义 pop 弹出但不返回栈顶值 push(item) 将item压入栈顶(实现可能是拷贝或者移入) emplace(args) args构造 top() 返回但是不弹出 二、队列和优先队列

头文件#include，默认情况下queue底层实现由双端队列实现，绝大多数情况，我们直接使用std::queue即可。双端队列意味着我既可以取得队列的最前面的元素front()，也可以取得队列最后的元素back()，可以使用pop弹出最前面的元素。（front和pop一般搭配使用）

std::queue的构造函数如下： 队列适配器没有初始化列表方式但是可以使用容器作为构造参数，也就是：

std::queue<int> que1={1,2,3,4};//error,没有初始化列表的方式 std::queue<int> que2({1,2,3,4,5});//ok，隐式转换成deque进行构造 std::vector<int> ivec{2,4,5,6,7}; std::queue<int,std::vector<int>> que3(ivec);//ok,vector构造,注意queue需要声明为vector类型 std::queue<int> qu3(ivec.begin(),ivec.end());//ok,迭代器构造，不过这个用法在C++23的时候才可用 

queue是队列，它要求顺序容器具有以下功能：

• back
• push_back
• front
• push_front

priority_queue优先队列，它要求顺序容器具有以下功能：

• front
• push_back
• pop_back
• 随机存储

队列操作 解释 q.pop() 弹出queue的首元素或priority_queue最高优先级元素 q.front() 返回栈顶元素 q.back() 只适用于queue，返回尾元素 q.top() 只适用于priority_queue，返回最高优先级元素 q.push(item) 在queue末尾或priority_queue中恰当的位置创建一个元素其值为item q.emplace(args) 同上，不过元素由args创建

front表示队伍最前面那个，图中那个正在被服务的人；back表示队伍最后的，也就是背着绿色包包那个；pop表示将排在前边，也就是最先进入队列的人踢出队伍。一般来说，队列最开始的使用front首先被服务，然后通过pop踢出队伍（因为已经服务完了）

队列的遍历需要借助front和pop，保存front的元素，然后将其弹出pop，它是一个不可逆的过程：

//遍历打印，不可逆 while(!que.empty()) { auto ele=que.front();//如果是清空则不需要保存 que.pop(); std::cout<<ele<<" ";//也不需要打印 } //que已经为空 

20211022 因为实现生产消费者模型重新看了一次，并增加了部分内容