C++——STL之stack和queue详解
C++——STL之stack和queue详解
- 🏐什么是stack和queue
- 🏐stack和queue的实现
- 🏀什么是deque
- 🏀stack的模拟实现
- 🏀queue的模拟实现
- 🏐优先级队列（priority_queue)
- 🏀优先级队列的实现
- ⚽push
- ⚽pop
- ⚽top，empty，size
- ⚽构造
- ⚽仿函数
- 💬总结
👀先看这里👈
😀作者：江不平
📖博客：江不平的博客
📕学如逆水行舟，不进则退
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
❀本人水平有限，如果发现有错误的地方希望可以告诉我，共同进步👍
🏐什么是stack和queue
之前我们了解 stl六大组件中的容器，迭代器，这里再来了解下适配器stack和queue
堆栈是一种容器适配器，专门设计用于在后进先出的内容（后进先出）中运行，其中元素仅从容器的一端插入和提取。
队列是一种容器适配器，专门设计用于在的内容（先进先出）中运行，其中元素插入容器的一端并从另一端提取。
因为这个限制特性，所以没有迭代器接口。
第二个模板参数传的是一个容器，我们知道stack和queue的实现是可以通过不同的方式的，可以是顺序表的实现方式也可以是链表的实现方式，这里就是我们选择不同的容器，来达到不同的实现，这里默认容器为deque
🏐stack和queue的实现
🏀什么是deque
在上面stack和queue的类模板声明中我们就可以看到，它们的模板参数有两个，第一个是存储在stack和queue中的元素类型，而另一个是使用的容器类型。默认使用deque作为指定容器。那么deque是什么呢？
deque跟vector，list一样，也是一个容器，是一个既能支持随机访问，也能轻松做到头尾插入删除，看起来具备了vector和list二者的优势的一个双端开口队列。正是因为这种特性符合栈和队列的特性，所以用deque作为默认容器。
deque的底层是通过很多个小的数组buffer来实现的，这些buffer的地址存储在一个指针数组——中控数组中，如图
🏀stack的模拟实现
这里的模拟实现还是比较简单的，与数据结构差不多，就是要通过容器来做到相关接口。
#pragma once
#include <deque>
namespace ptj
{
template<class T, class Container = deque<T>>
class stack
{
public:
//尾插
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
//获取栈顶元素
T& top()
{
return _con.back();
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
//vector<T> _con;
Container _con;
};
}
🏀queue的模拟实现
#pragma once
#include <deque>
namespace ptj
{
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
T& back()
{
return _con.back();
}
T& front()
{
return _con.front();
}
const T& back() const
{
return _con.back();
}
const T& front() const
{
return _con.front();
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
Container _con;
};
}
🏐优先级队列（priority_queue)
优先级队列是一种容器适配器，根据一些严格的弱排序标准，专门设计使其第一个元素始终是它包含的最大元素。
类似于堆，其中可以随时插入元素，并且只能检索最大堆元素（优先级队列顶部的那个）。
我们发现这里用的底层容器默认是vector，没有用deque。因为它这里要大量运用[]，用deque效率低，没有vector好。当然你也可以换容器，没有规定死。
🏀优先级队列的实现
我们也来模拟实现下优先级队列，其实跟跟数据结构时建大堆的操作差不多（感兴趣的看堆排序相关内容——你知道有一种树叫二叉树吗？）
⚽push
这里写push的重点在于把插入的数向上调整到顶端
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[child] > _con[parent])
if (_con[parent] < _con[child])
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
⚽pop
这里写pop的重点在于向下调整
void adjust_down(size_t parent)
{
Compare com;
size_t child = parent * 2 + 1;
while (child < _con.size())
{
// 选出左右孩子中大的那一个
//if (child+1 < _con.size() && _con[child+1] > _con[child])
if (child + 1 < _con.size() && _con[child] < _con[child + 1])
{
++child;
}
//if (_con[child] > _con[parent])
if (_con[parent] < _con[child])
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
⚽top，empty，size
再来看一些常用的接口
取堆顶的数据
const T& top()//加const，不允许被修改数据
{
return _con[0];
}
判空
bool empty() const
{
return _con.empty();
}
算数据大小
size_t size() const
{
return _con.size();
}
⚽构造
这里我们建堆采用向下调整建堆，因为这样是时间复杂度是要低于向上调整建堆的（详情看堆排序相关内容——你知道有一种树叫二叉树吗？）
我们模拟迭代器构造，这里的第三个参数是仿函数（后面会有介绍），我们先不管它
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
//先把数据插入
while (first != last)
{
_con.push_back(*first);
++first;
}
// 再建堆
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
{
adjust_down(i);
}
}
⚽仿函数
仿函数顾名思义，它做到了函数的功能，却不是个函数，这是怎么做到的呢？我们来看一下吧
namespace ptj
{
template<class T>
class less
{
public:
bool operator()(const T& data1, const T& data2) const
{
return data1 < data2;
}
};
template<class T>
class greater
{
public:
bool operator()(const T& data1, const T& data2) const
{
return data1 > data2;
}
};
}
int main()
{
ptj::less<int> lsData;
cout << lsFunc(1, 2) << endl;
// 等价于下面
//cout << lsData.operator()(1, 2) << endl;
ptj::greater<int> gtData;
cout << gtData(1, 2) << endl;
return 0;
}
通过阅读上面的代码，我们可以发现我们封装了一个类，用类对象的方式去调用了一个函数operator()，通过将运算符（）重载来实现我们想要的功能。这就是仿函数，通过传参的类似方式做到了我们想要的功能。
我们可以将一个对象当成函数来用，比如在if语句那里（以向上调整里判断父亲和孩子大小为例），我们就可以写成
//if (_con[child] > _con[parent])
//if (_con[parent] < _con[child])
if (com(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
💬总结
- 优先级队列（priority_queue）传的是类，sort传的是对象，一个是容器适配器，一个在算法模块Algorithm中
- 这些容器适配器不是简单的选择容器封装，比如priority_queue中，我们还做了堆的相关算法操作。
