C++入门之stl六大组件--stack和queue源码深度剖析及模拟实现
目录
前言
一、stack的介绍和使用
1.stack的介绍
2.stack的使用
3.stack的模拟实现
二、queue的介绍和使用
1.queue的介绍
2.queue的使用
3.queue的模拟实现
三、priority_queue的介绍和使用
1.priority_queue的介绍
2.priority_queue的使用
3.priority_queue的模拟实现
3.1解决一个topK问题
四、容器适配器
1.什么是容器适配器
2.stl中stack和queue的底层结构
3.deque的简单介绍(vector +list)
总结
前言
本文中的源码均在本地vs2019下测试无误，上传文件至gitee，地址为:https://gitee.com/a_young/stack_queue_-priority_queue
一、stack的介绍和使用
1.stack的介绍
通过阅读官方文档：
1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定 的成员函数来访问其元素，将特定类作为其底层的元素特定容器的尾部(即栈顶）被压入和弹出。3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下 操作：
- empty：判空操作
- back：获取尾部元素操作
- push_back：尾部插入元素操作
- pop_back：尾部删除元素操作
4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器, 默认情况下使用deque。
2.stack的使用
- stack() 构造空的栈
- bool empty() const { return c.empty(); }检查stack是否为空
- size_type size() const { return c.size(); } 返回stack中元素个数
- reference top() { return c.back(); } 返回栈顶元素
- const_reference top() const { return c.back(); } 返回栈顶元素
- void push(const value_type& x) { c.push_back(x); } 将元素val压栈
- void pop() { c.pop_back(); } 将stack尾部元素弹出
3.stack的模拟实现
源码中使用的deque来作为栈的适配器，所以我们使用deque来模拟stack
template<class T, class Contanier = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}size_t size(){return _con.size;}bool empty(){return _con.empty();}private:Contanier _con;};void test_stack(){//stack<int, vector<int>>st; //数组栈// stack<int,list<int>> st; 链式栈stack<int, deque<int>>st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;}
}二、queue的介绍和使用
1.queue的介绍
1. 队列是一种容器适配器，专门用于在 FIFO 上下文 ( 先进先出) 中操作，其中从容器一端插入元素，另一端 提取元素。2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类， queue 提供一组特定的 成员函数来访问其元素。元素从队尾入队列，从队头出队列。3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作 :empty ：检测队列是否为空size ：返回队列中有效元素的个数front ：返回队头元素的引用back ：返回队尾元素的引用push_back ：在队列尾部入队列pop_front ：在队列头部出队列4. 标准容器类deque和list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque 。
2.queue的使用
queue() 构造空的队列empty() 检测队列是否为空，是返回 true ，否则返回 falsesize() 返回队列中有效元素的个数front() 返回队头元素的引用back() 返回队尾元素的引用push() 在队尾将元素 val 入队列pop() 将队头元素出队列
3.queue的模拟实现
#pragma once
#pragma once
#include<iostream>
#include<vector>
#include<stack>
#include<list>using namespace std;namespace jellytest
{//适配器模式/配接器 //队列 先进先出template<class T, class Contanier = 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();}bool empty(){return _con.empty();}private:Contanier _con;};void test_queue(){//stack<int, vector<int>>st; //数组栈// stack<int,list<int>> st; 链式栈queue<int, deque<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的介绍
1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素 ( 优先队列中位于顶部的元 素 ) 。3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类， queue 提供一组特 定的成员函数来访问其元素。元素从特定容器的 “ 尾部 ” 弹出，其称为优先队列的顶部。4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问，并支持以下操作：
- empty()：检测容器是否为空
- size()：返回容器中有效元素个数
- front()：返回容器中第一个元素的引用
- push_back()：在容器尾部插入元素
2.priority_queue的使用
优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue 。注意： 默认情况下 priority_queue 是大堆 。
priority_queue()/priority_queue(fifirst,last) 构造一个空的优先级队列empty( ) 检测优先级队列是否为空，是返回true，否则返回 falsetop( ) 返回优先级队列中最大(最小元素)，即堆顶元素push(x) 在优先级队列中插入元素xpop() 删除优先级队列中最大(最小)元素，即堆顶元素
3.priority_queue的模拟实现
通过上面的介绍，priority_queue的底层结构就是堆，因此此处只需对堆进行封装即可。stl中默认实现的是大堆。
这里先介绍一个新的概念--仿函数，使用仿函数定义的对象可以像函数一样使用，本质是调用运算符重载，如下定义：
struct less {bool operator()(int x, int y){return x<y;} }struct greater {bool operator()(int x,int y){return x>y;} }int main() {Less lessfun; //声明一个对象cout<<lessfun(1,2)<<endl; // 1 }stl中使用模板类，可以比较不止内置类型
3.1解决一个topK问题
topK问题实际上是找出文件中所有数的最大的前K个.
方法1：可以构造一个大堆，pop出前K个。
分析方法1：假设N很大，K很小，N个数都需要存到内存中，很浪费资源。
方法2:构造一个K个数的小堆，后面的数依次和堆顶元素进行比较，大于堆顶元素就进堆，替换堆顶元素，然后向下调整。最后前K大的数所有的就在堆中。
分析方法2：时间复杂度O(N*logK),空间复杂度O(K)
综上对两种方法比较，选择方法2来实现
template<class T>
struct less
{bool operator()(T & x, T& y){//如果是自定义类型这里需要自己实现运算符重载return x<y;}
}//创建一个小堆
template<class T,class Container = deque<T> ,class Compare = greter<T>>
class priority_queue
{public://向下调整void adjust_down(int parent){Compare com;int child = 2*parent +1;while(chile < _con.size()){// if(child+1 <_con.size() && _con[child] < _con[child+1])if(child+1 <_con.size() && com(_con[child] , _con[child+1])){++child;}// if(_con[parent] < _con[child])if( com(_con[parent] , _con[child]){swap(_con[child] , _con[parent]);child = parent;parent = 2*child+1;}else{break;}}}//向上调整void adjust_up(int child){Comapre com;int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (com(_con[parent], _con[child]))//if (Comapre()(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}//堆的一些成员函数 封装一些接口void push(){_con.push_back(x);adjust_up(_con.size()-1);}void pop(){swap(_con[0],_con[_con.size()-1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;
}void test_priority_queue()
{priority_queue<int,deque<int>,less<int>> pq;pq.push(0);pq.push(1);pq.push(2);pq.push(3);while(!pq.empty()){cout<<pq.top()<<" ";pq.pop();}四、容器适配器
1.什么是容器适配器
2.stl中stack和queue的底层结构
3.deque的简单介绍(vector +list)
deque(双端队列）：是一种双开口的“连续”空间的数据结构，双开口的含义是：可以在头尾两端进行插入删除操作，且时间复杂度为O（1），与vector比较，头插效率高，不用挪动元素，与list比较，空间利用率较高。缺点就是：中间插入删除麻烦
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。头插的时候，就在中控数组前面插入一个指针，尾插在中控尾巴插入一个
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护“整体连续”以及随机访问的假象，落在deque的迭代器上，因此deque的迭代器设计就比较复杂。
为什么选择 deque 作为 stack 和 queue 的底层默认容器stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以； queue 是先进先出的特殊线性数据结构，只要具有 push_back 和 pop_front 操作的线性结构，都可以作为 queue 的底层容器，比如 list 。但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器，主要是因为：1. stack 和 queue 不需要遍历 ( 因此 stack 和 queue 没有迭代器 ) ，只需要在固定的一端或者两端进行操作。2. 在 stack 中元素增长时， deque 比 vector 的效率高 ( 扩容时不需要搬移大量数据 ) ； queue 中的元素增长 时， deque 不仅效率高，而且内存使用率高。结合了 deque 的优点，而完美的避开了其缺陷。
总结
本文主要模拟实现了stack,queue,priority_queue的一些接口，简单介绍了什么是容器适配器。