1. 前言
和C语言学习期间的学习顺序一样
顺序表,链表过了就是栈和队列
但是栈和队列非常特殊,它的内部结构
并不是靠自己实现的,而是一种适配器模式
本章重点:
本篇文章着重讲解适配器原理
和栈,队列的接口函数熟悉以及模拟实现
适配器里有一个特殊容器:deque
最后讲解优先级队列相关知识和实现
2. 栈和队列的接口函数熟悉
栈的接口函数熟悉:
由于栈结构只能支持栈顶插入,栈顶pop
所以它的接口很少,这里就不多介绍了!
队列的接口函数熟悉:
队列只比栈多了一个接口:back
队列的front相当于栈的top
在了解了接口函数后,可以尝试做几个题巩固
3. 适配器介绍
先看栈和队列的类模板:
我们发现第二个模板参数是:Container
并且它还有缺省值为 deque<T>
这里就直接引出一个概念: 适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
一个比较经典的例子就是插头的适配器:
那么在数据结构栈中,这种适配器是什么呢?
很显然,在C语言阶段实现栈时,我们
使用的底层是顺序表来实现,也就是
把顺序表做了一层封装和限制,让它
的功能变得和栈一样,C++这里也是一样!
我们在实现栈时不用再去写一个顺序表
而是直接调用库中的vector!
4. 栈和队列的模拟实现
栈的模拟实现要复用其他数据结构
所以在定义模板时要定义两个!
template<class T, class Container = deque<T>> class Stack { //...... private: Container _con; }
我们和库中的缺省值保持一致,使用deque
这个容器我们后面会有所解释!
这样使用栈非常的方便!因为此时的栈
就像"富二代"一样,不用写构造和析构函数
因为默认生成的构造或析构会去调用
内嵌类型的构造或析构帮助我们完成任务!
在此之后,只需要实现一些接口函数即可!
void push(const T& val) { _con.push_back(val); } 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(); }
注:函数中的push_back或back等函数接口是调用适配器中的!如vector中的
栈的结构实现完成,队列就交给你们了!
5. deque的简单介绍
deque也是一个STL库中的容器
先来看看它的介绍:
deque又被称为双端队列是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素,与list比较,空间利用率比较高
接下来看看它的接口函数:
deque既有头插头删也有尾插尾删
这是意料之中,它也支持方括号[]
其实对于deque的了解到这里就差不多了
下面的内容属于拓展了解,有兴趣的可以看看
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
deque扩容是直接另外开辟一份空间
再让中控数组指向新开辟的空间
再将原先空间的内容拷贝至新空间
注意它有一个中控数组的概念!
6. 优先级队列深度剖析
优先级队列的英文是: priority_queue
它也是一个容量适配器,文档的大致翻译:
优先级队列默认是大堆!
并且它的底层适配器默认是vector
优先级队列默认有三个类模板,然而第三个
模板就是决定此优先级队列是大堆还是小堆
它叫仿函数,我们先不管它,下一篇文章回讲解
我们需要了解的是,默认的less是大堆
我们显示传参greater时是小堆!
优先级队列的接口函数熟悉:
注:如果你想使用小堆,就要将前两个模板参数实例化后才能实例化第三个当less变成greater时,就是小堆
7. 优先级队列的模拟实现
在学习仿函数之前,先实现无仿函数版本:
基本结构和框架:
template<class T, class Container = vector<T>> class Priority_queue { public: //成员函数 private: Container _con;//此容器可能是vector可能是deque };
由于优先级队列是"富二代",所以
构造,析构和拷贝构造都可以忽略不写
优先级队列的插入和删除操作:
由于优先级队列实际上就是个堆
所以在插入,删除之后.都需要做一件事
那就是向上调整或向下调整!所以插入和
删除的关键其实就在于向上/下调整!
向上调整:
void AdjustUp(int* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] > a[parent]) { swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }
向下调整:
void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (a[child+1] < a[child] && child + 1 < n) { child++; } if (a[child] < a[parent]) { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
这两个操作在学习堆时就已经实现过了,老朋友了
详情可看: 堆以及topk问题
优先级队列的插入和删除
void push(const T& val)//堆的插入 { _con.push_back(val); adjust_up(_con.size() - 1); } void pop()//堆的删除 { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); }
插入和删除可谓是和堆的做法一模一样
其他的函数接口也是如此,这里就不多解读
我把优先级队列模拟实现的所有代码分享出来:
8. 总结以及拓展
其实我们可以感受到,有了前面STL
容器的学习,现在学习栈和队列要轻松许多
不仅是模拟实现上可以复用以前的容器
连使用方法和函数接口都和之前一样
这就是C++STL的魅力所在!
拓展阅读:
对于deque我们还有很多未知的地方
比如它的扩容是怎样完成的?是否是缩容?
deque是如何支持随机访问的?deque的缺陷?
有兴趣的老铁可以阅读下面这篇文章:
🔎 下期预告:模板进阶以及仿函数 🔍
