【落羽的落羽 C++】stack和queue、deque、priority_queue、仿函数

一、stack和queue

1. 概述

我们之前学习的vector和list，以及下面要认识的deque，都属于STL的容器（containers）组件。而stack和queue，属于STL的配置器（或称为配接器）（adapters）组件，或者归类为容器配置器（container adapters），它们可以修饰容器的接口而呈现出全新的容器性质，即stack的“先进后出”和queue的“先进先出”特点。

2. 使用

stack的所有元素的进出都必须符合“先进后出”的条件，queue的所有元素的进出都必须符合“先进先出”的条件。换句话说，只有stack的栈顶元素和queue的队头元素才有机会被移除，因此stack和queue不提供遍历的功能，也不提供迭代器。

除此之外，stack和queue的功能和使用也都很好理解了，之前我们已经学过栈和队列。

• stack：

函数声明	接口说明
stack()	构造空的栈
empty()	检测栈是否为空
size()	返回栈中元素个数
top()	返回栈顶元素的引用
push()	在栈顶入栈
pop()	将栈顶元素出栈

使用演示：

• queue：

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空
size()	返回队列中元素个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾入队列
pop()	将队头元素出队列

使用演示：

3. 模拟实现

STL库中的stack和queue的模板实际上有两个模板类型：


第一个就是要存储的数据类型了。第二个代表它们所修饰的容器类型，前面说过，它们不是独立的容器，而是容器配置器，要依靠别的容器才能实现它们，这就是第二个模板参数的意义。我们可以用vector或list来实现出stack和queue，如stack<int, vector<int>>或queue<char, list<char>>，我们在上层使用stack和queue时是感受不到vector或list的区别的。不论是哪种容器，都有push、pop、front、back、empty等相关操作，得以再封装成stack和queue的功能。
模板参数也是可以有缺省值的，我们能看到STL标准库中的stack和queue的Container模板类型默认给了deque，deque也是一种容器，我们一会再介绍它。

除了这一点，stack和queue的模拟实现就很简单了，遵循它们的特性就好：

namespace lydly
{template<class T, class Container = deque<T>>class queue{private:Container _con;public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& front(){return _con.front();}const T& front() const{return _con.front();}T& back(){return _con.back();}const T& back() const{return _con.back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}};template<class T, class Container = deque<T>>class stack{private:Container _con;public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top() const{return _con.back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}};
}

二、deque

关于deque，简单了解就好。
对比一下vector和list的优缺点：

容器	优点	缺点
vector	支持下标随机访问、CPU高速缓存命中率高	头部或中部插入删除数据效率低、扩容有一定成本，存在一定浪费
list	任意位置插入删除数据效率高、不用扩容，按需申请空间，不存在浪费	不支持下标随机访问、CPU高速缓存命中率低

可见，vector和queue都有各自的优缺点，deque包含了两种容器的优点，是一种双向开口的线性连续空间

deque有一个中控器，存放着指向不同节点的指针，每一个节点是一个缓冲区buffer，是一个数组用于存放数据。执行尾插时，就在当前buffer的尾部插入数据，若当前buffer已满，就去中控器的下一个节点指向的buffer的第一个位置存放；执行头插时，要倒着看，当前buffer头部没有空间，就去中控器的上一个节点指向的buffer的最后一个位置存放，再头插一次就存放到倒数第二个位置，以此类推。头删和尾删也是一样的道理。

deque并不是真正完全连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似一个动态的二维数组，deque的迭代器的结构就更为复杂了。

所以，deque与vector相比，头部插入效率更高，不需要挪动元素；与list相比，空间利用率更高。但是，deque不适合遍历，因为在遍历时迭代器需要频繁检测每一个buffer是否到达边界，导致效率低下。而在序列式场景中，可能经常需要遍历，所以实际需要线性数据结构时，大多数情况下优先考虑vector和list，deque的应用并不多，目前能看到的一个应用就是STL用它作为stack和queue的底层数据结构。
而STL选择deque作为stack和queue的底层，主要原因也是stack和queue不需要遍历，只在固定的一端或两端进行操作，以及deque结合vector和list的优点了。

三、priority_queue

1. 概述和使用

priority_queue，意为优先级队列，是queue的一种，带有权值观念，其内的元素并非按照入队列的顺序排列，而是按照元素的权值排列，默认权值较高的元素排在前面。
举个栗子：

有没有发现，优先级队列其实就是我们之前学过的堆。

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的场景，都可以考虑使用优先级队列。默认情况下，优先级队列是大堆。

函数声明	接口说明
priority_queue()	构造空的优先级队列
empty()	检测优先级队列是否为空
size()	返回优先级队列中元素个数
top()	返回优先级队列中的最大（最小）元素，即堆顶元素
push()	在优先级队列中插入元素
pop()	删除优先级队列中的最大（最小）元素，即堆顶元素

2. 模拟实现

既然优先级队列就是堆，那么实现优先级队列也就和实现堆道理类似了：
传送门：https://blog.csdn.net/2402_86681376/article/details/145808942?spm=1011.2415.3001.5331（堆的讲解
要用到的向上调整算法、向下调整算法，我们都学习过了。

namespace lydly
{template<class T, class Container = vector<T>>class priority_queue{private:Container _con;public:priority_queue(){}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() const{return _con[0];}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:void adjustup(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjustdown(size_t parent){size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){++child;}if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}};
}

问题来了，我们想让优先级队列降序排列元素，再重载一次·未必太麻烦了，怎么办呢？这里就需要用到仿函数。

四、仿函数

在STL标准库中，我们看到优先级队列的模板参数中还有一个Compare，这个就是仿函数。

仿函数是一种类对象，顾名思义，它可以“模仿函数”，允许用户“以模板参数来指定所要采取的策略”。在priority_queue中，它的第三个模板类型参数就是仿函数，默认给了一个less，less其实是这样的：

template<class T>
class less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};

less是一个类，less<typename Container::value_type>就是一个匿名对象，它的里面重载了()，这样一来，倘若有less<T> Com;那我们就可以写出Com(a, b)，（a，b是T类型的）这个表达式的意思就是a < b！
举一反三，STL中还有greater的仿函数：

template<class T>
class greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};

倘若有greater<T> Com;那我们就可以写出Com(a, b)，这个表达式的意思就是a > b！

大堆和小堆的区别在于AdjustUp和AdjustDown中几处<或>的不同，有了上面的两种仿函数，我们就能在创建优先级队列时根据需要，模板参数传less或greater，区分大堆和小堆。具体是<还是>，就可以依靠传的是less还是greater来分别。STL的仿函数中的less和greater，就可以传给priority_queue的模板：

我们的模拟实现也按照这个思路来完成：

namespace lydly
{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{private:Container _con;public:priority_queue(){}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() const{return _con[0];}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:void adjustup(int child){//构造一个less或greater的对象Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);// child = parent;parent = (child - 1) / 2;}else{break;}}}void adjustdown(size_t parent){//构造一个less或greater的对象Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}};
}

关于less，我们还可能会遇到其他情况：

• 当想要比较的是自定义类型时，就需要这个自定义类型中重载<和>运算符，这一点很好理解。
• 当传入指针时，一般我们应该是想要比较的是指向的内容，但如果只把less写成刚才那样，会被解析成直接比较两个地址的值。这时，需要写成这样：

template<class T>
class less<T*>
{
public:bool operator()(const T* const & x, const T* const & y){return *x < *y;}
};