C++中的栈和队列

news/2024/5/20 4:27:04

✨前言✨

📘 博客主页：to Keep博客主页
🙆欢迎关注，👍点赞，📝留言评论
⏳首发时间：2024年5月8日
📨 博主码云地址：博主码云地址
📕参考书籍：《C++ Primer》《C++编程规范》
📢编程练习：牛客网+力扣网
**由于博主目前也是处于一个学习的状态，如有讲的不对的地方，请一定联系我予以改正！！！

C++中栈和队列

- 1 适配器
- - 1.1 适配器的介绍
  - 1.2 代码实现
  - 1.3 总结
- 2 仿函数
- 3 deque的原理（了解）

1 适配器

1.1 适配器的介绍

在C语言中，如果我们要实现栈和队列，就需要我们自己去手搓代码，并且实现底层利用的是顺序表还是链表也是有所不同的！在C++中还这样做，那你就慢了！在C++中我们学习了一些STL库中的容器，那么我们可不可以利用STL库中已经实现好的容器（vector，list，deque）呢？利用我们所学的模版，答案是可以的，所以像栈和队列这样的，并不需要自己去实现具体的函数，而是通过调用其他容器的函数而实现的，我们就称为适配器！事实上，适配器就是一种设计模式，它就是将一个类的接口转化成客户希望的另一个接口！

1.2 代码实现

我们首先来看看C++中对于栈的实现

#include <list>
namespace demo {template<class T,class Container = list<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.top();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

可以发现，我们只是调用list已经实现好的函数，就可以实现一个栈了！我们甚至可以将上面的容器换成vector，接下来我们在看一下C++库中是默认什么容器来实现的：
在这里插入图片描述

从图中我们可以发现：
1️⃣库里面是利用deque这个容器来实现栈的（队列其实也是）
2️⃣凡是一个容器，只要实现了以上5个红框中的函数，就可以实现栈！

1.3 总结

栈和队列的实现都是套用了其他容器中的函数而完成的，这里只是简单的介绍了栈，队列其实也是同理的！

2 仿函数

在了解完什么事适配器之后，我们在来实现一下priority_queue

namespace demo{template<class T,class Container = deque<T>>class priority_queue{public:void adjust_up(size_t child){//大根堆为例size_t parent = (child - 1) / 2;while (child > 0){if (_con[child]>_con[parent]){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else {break;}}}void adjust_down(size_t parent){size_t child = 2 * parent + 1;while (child<_con.size()){if (child + 1 < _con.size() && _con[child + 1] > _con[child]){child++;}if(_con[child]> _con[parent]){swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else {break;}}}bool empty(){return _con.empty();}void push(const T& x){_con.push_back(x);//堆向上调整adjust_up(_con.size()-1);}size_t size(){return _con.size();}void pop(){swap(_con[0], _con[_con.size()-1]);_con.pop_back();//堆进行向下调整adjust_down(0);}T& top(){return _con.front();}private:Container _con;};
}

我们可以发现，这里只是实现了大根堆，那么我们如果要实现小根堆呢？我们还要亲自动手在改调整堆中的大于小于的符号吗？就不可以指定一个规则让它自己去比较大小呢，从而实现大根堆与小根堆之间的切换。库里面就是利用仿函数来实现的！在上面的代码中做出如下修改，并且多加入一个模版参数
在这里插入图片描述

我们可以发现。只需要改变第三个模版参数，使用less< T >就是小根堆，使用greater< T >就是大根堆，就可以改变你要建立的是大根堆还是小根堆！那么明白了以上的场景，那么什么又是仿函数呢？
1️⃣仿函数不是一个函数，是一个类，在类中重载实现了运算符（）
2️⃣我们是将该类的对象作为参数，传入到priority_queue中，从而调用（）函数