栈、队列和优先队列的使用

1.栈的使用：

2.队列的使用：

3.优先队列的使用：叫队列，底层实现其实是大根堆；另外push 和 emplace 的区别为前者是对已有对象插入，后者可原地构造后插入。

4.容器适配器：可以理解为对底层数据结构进行封装，提供给客户需要的接口。

STL标准库中的stack 和 queue的底层结构默认都为deque。deque 是双端队列，是一种双开口的“连续”空间的数据结构，可以在头尾两端进行插入和删除操作，时间复杂度为O(1)，与 vector 比头插和删除效率高，不需要移动元素，扩容时，也无需移动元素效率高；与 list 相比，空间利用率高，不需要存储额外字段。deque 的缺陷是不适合遍历，因为在遍历时，deque 的迭代器要频繁检测其是否移动到某段小空间边界，导致效率低。

deque 并不连续的空间，而是由一段段连续的小空间拼接而成，类似一个二维数组。

5.仿函数：也叫函数对象，行为像函数的类对象，核心是类中重载函数调用运算符。仿函数对象可以保存状态，可以根据对象数据的不同，产生不同的行为

#include<iostream> class Add { public: int operator()(int x, int y)const { return x + y; } }; //使用时先创建对象，然后像调用函数一样调用他 int main() { Add add; int ret = add(10, 20);//add.operator()(10, 20); std::cout << ret << std::endl; }

class mycomparison { bool reverse; public: mycomparison(bool revparam = false) : reverse(revparam) {} bool operator()(const int& lhs, const int& rhs) const { if (reverse) return lhs > rhs; else return lhs < rhs; } }; int main() { mycomparison cmp1; // reverse == false mycomparison cmp2(true); // reverse == true cmp1(10, 20); // 相当于 10 < 20，结果为 true cmp2(10, 20); // 相当于 10 > 20，结果为 false }