C++ stl -- stack / queue / priority_queue
目录
前言
C语言学习阶段中学习过栈和队列两大基础数据结构 ，只不过C语言中需要自己造轮子 ， c++的stl不仅给我们提供了stack和queue，还提供了一种基于堆的优先级队列--priority_queue ，通过对于这三个序列式容器的学习可以对于适配器和仿函数有更好的理解。
一、stack
1.1 stack的使用
stack的常用接口如下
| function | explanation |
| stack() | constructor |
| empty() | 判断是否空 |
| size() | 返回栈中元素个数 |
| top() | 返回栈顶元素 |
| push() | 压栈 |
| pop() | 弹栈 |
1.2stack的模拟实现
这里我们使用vector作为我们的适配器，我们阅览源码会发现用的是deque ， deque是一种既能满足任意位置0(1)插入又能随机访问的一种数据结构 ，后续详解
template<class T, class Container = vector<T>>
class stack
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}
bool empty()
{
return _con.empty();
}
T& top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
}
;
二、queue
队列专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2.1queue的使用
| function | explanation |
| queue() | constructor |
| empty() | 检验是否为空 |
| size() | 返回有效元素个数 |
| front() | 返回队头元素引用 |
| back() | 返回队尾元素引用 |
| push() | 入队 |
| pop() | 出队 |
2.2queue的模拟实现
template<class T, class Container = list<T>>
class queue
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
size_t size()
{
return _con.size();
}
T& front()
{
return _con.front();
}
T& back()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
}
;
2.3容器适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
设计模式的使用将提高软件系统的开发效率和软件质量，节省开发成本。有助于初学者深入理解面向对象思想，设计模式使设计方案更加灵活，方便后期维护修改。
在stack，queue中 deque<T>接口转换到Container中。deque是什么呢？我们不是说stack可以用vector，queue用list吗，怎么这里用的deque。
三、deque
在容器适配器为什么会选择deque，那么就必须得从vector，list的优缺点说起
3.1vector ， list的优缺点
vector:
stack可以随机访问，但是头部中部插入删除效率低，并且还需要扩容
list:
虽然queue在任何地方插入删除效率高，但是不支持随机访问，CPU高速缓存命中率低
对于deque就完美兼容vector，list的优点。所以对于接口选择就是deque。
3.2deque的原理介绍
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和 删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
这个是deque一段的buffer数组，所以deque并不是真正连续的空间，它是由一段一段这样的buffer数组链接而成，一段一段的buffer数组被放在中控，这个中控就是一个指针数组，实际上deque类似于一个动态的二维数组， 如图：
这里的缓冲区就是buffer数组，用于存放数据。map就是中控器，就是存放指针。当map空间不够后，会再开辟一个中控-map。
3.3deque--插入
头插
尾插
查找：
即相当于二维数组一样，先找map中的地址（第一层），然后在找buffer（第二层）
缺点：
那么我们发现它下标访问有一定的消耗，没有vector快。当我们中间插入时候，它的中间插入的时候需要挪动数据，与list相比也是有消耗的。
deque不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到 某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作 为stack和queue的底层数据结构。
我们通过发现deque其实是没有想象中那样完美的，它与vector和list相比是不够极致的。vector是吕布，list是诸葛亮，那么deque就是魏延。所以更多的时候我们更需要极致。
deque的底层实现是比较复杂的，不仅仅是上诉简单两句的问题。
根据上图，对于deque的维护是通过两个迭代器，start和finsh。因为deque是作为stack和queue的底层默认容器，一般来说deque是不需要进行中间插入的，那么start和finsh就很好的处理头插和尾插。它通过frist和last指向头尾，头插通过start的frist，如果满了node链接map新开辟buffer的指针位置。尾插通过finish的last控制。如果top()和back(),即通过start的cur和finish的cur控制。
3.4deque的接口
通过stack，queue的接口与deque的接口对比，发现直接调用deque是非常适合充当stack，queue的默认容器。stack，queue就是直接调用deque的接口。
四、priority_queue
优先队列是一种容器适配器，而它实质就是堆。是否还记得堆是完全二叉树中用数组实现的，因为数组正好满足堆下标随机存取的需求，标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。相对deque，vector更加极致。priority_queue是默认大根堆。
4.1priority_queue的使用
priority_queue的使用来说也是比较简单的，接口也比较少。
| 函数声明 | 接口说明 |
| priority_queue()/priority_queue(first, last) | 构造一个空的优先级队列 |
| empty( ) | 检测优先级队列是否为空，是返回true，否则返回 false |
| top( ) | 返回优先级队列中最大(最小元素)，即堆顶元素 |
| push(x) | 在优先级队列中插入元素 |
| pop() | 删除优先级队列中最大(最小)元素，即堆顶元素 |
priority_queue与queue都是一个头文件。
priority_queue<int, vector<int>, less<int>> pq1;
pq1.push(4);
pq1.push(2);
pq1.push(1);
pq1.push(3);
while (!pq1.empty())
{
cout << pq1.top() << " ";
pq1.pop();
}输出：4 3 2 1
priority_queue<int, vector<int>, greater<int>> pq2;
pq2.push(4);
pq2.push(2);
pq2.push(1);
pq2.push(3);
while (!pq2.empty())
{
cout << pq2.top() << " ";
pq2.pop();
}输出： 1 2 3 4
4.2模拟实现
template<class T>
struct less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T, class Container = vector<T>, class cmp = less<T>>
class priority_queue
{
public:
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);
}
T& top() {
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty() {
return _con.size() == 0;
}
private:
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && cmp()(_con[child], _con[child + 1]))
{
++child;
}
//if(_con[child] < _con[parent])
if (cmp()(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (parent >= 0)
{
//if(_con[parent] > _con[child])
if (cmp()(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
Container _con;
}
;如果入队我们就向上调整，出队就向下调整
整体的思想还是比较简单的
五、仿函数/函数对象
5.1仿函数的实现
其实就是struct重载了()
template<class T>
struct less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};5.2仿函数的使用
冒泡排序
template <class T>
void BubbleSort(T* a, int n)
{
for (int i = 0; i < n; i++)
{
int flag = 0;
for (int j = 1; j < n - i; j++)
{
if (a[j - 1] > a[j])
swap(&a[j - 1], &a[j]);
flag = 1;
}
if (flag == 0)
break;
}
}在C语言时期，冒泡函数进行比较的时候，是需要进入冒泡函数内部改变">","<"。或者是通过函数指针的方式，在多增加一个函数参数。
方法一：
if (a[j - 1] > a[j]) //改变其大与小
对于封装的好的函数来说，这样对使用者是非常不友好的，那么就可以通过接口的方式，增加函数指针。
方法二：
void BubbleSort(T* a, int n，bool（*pcom）(int,int))
方法二的话，这个方法是比较搓的，使用的函数时需要传太多变量，阅读性也不够强。那么c++中函数模板就起到了重要的作用了。我们可以增加一个模板参数，再增加给函数的参数，通过类型的对象去比较，可以想函数一样去是使用。
template <class T,class compaer>
// 冒泡排序
void BubbleSort(T* a, int n,compaer com)
{
for (int i = 0; i < n; i++)
{
int flag = 0;
for (int j = 1; j < n - i; j++)
{
//if (a[j - 1] > a[j])
if (com(a[j - 1] , a[j]))
swap(a[j - 1], a[j]);
flag = 1;
}
if (flag == 0)
break;
}
}
void test_less()
{
qhx::less<int> lessFunc;
if (lessFunc(3, 2))
cout << "yes" << endl;
else
cout << "no" << endl;
}
void test_BubbleSort()
{
qhx::less<int> lessFunc;
int arr[] = { 1, 2, 4, 9, 8, 3, 6, 7 };
//BubbleSort(arr, sizeof(arr) / sizeof(arr[0]),lessFunc);
BubbleSort(arr, sizeof(arr) / sizeof(arr[0]), lessFunc);
for (auto e : arr)
{
cout << e << " ";
}
}
int main()
{
test_BubbleSort();
return 0;
}运行结果：9 8 7 6 4 3 2 1
这里的less是根据优先级队列来定义的，这里是降序，greater就是升序。
注意：这里模板参数是类，函数调用类模板增加的代码内存时不多的。例如上述只增加1个字节。