python网站开发高并发,衡水网站推广公司,做资讯的网站,内部网站做登陆内部链接1. 标准库中的stack
stack 的介绍#xff1a;
1. stack是一种容器适配器#xff0c;专门用在具有后进先出操作的上下文环境中#xff0c;其删除只能从容器的一端进行 元素的插入与提取操作
2. stack是作为容器适配器被实现的#xff0c;容器适配器即是对特定类封装作为其…
1. 标准库中的stack
stack 的介绍
1. stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行 元素的插入与提取操作
2. stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类
a. stack 的使用 注意
如果要访问所有元素得到栈顶元素再pop直到为空 2. stack的模拟实现 代码 namespace lhy
{ templateclass T,class container vectorTclass stack{public:void push(const T x){_t.push_back(x);}void pop(){_t.pop_back();}size_t size(){return _t.size();}bool empty(){return _t.empty();}const T top(){return _t.back();}private:container _t;}; //用法很像缺省参数不过这里缺省的是类型 3. 标准库中的queue
queue 的介绍
1. 队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端提取元素
2. 队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从队尾入队列从队头出队列
3. 底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类 a. queue 的使用 4. queue的模拟实现 代码 namespace lhy
{ templateclass T,class container listTclass queue{public:void push(const T x){_v.push_back(x);}void pop(){_v.pop_front();}bool empty(){return _v.size() 0;}const T back(){return _v.back();}const T front(){return _v.front();}size_t size(){return _v.size();}private:container _v;}; 5. priority_queue 优先级队列
优先级队列的介绍
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构
因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue
注意
默认情况下priority_queue是大堆 a. priority_queue 的使用
priority_queue() (无参构造函数)priority_queue(InputIterator first, InputIterator last)empty() (判空)push() (尾插)pop () 删除栈顶元素即第一个元素top() (返回栈顶元素) 6. priority_queue 的模拟实现 代码 namespace lhy
{templateclass Tstruct less{bool operator()(const T x, const T y){return x y;}};templateclass Tstruct greater{bool operator()(const T x, const T y){return x y;}};templateclass T, class container vectorT, class compare lessTclass priority_queue{private:container con;void AdjustUp(int child){int parent (child - 1) / 2;while (child 0){if (compare()(con[parent], con[child])){std::swap(con[parent], con[child]);}else{break;}child parent;parent (child - 1) / 2;}}void AdjustDown(int parent){int child parent * 2 1;while (child size()){if (child 1 size() con[child] con[child 1]){child;}if (compare()(con[parent], con[child])){std::swap(con[parent], con[child]);}else{break;}parent child;child parent * 2 1;}}public:size_t size(){return con.size();}void push(const T x){con.push_back(x);AdjustUp(size() - 1);}void pop(){swap(con[0], con[size() - 1]);con.pop_back();AdjustDown(0);}bool empty(){return con.empty();}const T top(){return con[0];}};
} 代码注意事项 这两个类实际上又可以说成伪函数这里通过比较大小判断建大堆还是小堆 用法如下 compare()是匿名对象后面接着是调用 less 类 或者 greater 类的运算符重载
