学校门户网站流程建设方案,长沙网站seo按天计费,免费做网站收录的,企业网站建设人员分析C栈队列优先级队列 1.熟悉stack接口以及使用1.1stack的接口1.2stack的模拟实现1.3stack的一些笔试题 2.熟悉queue接口以及使用2.1queue的接口2.2queue的模拟实现2.3queue的笔试题 3.熟悉priority_queue的接口以及使用#xff08;底层堆#xff09;3.1priority_queue的接口3.2… C栈队列优先级队列 1.熟悉stack接口以及使用1.1stack的接口1.2stack的模拟实现1.3stack的一些笔试题 2.熟悉queue接口以及使用2.1queue的接口2.2queue的模拟实现2.3queue的笔试题 3.熟悉priority_queue的接口以及使用底层堆3.1priority_queue的接口3.2priority_queue的模拟实现3.3priority_queue的笔试题 4.容器适配器4.1deque了解(双端队列)4.1.1deque的优缺点4.1.2为什么选择deque作为stack和queue的底层默认容器 1.熟悉stack接口以及使用
stack的C官方文档
1.1stack的接口
函数说明接口说明stack()构造空的栈empty()检测stack是否为空size()返回stack中元素个数top()返回栈顶元素的引用push()将元素val压入stack中pop()将stack中尾部的元素弹出
1.2stack的模拟实现
//STL下的stack实现
#includedeque
namespace ljh
{templateclass T,class containerstd::dequeTclass stack{stack(){}void push(const T x){_c.push_back(x);}void pop(){_c.pop_back();}T top(){return _c.back();}const T top() const{return _c.back();}size_t size() const{return _c.size();}bool empty() const{return _c.empty();}private:container _c;};
}1.3stack的一些笔试题
最小栈
class MinStack {
public:stackint _st;stackint _minst;MinStack(){}void push(int val){_st.push(val);if(_minst.empty()||val_minst.top()){_minst.push(val);}}void pop(){int val_st.top();_st.pop();if(val_minst.top()){_minst.pop();}}int top(){return _st.top();}int getMin(){return _minst.top();}
};栈的压入、弹出序列
class Solution {
public:bool IsPopOrder(vectorint pushV, vectorint popV){stackint st;size_t pushi0;size_t popi0;while(pushipushV.size()){st.push(pushV[pushi]);while(!st.empty()st.top()popV[popi]){st.pop();popi;}}return st.empty();}
};逆波兰表达式
class Solution {
public:int evalRPN(vectorstring tokens){stackint st;for(auto str:tokens){if(str||str-||str*||str/){int rightst.top();st.pop();int leftst.top();st.pop();switch(str[0]){case :st.push(leftright);break;case -:st.push(left-right);break;case *:st.push(left*right);break;case /:st.push(left/right);break;}}else{st.push(stoi(str));}}return st.top();}
};栈实现队列
class MyQueue {
public:MyQueue(){}void push(int x){_pushst.push(x);}int pop(){int retthis-peek();_popst.pop();return ret;}int peek(){if(_popst.empty()){while(!_pushst.empty()){_popst.push(_pushst.top());_pushst.pop();}}return _popst.top();}bool empty(){return _pushst.empty()_popst.empty();}stackint _pushst;stackint _popst;
};2.熟悉queue接口以及使用
queue的C官方文档
2.1queue的接口
函数声明接口说明queue()构造空的队列empty()检测队列是否为空是返回true否则返回falsesize()返回队列中有效元素的个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素val入队列pop()将队头元素出队列
2.2queue的模拟实现
//STL下queue的实现
#includequeue
#includelist
namespace ljh
{templateclass T,class containerstd::dequeT//templateclass T,class containerstd::listTclass queue{public:queue(){}void push(const T x){_c.push_back(x);}void pop(){_c.pop_front();}T back(){return _c.back();}const T back()const{return _c.back();}T front(){return _c.front();}const T front()const{return _c.front();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:container _c;};
}2.3queue的笔试题
队列实现栈
class MyStack {
public:MyStack(){}void push(int x){if(!q1.empty()){q1.push(x);}else{q2.push(x);}}int pop(){if(!q1.empty()){while(q1.size()1){q2.push(q1.front());q1.pop();}int retq1.front();q1.pop();return ret;}else{while(q2.size()1){q1.push(q2.front());q2.pop();}int retq2.front();q2.pop();return ret;}}int top(){if(!q1.empty()){return q1.back();}else{return q2.back();}}bool empty(){return q1.empty()q2.empty();}queueint q1;queueint q2;
};3.熟悉priority_queue的接口以及使用底层堆
priority_queueC官方文档 以下稍微看看就行
优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空 size()返回容器中有效元素个数 front()返回容器中第一个元素的引用 push_back()在容器尾部插入元素标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指 定容器类则使用vector。需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作
3.1priority_queue的接口
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成 堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意 默认情况下priority_queue是大堆。
函数声明接口说明priority_queue()/priority_queue(first,last)构造一个空的优先级队列和迭代器区间构造的优先级队列empty()检测优先级队列是否为空是返回true否则返回falsetop()返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素
注意
默认情况下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(v.begin(),v.end());cout q1.top() endl;// 如果要创建小堆将第三个模板参数换成greater比较方式priority_queueint, vectorint, greaterint q2(v.begin(), v.end());cout q2.top() endl;
}如果在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;
}3.2priority_queue的模拟实现
#pragma once
#includeiostream
using namespace std;#includevector
//priority_queue-堆
namespace ljh
{templateclass Tstruct less{bool operator()(const T left, const T right){return left right;}};templateclass Tstruct greater{bool operator()(const T left, const T right){return left right;}};templateclass T,class Containerstd::vectorT,class ComparelessTclass priority_queue{public:priority_queue(){}templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last):_con(first, last){for (int i (_con.size() - 2) / 2;i 0;i--){adjust_down(i);}}void adjust_up(int child){Compare com;int parent (child - 1) / 2;while (child 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void adjust_down(int parent){Compare com;size_t child parent * 2 1;while (child _con.size()){if (child 1 _con.size() com(_con[child], _con[child 1])){child;}if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent child;child child * 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);}const T top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}3.3priority_queue的笔试题
数组中第k个最大元素
class Solution {
public:int findKthLargest(vectorint nums, int k){priority_queueint q(nums.begin(),nums.end());while(--k){q.pop();}return q.top();}
};4.容器适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结) 将一个类的接口转换成客户希望的另外一个接口。
实际上STL标准库中stack和queue是容器适配器
4.1deque了解(双端队列)
deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和 删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比 较高。 如果说中控数组满了则需要扩容但扩容的代价低
中间位置插入删除数据是整体挪动数据还是对单个buff数组扩容实际上两种都行第一种的buff是一样大则[]访问会快很多 整体挪动优势: xi/10 确认在第几个buff yi%10 确认在这个buff数组的第几个位置 劣势挪动数据代价大
单个buff数组扩容优势 扩容代价小 劣势数组访问[]比较麻烦
4.1.1deque的优缺点
优点 与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不 需要搬移大量的元素 与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。
缺点不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构。
4.1.2为什么选择deque作为stack和queue的底层默认容器
stack是一种后进先出的特殊线性数据结构因此只要具有push_back()和pop_back()操作的线性结构都可以作为stack的底层容器比如vector和list都可以queue是先进先出的特殊线性数据结构只要具有push_back和pop_front操作的线性结构都可以作为queue的底层容器比如list。 但是STL中对stack和queue默认选择deque作为其底层容器主要是因为
stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。在stack中元素增长时deque比vector的效率高(扩容时不需要搬移大量数据)queue中的元素增长 时deque不仅效率高而且内存使用率高。
