目录
前言
1. 容器的使用
1.1 stack
1.2 queue
2. 什么是适配器
3. stack&&queue底层实现
4. deque的简单介绍
4.1 deque的缺陷
5. priority_queue
思考
6. priority_queue的实现
前言
栈和队列在C语言中大家都有所了解,C语言的栈和队列都是我们手动去实现,而C++中的栈和队列不同,它们的内部并不是自己实现的,而是适配器模式,它们都是容器适配器;本文将会围绕栈和队列来介绍适配器的原理;
1. 容器的使用
在深入了解STL容器之前,我们先来看看stack和queue库里边提供了哪些接口;
1.1 stack
栈的功能接口及简介
1.2 queue
队列的功能接口及简介
从这些接口及功能上我们发现,栈和队列它们都不支持遍历;在刷题时,栈的应用相较来说也比较多;
下边是一些练习题目,可以练习一下:
最小栈(力扣)
栈的压入和弹出序列(牛客)
逆波兰表达式求值(力扣)
二叉树的层序遍历(力扣)
二叉树的层序遍历使用队列解决
2. 什么是适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口
它的核心其实就是复用,举个日常生活中的例子,充电器的适配器:
3. stack&&queue底层实现
开始时提到stack和queue都是容器适配器,那到底什么是容器适配器?我们先来看看它的底层声明或许就会明白了:
stack:
queue:
它们用到了两个模板参数,一个是存储的数据类型,一个就是底层实现的容器;它们默认使用的都是deque(双端队列);
那到底什么是容器适配器?容器适配器即将特定容器类封装作为其底层容器类
了解完这些我们可以上手来实现一下:
我们可以复用其他容器的接口来实现封装,为了和库里尽量保持一致,我们也使用双模板参数:
实现代码如下:
栈
template<class T, class container = deque<T>>
class stack
{
public:
void push(const T& x)
{
return _con.push_back(x);
}
void pop()
{
return _con.pop_back();
}
T& top()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.szie();
}
private:
container _con;
};
队列
template<class T, class container = deque<T>>
class queue
{
public:
void push(const T& x)
{
return _con.push_back(x);
}
void pop()
{
return _con.pop_front();
}
T& front()
{
return _con.front();
}
T& black()
{
return _con.black();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.szie();
}
private:
container _con;
};
在调用时我们也可以控制它底层使用的容器
queue<int, list<int>> q1;
stack<int, vector<int>> st;
我们在用STL库里的stack和queue时也没有传参啊?
这是因为库里边给Container(容器)一个缺省参数,默认使用的是deque(双端队列)
4. deque的简单介绍
双端队列名字中带有队列,但它其实并不是队列;
队列要求尾进头出,而双端队列可以双向进出;
简介
deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高,并且支持随机访问;
双端队列同时具体它们的优点,在功能上deque可以算的上是list和vector的结合版;
它的使用和list、vector的使用方法基本一致,但它的底层相较于它们却非常复杂;
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成,实际deque类似于一个动态的二维数组;
数组里边存的是指针,指针指向的是一个个的buff数组,这个存放指针的数组也叫作中控数组
中控满了进行扩容时,会直接开一块新空间,将内容拷贝过去(拷贝指针代价较小)
4.1 deque的缺陷
与vector相比,deque的优势是:头插和头删时,不需要挪动数据,效率很高,扩容时也不需要大量的挪动数据(只需要挪作指针即可);
与list相比,其底层是连续空间,空间利用率比较高;
它的各个属性都还可以可谓是 “ 六边形战士 ”,但是它的各个属性都不是最顶尖的;它的遍历效率没有vector高,中间插入删除操作没有list效率高;所以它主要作为stack和queue的底层容器;
主要原因有两个:
- stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作;
- 在stack中需要扩容时,deque比vector的效率高(扩容时不需要搬移大量数据),在queue中空间利用率较高,不需要频繁开空间;
5. priority_queue
优先队列它也是一种容器适配器,默认情况下priority_queue类实例化时使用的是vector;
那优先队列到底是什么?本质是其实就是堆,在默认情况下是大堆,通过我们所传的模板参数进行控制;
如果要创建小堆,将第三个模板参数换成greater比较方式
vector<int> v = { 3,1,5,6,4,0 };
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
思考
实现优先队列之前思考一个问题,优先队列需不需要实现:构造函数、拷贝构造、析构函数 ?
不需要,优先队列是一种容器适配器,它是通过其他容器封装来的,使用时生成默认的构造函数、拷贝构造、析构函数;它们又会去调用底层容器的构造函数、拷贝构造、析构函数;
6. priority_queue的实现
堆的相关内容前边已经介绍过了,详细介绍可见:二叉树的顺序存储(堆)
priority_queue基本框架如下:
template<class T, class container = vector<T>>
class priority_queue
{
public:
private:
container _con;
};
堆的核心内容就在于向上调整和向下调整(默认大堆),实现代码如下:
向上调整:
void adjust_up(int child)
{
size_t 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 adjust_down(int 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[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
入堆和出堆以及其他功能的实现
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
bool empty()
{
return _con.empty();
}
T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
以上便是priority_queue的基本实现;细心的朋友可能会发现,我们实现的与库里的有些不同,在调整大堆小堆时也不能通过传参控制,对于当前实现的priority_queue我们还需要做进一步的封装,达到这些需求需要了解模板相关的其他内容;下期我将会再次深入探讨模板——模板进阶;
以上便是本文的全部内容,希望可以对你有所帮助,感谢阅读!