天津创思佳网络网站制作公司,哪些网站可以接设计的单子做,张家港网站建设价格,wordpress关闭google字体这一节主要学习stack、quene和priority_quene的使用以及模拟实现#xff0c;最后介绍了容器适配器。 目录
stack的介绍和使用
stack的介绍
stack的使用
stack的模拟实现
queue的介绍和使用
queue的介绍
queue的使用
queue的模拟实现
priority_queue的介绍和使用
pri… 这一节主要学习stack、quene和priority_quene的使用以及模拟实现最后介绍了容器适配器。 目录
stack的介绍和使用
stack的介绍
stack的使用
stack的模拟实现
queue的介绍和使用
queue的介绍
queue的使用
queue的模拟实现
priority_queue的介绍和使用
priority_queue的介绍
priority_queue的使用
priority_quene的模拟实现
容器适配器
STL标准库中stack和queue的底层结构 stack的介绍和使用
stack的介绍 1.stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。 2.stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。 3.stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下操作 empty判空操作 back获取尾部元素操作 push_back尾部插入元素操作 pop_back尾部删除元素操作 4.标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器默认情况下使用deque。 stack的使用 stack()构造空的栈 empty()检测stack是否为空 size()返回stack中元素的个数 top()返回栈顶元素的引用 push()将元素val压入stack中 pop()将stack中尾部的元素弹出 stack的模拟实现
namespace ghs
{//适配器模式//stack(int,vectorint) st1//stack(int,listint) st2//templateclass T,class Container vectorT//添加缺省值和库保持一致templateclass T, class Container dequeTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T top(){return _con.back();}private:Container _con;};
}
queue的介绍和使用
queue的介绍 1.队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端提取元素。 2.队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从队尾入队列从队头出队列。 3.底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty()检测stack是否为空 size()返回stack中元素的个数 front()返回队头元素的引用 back()返回队尾元素的引用 push_back()在队列尾部入队列 pop_front()在队列头部出队列 4.标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标准容器deque。 queue的使用 quene()构造空的队列 empty()检测队列是否为空 size()返回stack中元素的个数 front()返回队头元素的引用 back()返回队尾元素的引用 push()在队尾将元素val入队列 pop()将队头元素出队列 queue的模拟实现
因为queue的接口中存在头删和尾插因此使用vector来封装效率太低故可以借助list来模拟实现queue具体如下
namespace ghs
{//适配器模式templateclass T, class Container dequeTclass quene{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T front(){return _con.front();}const T back(){return _con.back();}private:Container _con;};
}
priority_queue的介绍和使用
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来自动完成此操作。 priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意默认情况下priority_queue是大堆。 priority quene()/priority_quene(first,last)构造一个空的优先级队列 empty()检测优先级队列是否为空 top()返回优先级队列中最大最小元素即堆顶元素 push()在优先级队列中插入元素x pop()删除优先级队列中的最大最小元素即堆顶元素 【注意】
1.默认情况下priority_queue是大堆。
#include vector
#include queue
#include functional // greater算法的头文件
void TestPriorityQueue()
{// 默认情况下创建的是大堆其底层按照小于号比较vectorint v{3,2,7,6,0,4,1,9,8,5};priority_queueint q1;for (auto e : v)q1.push(e);cout q1.top() endl;// 如果要创建小堆将第三个模板参数换成greater比较方式priority_queueint, vectorint, greaterint q2(v.begin(), v.end());cout q2.top() endl;
}
2. 如果在priority_queue中放自定义类型的数据用户需要在自定义类型中提供 或者 的重载。
class Date
{
public:Date(int year 1900, int month 1, int day 1): _year(year), _month(month), _day(day){}bool operator(const Date d)const{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);}bool operator(const Date d)const{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);}friend ostream operator(ostream _cout, const Date d){_cout d._year - d._month - d._day;return _cout;}
private:int _year;int _month;int _day;
};
void TestPriorityQueue()
{// 大堆需要用户在自定义类型中提供的重载priority_queueDate q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout q1.top() endl;// 如果要创建小堆需要用户提供的重载priority_queueDate, vectorDate, greaterDate q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout q2.top() endl;
}
priority_quene的模拟实现
namespace ghs
{templateclass Tclass Less{public:bool operator()(const T x, const T y){return x y;}};templateclass Tclass Greater{public:bool operator()(const T x, const T y){return x y;}};//templateclass T,class Container vectorT//大堆templateclass T, class Container vectorT,class Compare LessTclass priority_quene{ public:void adjust_up(size_t child){Compare com;size_t parent (child - 1) / 2;while (child 0){if (com(_con[parent] , _con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){Compare com;int child parent * 2 1;while (child _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 (com(_con[parent] , _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}void push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T top(){return _con[0];}private:Container _con;};}
容器适配器
STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为stack和队列只是对其他容器的接口进行了包装STL中stack和queue默认使用deque比如
