【C++】栈、队列、双端队列与优先级队列
目录
一、stack（栈）
二、queue（队列）
三、deque（双端队列）
（一）概念
（二）为什么能作为 stack 和 queue 的容器
（三）缺点
四、priority_queue（优先级队列）
（一）概念
（二）仿函数
（三）模拟实现优先级队列
vector、list 是容器，而 stack 与 queue 是容器适配器。
所谓的容器适配器，其实就是在容器的基础上进行封装，得到我们的目标结构。
如图所示，vector 和 queue的第二个模板参数便是封装的容器，我们可以看到默认的容器是deque，我们也可以选择 vector 或者 list 。这种设计模式被称为适配器模式。
C语言版本实现：数据结构——栈与队列-CSDN博客
一、stack（栈）
栈的特点是后进先出，同时不提供迭代器。
下面是模拟实现：
#pragma once
#include <iostream>
#include<deque>
using namespace std;
namespace mh
{
template<class T, class Con = deque<T>>
class stack
{
public:
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_back();
}
T& top()
{
return _c.back();
}
const T& top()const
{
return _c.back();
}
size_t size()const
{
return _c.size();
}
bool empty()const
{
return _c.empty();
}
private:
Con _c;
};
}二、queue（队列）
队列的特点是先进先出，同时不提供迭代器。
下面是模拟实现：
#pragma once
#include <iostream>
#include<deque>
using namespace std;
namespace mh
{
template<class T, class Con = deque<T>>
class queue
{
public:
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_front();
}
T& back()
{
return _c, back();
}
const T& back()const
{
return _c.back();
}
T& front()
{
return _c.front();
}
const T& front()const
{
return _c.front();
}
size_t size()const
{
return _c.size();
}
bool empty()const
{
return _c.empty();
}
private:
Con _c;
};
}三、deque（双端队列）
（一）概念
deque是具有动态大小的顺序容器，可以在两端扩展或收缩。
（二）为什么能作为 stack 和 queue 的容器
deque不仅支持 [ ] 访问元素，而且头尾插入删除效率非常高。对于 stack 和 queue这两种结构只能在头或者尾进行操作，因此 deque 非常契合需求。
栈的持续插入元素时，vector的扩容需要挪动数据，而deque扩容时并不需要对原生数据进行挪动，只需增加中控数组和段空间的映射关系并在段空请插入元素即可。队列的元素增长时，deque效率高，同时因为存在部分连续存储，所以三级缓存命中率及空间利用率比list高。
（三）缺点
随机访问速度不如vector。由于deque的中控数组中指向的一段段地址空间之间并不连续，所以随机访问时需要计算目标数据处于哪个中控指针指向的空间的第几个元素。计算方式与磁盘定位扇区类似（LBA地址转化为CHS地址）。所以deque的随机访问速度并没有vector快。
中间插入、删除速度不如list。从deque的底层结构图中可以看出，中间插入、删除数据仍会产生数据的挪动且挪动复杂。deque中间插入、删除数据的速度不如list。
四、priority_queue（优先级队列）
（一）概念
优先级队列是一种容器适配器，不提供迭代器，它的底层是一个堆（默认是大堆），这个堆默认使用vector进行适配。
其中第一个模板参数表明优先级队列存储元素的类型，第二个函数参数表明封装的容器类型，而第三个模板参数是仿函数，默认调用库里的 less ，默认生成大根堆。
priority_queue<int, vector<int>, less<int>> pq; //大堆
priority_queue<int, vector<int>, greater<int>> pq; //小堆（二）仿函数
仿函数是一种行为类似于函数的对象，它通过重载圆括号操作符“()`”来实现类似函数的调用方式。
namespace mh
{
template<class T>
class less {
public:
bool operator()(const T& x, const T& y)const
{
return x < y;
}
};
template<class T>
class greater {
public:
bool operator()(const T& x, const T& y)const
{
return x > y;
}
};
}
int main()
{
mh::less<int> comp;
if (comp(1, 2))
cout << "1 < 2" << endl;
else
cout << " 1 >= 2" << endl;
return 0;
}（三）模拟实现优先级队列
namespace mh
{
template<class T>
class less {
public:
bool operator()(const T& x, const T& y)const
{
return x < y;
}
};
template<class T>
class greater {
public:
bool operator()(const T& x, const T& y)const
{
return x > y;
}
};
template <class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
private:
Container c;
Compare comp;
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (comp(c[parent], c[child]))
{
swap(c[parent], c[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < c.size())
{
if (child + 1 < c.size() && comp(c[child], c[child + 1]))
{
++child;
}
if (comp(c[parent], c[child]))
{
swap(c[parent], c[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
public:
priority_queue()
{
}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:c(first, last)
{
for (size_t i = (c.size() - 1 - 1) / 2; i > 0; --i)
{
adjust_down(i);
}
}
bool empty() const
{
return c.empty();
}
size_t size() const
{
return c.size();
}
const T& top()const
{
return c.front();
}
void push(const T& x)
{
c.push_back(x);
adjust_up(c.size() - 1);
}
void pop()
{
swap(c[0], c[c.size() - 1]);
c.pop_back();
adjust_down(0);
}
};
};当我们队内元素是指针类型时，对于自定义仿函数，我们可以使用函数重载进行指定类型的处理，也可以使用模板特化进行指针类型的处理。