如何建立和设计公司网站作文,免费做app,小程序推广方式,长沙做网站大概多少钱[本节目标] 1. stack的介绍和使用 2. queue的介绍和使用 3. priority_queue的介绍和使用 4. 容器适配器 1. stack的介绍和使用
1.1 stack的介绍 1. stack是一种容器适配器#xff0c;专门用在具有后进先出操作的上下文环境中#xff0c;其删除只能从容器的一端进行元素的…[本节目标] 1. stack的介绍和使用 2. queue的介绍和使用 3. priority_queue的介绍和使用 4. 容器适配器 1. stack的介绍和使用
1.1 stack的介绍 1. stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。 2. stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。 3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下 操作 empty判空操作back获取尾部元素操作push_back尾部插入元素操作pop_back尾部删除元素操作 4. 标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器 默认情况下使用deque。 1.2 stack的使用
函数说明 接口说明stack() 构造空的栈 empty() 检测stack是否为空 size() 返回stack中元素的个数 top() 返回栈顶元素的引用 push() 将元素val压入stack中 pop() 将stack中尾部的元素弹出
1.3 stack题目的练习
155. 最小栈 - 力扣LeetCode 我们来看看这个题目的解题思路我们首先来看一种错误的解题方法看看它为什么错误。
错误思路将数组中的值依次入栈此时定义一个变量min去记录最小值当入栈的值比min小更新min的值。 我们来看看这个思路为什么错误如果栈中途没有元素出栈那么这个思路完全正确因为入栈的过程相当于把这个栈遍历了一遍此时就可以找到最小值可是当我们有元素出栈呢我们看看上面的图片此时已经找到最小值了3可是随后3出栈了但是此时的min该如何变化呢此时找min就需要再遍历一次栈所以这个思路是行不通的。
正确思路建立两个栈一个普通栈正常入数据另外一个最小栈入栈最小值当普通栈为空的时候此时该值就直接入最小栈当普通栈入栈的数据大于上次最小值入栈的值时此时再次将上次的最小值入最小栈当普通栈入栈的数据小于上次最小值入栈的值时此时将这个小值入最小栈如果要取出最小值的时候只需要取最小栈的栈顶值即可。 我们能不能再进一步优化呢我们上面的最小栈没必要存储那么多的元素5当普通栈栈顶元素 最小栈栈顶元素的时候此时就不需要入栈但是普通栈栈顶元素 最小栈栈顶元素的时候我们需要入最小栈。 解题代码
class MinStack {
public:MinStack() {//这里可以不用写//自定义类型会去调用自己的默认构造}void push(int val) {st.push(val);if(minst.empty() || st.top() minst.top()){minst.push(val);}}void pop() {if(st.top() minst.top()) minst.pop();st.pop();}int top() {return st.top();}int getMin() {return minst.top();}stackint st;stackint minst;
};
此时面试官又会提一个问题如果入普通栈的数据全部都是3呢按照我们上面的逻辑此时最小栈也要全部存3那么我们上面的优化就相当于没有优化此时我可以通过计数器来解决当普通栈有多个相同值时此时最小栈入栈还可以存储一个计数器每次入最小栈的时候count栈每次pop的时候只需要--count当减到0的时候就可以删除3。
栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com) 解题思路题目要我们判断两个序列是否符合入栈出栈的次序我们就可以用一个栈来模拟。对于入栈序列我们让它入栈只要栈为空序列肯定要依次入栈。那什么时候出来呢自然是遇到一个元素等于当前的出栈序列的元素那我们就放弃入栈让它先出来。
强调一下我们这里不是拿的入栈序列和出栈序列依次比较而是构建一个辅助栈让的入栈序列再次入栈然后再比较的因为我们是想判断出栈顺序是否匹配且中途有元素出栈所以需要入栈序列入栈来模拟出栈过程。 具体做法
step 1准备一个辅助栈st两个下标curpush和curpop分别访问两个序列。step 2辅助栈st为空或者栈顶不等于出栈数组当前元素就持续将入栈数组加入栈中。step 3辅助栈st不为空并且栈顶等于出栈数组当前元素就出栈。step 4当入栈数组访问完出栈数组无法依次弹出就是不匹配的否则两个序列都访问完就是匹配的。
bool IsPopOrder(vectorint pushV, vectorint popV) {stackint st;int curpush 0;int curpop 0;while(curpush pushV.size()){//栈为空或者栈顶元素不等于出栈数组当前元素,直接入栈st.push(pushV[curpush]);//这里需要写成while,因为可能会有多次匹配//当栈为空时就不需要再出栈了while(!st.empty() st.top() popV[curpop]){st.pop();curpop;}} //根据出栈序列的下标即可判断是否匹配return curpop popV.size();
}
150. 逆波兰表达式求值 - 力扣LeetCode 逆波兰式是一种数学表达式的表示方法也称为后缀表达式。与传统的中缀表达式不同逆波兰式将操作符置于操作数的后面从而无需使用括号来指定运算顺序。 在逆波兰式中每个运算符都紧跟在其相关的操作数之后。例如中缀表达式 (2 1) * 3 在逆波兰式中表示为 2 1 3 * 。计算逆波兰式时从左到右扫描表达式遇到操作数就将其压入栈中遇到操作符就从栈中弹出相应数量的操作数进行运算并将结果压回栈中。最终栈中的唯一元素即为整个表达式的结果。 逆波兰式的优势在于不需要考虑运算符优先级和括号的使用使得计算机能够更容易地处理和解析数学表达式。这种表示方法在计算器和编程语言中得到广泛应用。 解题思路
使用一个栈存储操作数从左到右遍历逆波兰表达式进行如下操作
step 1如果遇到操作数则将操作数入栈step 2如果遇到运算符则将两个操作数出栈其中先出栈的是右操作数后出栈的是左操作数使用运算符对两个操作数进行运算将运算得到的新操作数入栈。step 3整个逆波兰表达式遍历完毕之后栈内只有一个元素该元素即为逆波兰表达式的值。 代码实现
class Solution {
public:int evalRPN(vectorstring tokens) {stackint st;int right 0;int left 0;for(auto e : tokens){if(e || e - || e * || e /){right st.top();st.pop();left st.top();st.pop();switch(e[0])//返回的char类型{case :st.push(left right);break;case -:st.push(left - right);break;case *:st.push(left * right);break;case /://题目明确不发生为除数为0清空st.push(left / right);break;}}else{//转为数字st.push(stoi(e));}} return st.top();}
};
这道题目只要清除栈的规则很容易做出来因为题目已经把后缀表达式给我们了导致题目非常容易如果这道题给我们的是中缀表达式呢我们就需要先转为后缀表达式然后再按照上述步骤进行计算转话的步骤也需要栈来完成。
step 1如果遇到操作数则将操作数输出step 2如果遇到运算符栈为空操作符入栈当前操作符比栈顶的操作符优先级高操作符也入栈。step 3如果遇到运算符操作符比栈顶的操作符优先级低或者相等代表栈定的操作符可以运算了出栈顶操作符
可是带括号呢
step 1如果遇到操作数则将操作数输出step 2如果遇到运算符栈为空操作符入栈当前操作符比栈顶的操作符优先级高操作符也入栈。step 3如果遇到运算符操作符比栈顶的操作符优先级低或者相等代表栈定的操作符可以运算了出栈顶操作符step4如果遇到运算符是括号找到左括号和右括号的位置然后让这段区间重复上面的step1- step3过程也就是递归如果当前元素是左括号则递归处理括号内的子表达式将子表达式的后缀形式输出到后缀表达式。如果当前元素是右括号则返回上一级递归。 这里就不实现了仅仅为本题的扩展。
1.4 stack的模拟实现
我们先来看一下我们传统的栈的写法。
namespace yu
{templateclass Tclass stack{public:push(const T x){//...}private:T* _a;size_t _top;size_t _capacity;};
}
但是从栈的接口中可以看出栈实际是一种特殊的vector因此使用vector完全可以模拟实现stack。
namespace yu
{//新增一个模板参数templateclass T, class Contanierclass stack{public://元素入栈void push(const T x){_con.push_back(x);}//元素出栈void pop() { _con.pop_back(); }//普通栈 返回栈顶元素T top() { return _con.back(); }//const栈 返回栈顶元素const T top()const { return _con.back(); }//返回栈内元素的个数size_t size()const { return _con.size();}//判断栈是否为空bool empty()const { return _con.empty();}private:Contaner _con;};
}
我们上面stack的模拟实现新增了一个模板它是一个容器容器这个概念对于我们来说并不陌生我们之前就已经学过vector和list容器了那是不是意味着这里需要传容器呢比如vectorint然后里面_con的类型就是vectorint里面的尾插尾删等其他函数就会调用vector的尾插尾删等其他函数这样就轻松的实现了我们的stack我们来测试一下。
int main()
{yu::stackint, vectorint st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (!st.empty()){cout st.top() ; st.pop();}cout endl;return 0;
}
运行结果 我们发现使用将vector容器传入就可以直接模实现拟栈并且也能符合栈的先进后出的特点。如果我们传入的容器是list呢
int main()
{yu::stackint, listint st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (!st.empty()){cout st.top() ; st.pop();}cout endl;return 0;
} 运行结果 我们发现此时也能实现栈并且也能符合出栈的先进后出的特点。并且我们上面的stack还不用写构造函数因为_con是自定义类型如果我们没显示的写构造函数自定义类型会去调用它自己的构造函数去初始化比如传入的容器时vector那么就会去调用vector的构造函数。不过需要注意一下如果我们传入的容器没有尾插、尾删等函数那么模拟实现的栈就会报错啦但是我们发现库里面的stack的模拟实现容器给是缺省值但缺省值不是vectorint也不是我们的listint而是dequeint。 deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。deque它包含了vector和list的功能同时还综合了vector和list的优点我们后面的会介绍这里我们先来使用它。
#include stack.h
#include deque
#include stackint main()
{//stackint, dequeint st;//这里也可以不用传入dequeint//因为库里面实现是dequeint作为缺省值//但是我们自己实现的需要带上//如果我们也不想带呢?用下面的语句//templateclass T, class Container dequeTyu::stackint, dequeint st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (!st.empty()){cout st.top() ; st.pop();}cout endl;return 0;
} 运行结果 2. queue的介绍和使用
2.1 queue的介绍 1. 队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端 提取元素。 2. 队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列从队头出队列。 3. 底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操 作: empty检测队列是否为空size返回队列中有效元素的个数front返回队头元素的引用back返回队尾元素的引用push_back在队列尾部入队列pop_front在队列头部出队列 4. 标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标准容器deque。 2.2 queue的使用
函数声明 接口说明 queue() 构造空的队列 empty() 检测队列是否为空是返回true否则返回false size() 返回队列中有效元素的个数 front() 返回队头元素的引用 back() 返回队尾元素的引用 push() 在队尾将元素val入队列 pop() 将队头元素出队列
2.3 queue题目的练习
225. 用队列实现栈 - 力扣LeetCode 102. 二叉树的层序遍历 - 力扣LeetCode 这个题目初看很简单但是题目的要求逐层遍历所有结点即在输出的时候我们必须要知道那个数字是那一个层的。
2.4 queue的模拟实现
有了之前的stack我们这里实现queue就非常简单. namespace yu
{templateclass T,class Container 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();}//返回队列内元素的个数size_t size()const{return _con.size();}//判断队列是否为空bool empty()const{return _con.empty();}private:Contaner _con;};
}
然后我们来测试一下
int main()
{yu::queueint, dequeint q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);while (!q.empty()){cout q.front() ;q.pop();}cout endl;return 0;
}
运行结果 同样的我们这里给上list容器都能是实现队列的先进进出的特点但是vector却不行因为vector没有pop_front接口所以会报错但是我们这里可以使用erase接口但是由于队列是出队头数据而vector的erase头删效率比较低需要挪动数据故一般很少传入vector容器去适配。
3. priority_queue的介绍和使用
3.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来自动完成此操作。 3.2 priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成 堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意 默认情况下priority_queue是大堆。
默认情况下priority_queue是大堆。 #include iostream
#include vector
#include queue
#include functional // greater算法的头文件using namespace std;void TestPriorityQueue()
{// 默认情况下创建的是大堆其底层按照小于号比较vectorint v{ 3,2,7,6,0,4,1,9,8,5 };priority_queueint q1;for (auto e : v)q1.push(e);while (!q1.empty()){cout q1.top() ;//建大堆每次取堆顶数据降序q1.pop();}cout endl;// 如果要创建小堆将第三个模板参数换成greater比较方式priority_queueint, vectorint, greaterint q2(v.begin(), v.end());while (!q2.empty()){cout q2.top() ;//建小堆每次取堆顶数据升序q2.pop();}
}int main()
{TestPriorityQueue();return 0;
}
运行结果 3.3 priority_queue题目的练习
215. 数组中的第K个最大元素 - 力扣LeetCode 思路一利用算法库的sort进行降序排序然后再通过下标[]直接返回元素。
class Solution {
public:int findKthLargest(vectorint nums, int k) {sort(nums.begin(),nums.end(),greaterint());return nums[k-1];}
};
这里要提一点之前的priority_queue我们想建小堆传入的参数是priority_queueint, vectorint, greaterint q2而这里sort排序却是sort(nums.begin(),nums.end(),greaterint())sort这里还多一个()为什么呢
我们上面的程序虽然能运行但是不符合题目要求我们的一个排序时间复杂度就是O(N*logN)。
思路二通过建大堆 pop掉前k个数据此时堆顶的数据就是第K个大的数据
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint pq(nums.begin(),nums.end());//大堆while(--k)//循环k-1次{pq.pop();//把前k-1最大的数据pop掉}return pq.top();}
}; 构建堆 使用 priority_queue 构建堆的时间复杂度为 O(n)其中 n 是数组 nums 的长度。 循环 k-1 次的 pop 操作 这一部分的时间复杂度为 O(k * log(n))因为每次 pop 操作都涉及到对堆的调整而每次调整的时间复杂度是堆的高度即 log(n)。
总的时间复杂度为 O(n k * log(n))。
需要注意的是当 k 远小于 n 时时间复杂度为 O(n)即构建堆的时间。当 k 较大时可能需要进行多次的 pop 操作对应的时间复杂度为 O(k * log(n))此时就接近O(n * log(n))。
思路三如果N和K非常大利用TopK解决问题前k个数据建小堆当有数据大于堆顶然后pop堆顶数据大于的那个数据入堆最后走完堆顶的数就是第K个大的数。
class Solution {
public:int findKthLargest(vectorint nums, int k) {//左闭右开,前k个数据建小堆,包括第k个数据priority_queueint, vectorint, greaterint pq(nums.begin(),nums.begin() k);for(int i k;i nums.size(); i){if(nums[i] pq.top()){pq.pop();pq.push(nums[i]);}}return pq.top();}
}; 构建小顶堆 使用小顶堆的构建时间复杂度为 O(k)其中 k 是输入参数。 遍历数组 从第 k 个元素开始遍历数组并在小顶堆中维护前 k 个最大的元素。这一部分的时间复杂度为 O((n - k) * log(k))其中 n 是数组 nums 的长度。
总的时间复杂度为 O(k (n - k) * log(k))。此时就能完美接近O(n)。当k远小于n此时时间复杂度就是O(n)当k很大n - k此时也就可以忽略不计此时时间复杂度就是O(logk)。但是呢如果k是n的一半此时效率也就不太行。
3.4 priority_queue的模拟实现
通过对priority_queue的底层结构就是堆因此此处只需对对进行通用的封装即可。 这里容器给的缺省值是vectorint并没有给我们的dequeint说明dequeint也是有缺点的至于缺点是啥我们后面会提到。这里priority默认实现的是大堆因此我们也先来实现一下大堆。
我们这里的堆插入逻辑是尾插然后再向上调整注意这里不能头擦向下调整因为头插后父子之间的关系就不对了并且此时不满足向下调整的前提左右子树是堆。 堆的删除逻辑是
将堆顶元素与堆中最后一个元素进行交换。删除堆中最后一个元素。将堆顶元素向下调整到满足堆特性为止。向下调整的结束条件是child等于叶子结点。 namespace yu
{templateclass T,class Container vectorTclass priority_queue{public:void adjust_up(int child){int parent (child - 1) / 2;while (child 0){if (_con[parent] _con[child]){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}void adjust_down(int parent){int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child] _con[child 1]){child child 1;}if (_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);}const T top(){return _con[0];}//返回堆内元素的个数size_t size()const{return _con.size();}//判断堆是否为空bool empty()const{return _con.empty();}private:Container _con;};
}
我们来测试一下
int main()
{yu::priority_queueint q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);while (!q.empty()){cout q.top() ;q.pop();}cout endl;return 0;
}
运行结果 如果是小堆呢我们就要修改上面的代码。
namespace yu
{templateclass T,class Container vectorTclass priority_queue{public:void adjust_up(int child){int parent (child - 1) / 2;while (child 0){if (_con[parent] _con[child]){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}void adjust_down(int parent){int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child] _con[child 1]){child child 1;}if (_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);}const T top(){return _con[0];}//返回堆内元素的个数size_t size()const{return _con.size();}//判断堆是否为空bool empty()const{return _con.empty();}private:Container _con;};
}
运行结果 注意我们这里不能使用list去适配因为list不支持[ ]去访问元素而我们堆需要大量的[ ]去访问元素我们上面通过修改堆里面的代码去实现大小堆的切换但是这样的做法很不好有的使用者如果不清楚堆的逻辑就不知道怎么去修改我们应该提供一个方法传递大于就是大堆小于就是小堆能完成大小堆的切换而不是通过去修改堆的代码c语言一般通过函数指针 回调函数去解决但是比较复杂C就通过仿函数/函数对象解决。
//仿函数/函数对象
namespace yu
{class less{public:bool operator()(int x, int y){return x y;}};
}
int main()
{yu::less lessFunc;cout lessFunc.operator()(1, 2) endl;//运算符重载cout lessFunc(2, 1) endl;//有点像函数调用 - 仿函数//lessFunc像函数名 - 实际上是一个对象 - 函数对象return 0;
}
运行结果 然后我们再来看一下函数指针的缺陷
bool lessfunc(int x, int y)
{return x y;
}
bool greaterfunc(int x, int y)
{return x y;
}
// A这个类要回调lessfunc
//构成函数的函数指针是一个对象不能在类模板的参数传递
//函数指针只能通过函数传递光有类型还不够我们要找到指针指向的函数
class A
{
public:A(bool(*pf)(int, int)):_pf(pf){}void func(int x, int y){cout _pf(x, y) endl;;}
private:bool(*_pf)(int, int);//类型为bool(*)(int,int)变量名为pf
};int main()
{yu::less lessFunc;cout lessFunc.operator()(1, 2) endl;//运算符重载cout lessFunc(2, 1) endl;//有点像函数调用 - 仿函数//lessFunc像函数名 - 实际上是一个对象 - 函数对象//函数指针A aa1(lessfunc);aa1.func(1, 2);A aa2(greaterfunc);aa2.func(1, 2);return 0;
}
函数指针的类型比较复杂并且函数指针只能通过函数参数传递比较复杂我们来看一下仿函数实现回调呢
//仿函数/函数对象
namespace yu
{class less{public:bool operator()(int x, int y){return x y;}};
}
//仿函数/函数对象
namespace yu
{class greater{public:bool operator()(int x, int y){return x y;}};
}templateclass T, class Compare
class A
{
public:void func(const T x, const T y){Compare com;cout com(x, y) endl;;}
};int main()
{Aint, yu::less aa1;aa1.func(1, 2);Aint, yu::greater aa2;aa2.func(1, 2);return 0;
}
这样通过一个仿函数就也实现了类似函数指针的功能并且实现更简单。所以我们现在也要实现一个仿函数能让我们的堆结构实现大小堆的切换。
namespace yu
{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,class Compare yu::lessTclass priority_queue{public:void adjust_up(int child){int parent (child - 1) / 2;while (child 0){//这里的less是默认建大堆 - 使用小于//if (_con[parent] _con[child])//com是less类的对象可以调用内部成员函数if (com(_con[parent],_con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}void adjust_down(int parent){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 child 1;}//if (_con[parent] _con[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);}const T top(){return _con[0];}//返回堆内元素的个数size_t size()const{return _con.size();}//判断堆是否为空bool empty()const{return _con.empty();}private:Container _con;Compare _com;//实现比较};
}
我们来测试一下
int main()
{yu::priority_queueint,vectorint, yu::lessint q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);q1.push(5);while (!q1.empty()){cout q1.top() ;q1.pop();}cout endl;yu::priority_queueint, vectorint, yu::greaterint q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);while (!q.empty()){cout q.top() ;q.pop();}cout endl;return 0;
}
运行结果 我们再来看一下这张图 priority_queue是只能传递仿函数如果也传入函数指针类型的话它就找不到那个要回调的函数而sort里面的不仅可以传入仿函数对象还可以传入函数指针不仅能推导出函数指针的类型同时还拿到了指向要回调函数的指针。
4. 容器适配器
4.1 什么是适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结)该种模式是将一个类的接口转换成客户希望的另外一个接口。 适配器的本质就是封装复用
4.2 STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为stack和队列只是对其他容器的接口进行了包装STL中stack和queue默认使用deque比如 为什么stack和queue都使用我们的deque去做适配器而priority_queue却选择我们的verctor去做适配器这里我们就需要了解一下deque容器。
4.3 deque的简单介绍(了解)
我们首先来看一下vector和list的优缺点 而deque的功能既包括了vector和list同时还具有vector和list的优点两者兼得
4.3.1 deque的原理介绍
deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。 deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组其底层结构如下图所示 双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问的假象落在了deque的迭代器身上因此deque的迭代器设计就比较复杂如下图所示 那deque是如何借助其迭代器维护其假想连续的结构呢 那deque如何尾插和头插呢如果cur不等于last就可以直接插入数据如果cur等于last就表示buff已经满了此时就需要新开一个buff让finish指向新开的buff通过node找到这个新开的位置直接插入即可。如果是头插呢也是新开一个buff然后修改start中的node指针指向中控位置再让cur指向插入的数据first指向新开buff的开始last指向新开buff的结束。 那如何判断第一个buff是不是从头开始的呢如果是从头开始那么cur一定是和first是相等的。我们再来看一下迭代器如何遍历。cur里面存入的是数据在一个buff中我们只需要让cur如果不等于last就可以遍历到这一个buff里面的全部数据当这个buff遍历完让node找到下一个buff继续遍历数据。我们开一下源码里面的迭代器。 4.3.2 deque的缺陷
与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是必vector高的。
与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。
但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到 某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构 时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作 为stack和queue的底层数据结构。
结论 1.deque下标随机访问效率不错但是和vector仍有差距。2.deque中间插入删除效率较差。使用场景大量头插头删尾插尾删deque大量下标访问元素vector大量中间插入list 4.4 为什么选择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的优点而完美的避开了其缺陷。
