🏆个人主页：企鹅不叫的博客
🌈专栏
⭐️ 博主码云gitee链接：代码仓库地址
⚡若有帮助可以【关注+点赞+收藏】，大家一起进步💙系列文章💙
💙系列文章💙
【初阶与进阶C++详解】第二篇：C&&C++互相调用（创建静态库）并保护加密源文件
【初阶与进阶C++详解】第三篇：类和对象上（类和this指针）
【初阶与进阶C++详解】第四篇：类和对象中（类的六个默认成员函数）
【初阶与进阶C++详解】第五篇：类和对象下（构造+static+友元+内部类
【初阶与进阶C++详解】第六篇：C&C++内存管理（动态内存分布+内存管理+new&delete）
【初阶与进阶C++详解】第七篇：模板初阶（泛型编程+函数模板+类模板+模板特化+模板分离编译）
【初阶与进阶C++详解】第八篇：string类（标准库string类+string类模拟实现）
文章目录
💎一、stack和queue使用
🏆1.stack使用
stack() 构造空的栈 empty() 检测stack是否为空 size() 返回stack中元素的个数 top() 返回栈顶元素的引用 push() 将元素val压入stack中 pop() 将stack中尾部的元素弹出 void Testatack() { stack<int> s; s.push(1); s.push(2); s.push(3); s.push(4); while (!s.empty()) { cout << s.top() << " "; s.pop(); } cout << endl; }
🏆2.queue使用
queue() 构造空的队列 empty() 检测队列是否为空，是返回true，否则返回false size() 返回队列中有效元素的个数 front() 返回队列中第一个元素 back() 返回队列中最后一个元素 push() 在队尾将元素val入队列 pop() 在队尾将元素val出队列 void Testqueue() { queue<int> q; q.push(1); q.push(2); q.push(3); q.push(4); while (!q.empty()) { cout << q.front() << " "; q.pop(); } cout << endl; }
💎二、容器适配器（deque）
适配器是一种设计模拟，将一个类的接口转化成另一个类的接口
//std::stack template <class T, class Container = deque<T>> class stack; //std::queue template <class T, class Container = deque<T>> class queue;以上使用了容器适配器，默认使用的是deque。
deque(双端队列)：是一种双开口底部总体不连续空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
底层结构不是一段连续的空间，而是由多个小空间组成，相等于一个动态二维数组，但与vector和list相比又会有差异。
deque的优点：
1.相比于vector，deque可以进行头插和头删，且时间复杂度是O(1)，扩容是也不需要大量挪动数据，因此效率是比vector高的。
2.相比于list，deque底层是是连续的空间（单底层不是连续空间），空间利用率高,，也支持随机访问（相比较list而言），但没有vector那么高。
3.总的来说，deque是一种同时具有vector和list两个容器的优点的容器，有一种替代二者的作用，但不是完全替代。deque的缺点：
1.不适合遍历，因为在遍历是，deque的迭代器要频繁地去检测是否运动到其某段小空间的边界，所以导致效率低下。
2.deque的随机访问的效率是比vector低很多的，实际中，线性结构大多数先考虑vector和list。
💎三、stack和queue模拟实现
🏆1.stack模拟实现
创建一个Container的对象 _con，再借助对象完成封装，默认使用的是deque，其实也可以使用vector
template<class T, class Container = deque<T>> class stack { public: size_t size() { return _con.size(); } const T& top() { return _con.back(); } void push(const T& val) { _con.push_back(val); } void pop() { _con.pop_back(); } bool empty() { return _con.empty(); } private: Container _con; };stack使用
void test_stack() { stack<int, vector<int>> s; s.push(1); s.push(2); s.push(3); s.push(4); while (!s.empty()) { cout << s.top() << " "; s.pop(); } cout << endl; }
🏆2.queue模拟实现
注意：queue不能使用vector作为容器，vector头插效率很低，我们可以用list作为容器
template<class T, class Container = deque<T>> class queue { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_front(); } const T& front() { return _con.front(); } const T& back() { return _con.back(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con; };queue使用
void test_queue() { queue<int, list<int>> q; //queue<int, vector<int>> q; // 不行,头插效率低 q.push(1); q.push(2); q.push(3); q.push(4); while (!q.empty()) { cout << q.front() << " "; q.pop(); } cout << endl; }
💎四、priority_queue (优先级队列)
🏆1.priority_queue介绍和使用
和queue一样都是属于头文件< queue >，底层采用vector容器作为底层数据结构
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;优先级队列就是一个堆，默认是大堆，有关堆知识的传送门
priority_queue()/priority_queue(first, last) 构造一个空的优先级队列 empty( ) 检测优先级队列是否为空，是返回true，否则返回 false top( ) 返回优先级队列中最大(最小元素)，即堆顶元素 push(x) 在优先级队列中插入元素x pop() 删除优先级队列中最大(最小)元素，即堆顶元素 void test_priority_queue() { priority_queue<int, vector<int>> pq; pq.push(5); pq.push(7); pq.push(4); pq.push(2); pq.push(6); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; }
🏆2.priority_queue模拟实现
2.1priority_queue框架
模拟实现需要用到堆的知识，C++有关堆的其实有相关函数，传送门
模板中有第三个参数Compare(仿函数，类)，明确优先级队列是升序还是降序的
//优先级队列-大堆(<), 小堆(>) template<class T, class Container = vector<T>, class Compare = less<T>>//默认是大堆 class priority_queue { public: private: Container _con;//利用适配器控制优先级队列 };
2.2仿函数
注意，由于仿函数是个类，所以我们在使用时要重载(),使得可以像函数一样使用，仿函数是模板函数，速度比一般函数慢，但本质上简化了代码。
template<class T> //小于 struct less { bool operator()(const T& x, const T& y) const { return x < y; } }; //大于 template<class T> struct greater { bool operator()(const T& x, const T& y) const { return x > y; } };仿函数就是用一个类封装一个成员函数operator()，使得这个类的对象可以像函数一样去调用。
less<int> le; cout << le(2, 3) << endl;// 该类实例化出的对象可以具有函数行为库函数中less和greater存放在< functional >头文件中
2.3priority_queue模拟实现
void AdjustUp(int child) { int parent = (child - 1) / 2; while (child > 0) { //if (_con[child] > _con[parent]) //< 建小堆 > 建大堆 if (_comFunc(_con[parent], _con[child])) { swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void AdjustDown(int parent) { size_t child = parent * 2 + 1; while (child < _con.size()) { //if (child+1 < _con.size() && _con[child] < _con[child+1]) if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1])) { ++child; } //if (_con[parent] < _con[child]) //建大堆 if (_comFunc(_con[parent], _con[child])) { swap(_con[parent], _con[child]); parent = child; child = parent * 2 + 1; } else { break; } } } //先将顶部元素和队尾元素交换，在删除队尾元素，在向下调整建立大堆或者小堆 void pop() { assert(!_con.empty()); swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } //先在队尾插入数据，然后向上调整建大堆或者小堆 void push(const T& x) { _con.push_back(x); AdjustUp(_con.size() - 1); } const T& top() { return _con[0]; } size_t size() { return _con.size(); } bool empty() { return _con.empty(); }