网站建设设计猫和老鼠,湖南省建设厅官网查询,舟山网页设计,科技改变生活目录
前言
一、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的模…目录
前言
一、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
templateclass T, class Contanier dequeTclass 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(){//stackint, vectorintst; //数组栈// stackint,listint st; 链式栈stackint, dequeintst;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 否则返回 false size() 返回队列中有效元素的个数 front() 返回队头元素的引用 back() 返回队尾元素的引用 push() 在队尾将元素 val 入队列 pop() 将队头元素出队列 3.queue的模拟实现
#pragma once
#pragma once
#includeiostream
#includevector
#includestack
#includelistusing namespace std;namespace jellytest
{//适配器模式/配接器 //队列 先进先出templateclass T, class Contanier dequeTclass 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(){//stackint, vectorintst; //数组栈// stackint,listint st; 链式栈queueint, dequeint 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()在容器尾部插入元素 pop_back() 删除容器尾部元素 5. 标准容器类 vector 和 deque 满足这些需求。默认情况下如果没有为特定的 priority_queue 类实例化指 定容器类则使用 vector 。 6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap 、 push_heap 和 pop_heap 来自动完成此操作。 2.priority_queue的使用 优先级队列默认使用 vector 作为其底层存储数据的容器在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构因此 priority_queue 就是堆所有需要用到堆的位置都可以考虑使用 priority_queue 。注意 默认情况下 priority_queue 是大堆 。 priority_queue()/priority_queue(fifirst,last) 构造一个空的优先级队列 empty( ) 检测优先级队列是否为空是返回true否则返回 false top( ) 返回优先级队列中最大(最小元素)即堆顶元素 push(x) 在优先级队列中插入元素x pop() 删除优先级队列中最大(最小)元素即堆顶元素 3.priority_queue的模拟实现 通过上面的介绍priority_queue的底层结构就是堆因此此处只需对堆进行封装即可。stl中默认实现的是大堆。 这里先介绍一个新的概念--仿函数使用仿函数定义的对象可以像函数一样使用本质是调用运算符重载如下定义 struct less
{bool operator()(int x, int y){return xy;}
}struct greater
{bool operator()(int x,int y){return xy;}
}int main()
{Less lessfun; //声明一个对象coutlessfun(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来实现 templateclass T
struct less
{bool operator()(T x, T y){//如果是自定义类型这里需要自己实现运算符重载return xy;}
}//创建一个小堆
templateclass T,class Container dequeT ,class Compare greterT
class priority_queue
{public://向下调整void adjust_down(int parent){Compare com;int child 2*parent 1;while(chile _con.size()){// if(child1 _con.size() _con[child] _con[child1])if(child1 _con.size() com(_con[child] , _con[child1])){child;}// if(_con[parent] _con[child])if( com(_con[parent] , _con[child]){swap(_con[child] , _con[parent]);child parent;parent 2*child1;}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_queueint,dequeint,lessint pq;pq.push(0);pq.push(1);pq.push(2);pq.push(3);while(!pq.empty()){coutpq.top() ;pq.pop();}
四、容器适配器
1.什么是容器适配器
2.stl中stack和queue的底层结构
3.deque的简单介绍(vector list)
deque(双端队列是一种双开口的“连续”空间的数据结构双开口的含义是可以在头尾两端进行插入删除操作且时间复杂度为O1与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的一些接口简单介绍了什么是容器适配器。
