【初阶与进阶C++详解】第十一篇：stack+queue+priority_queue+deque

🏆个人主页：企鹅不叫的博客

​ 🌈专栏

• C语言初阶和进阶
• C项目
• Leetcode刷题
• 初阶数据结构与算法
• C++初阶和进阶
• 《深入理解计算机操作系统》
• 《高质量C/C++编程》
• Linux

⭐️ 博主码云gitee链接：代码仓库地址

⚡若有帮助可以【关注+点赞+收藏】，大家一起进步💙系列文章💙

💙系列文章💙

【初阶与进阶C++详解】第一篇：C++入门知识必备

【初阶与进阶C++详解】第二篇：C&&C++互相调用（创建静态库）并保护加密源文件

【初阶与进阶C++详解】第三篇：类和对象上（类和this指针）

【初阶与进阶C++详解】第四篇：类和对象中（类的六个默认成员函数）

【初阶与进阶C++详解】第五篇：类和对象下（构造+static+友元+内部类

【初阶与进阶C++详解】第六篇：C&C++内存管理（动态内存分布+内存管理+new&delete）

【初阶与进阶C++详解】第七篇：模板初阶（泛型编程+函数模板+类模板+模板特化+模板分离编译）

【初阶与进阶C++详解】第八篇：string类（标准库string类+string类模拟实现）

【初阶与进阶C++详解】第九篇：vector

【初阶与进阶C++详解】第十篇：list

文章目录

💎一、stack和queue使用

🏆1.stack使用

数据结构栈(stack)和队列(queue)介绍

stack()构造空的栈empty()检测stack是否为空size()返回stack中元素的个数top()返回栈顶元素的引用push()将元素val压入stack中pop()将stack中尾部的元素弹出

voidTestatack(){
    stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);while(!s.empty()){
        cout << s.top()<<" ";
        s.pop();}
    cout << endl;}

🏆2.queue使用

queue()构造空的队列empty()检测队列是否为空，是返回true，否则返回falsesize()返回队列中有效元素的个数front()返回队列中有效元素的个数back()返回队列中有效元素的个数push()在队尾将元素val入队列pop()在队尾将元素val入队列

voidTestqueue(){
    queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);while(!q.empty()){
        cout << q.front()<<" ";
        q.pop();}
    cout << endl;}

💎二、容器适配器（deque）

适配器是一种设计模拟，将一个类的接口转化成另一个类的接口

//std::stacktemplate<classT,classContainer= deque<T>>classstack;//std::queuetemplate<classT,classContainer= deque<T>>classqueue;

以上使用了容器适配器，默认使用的是deque。

**deque(双端队列)**：是一种双开口底部总体不连续空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

底层结构不是一段连续的空间，而是由多个小空间组成，相等于一个动态二维数组，但与vector和list相比又会有差异。

deque的优点：

1.相比于vector，deque可以进行头插和头删，且时间复杂度是O(1)，扩容是也不需要大量挪动数据，因此效率是比vector高的。
2.相比于list，deque底层是是连续的空间（单底层不是连续空间），空间利用率高,，也支持随机访问（相比较list而言），但没有vector那么高。
3.总的来说，deque是一种同时具有vector和list两个容器的优点的容器，有一种替代二者的作用，但不是完全替代。

deque的缺点：

1.不适合遍历，因为在遍历是，deque的迭代器要频繁地去检测是否运动到其某段小空间的边界，所以导致效率低下。
2.deque的随机访问的效率是比vector低很多的，实际中，线性结构大多数先考虑vector和list。

💎三、stack和queue模拟实现

🏆1.stack模拟实现

创建一个Container的对象 _con，再借助对象完成封装，默认使用的是deque，其实也可以使用vector

template<classT,classContainer= deque<T>>classstack{public:
        size_t size(){return _con.size();}const T&top(){return _con.back();}voidpush(const T& val){
            _con.push_back(val);}voidpop(){
            _con.pop_back();}boolempty(){return _con.empty();}private:
        Container _con;};

stack使用

voidtest_stack(){
    stack<int, vector<int>> s;

    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);while(!s.empty()){
        cout << s.top()<<" ";
        s.pop();}
    cout << endl;}

🏆2.queue模拟实现

注意：queue不能使用vector作为容器，vector头插效率很低，我们可以用list作为容器

template<classT,classContainer= deque<T>>classqueue{public:voidpush(const T& x){
            _con.push_back(x);}voidpop(){
            _con.pop_front();}const T&front(){return _con.front();}const T&back(){return _con.back();}

        size_t size(){return _con.size();}boolempty(){return _con.empty();}private:
        Container _con;};

queue使用

voidtest_queue(){
    queue<int, list<int>> q;//queue<int, vector<int>> 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介绍和使用

和queue一样都是属于头文件< queue >，底层采用vector容器作为底层数据结构

template<classT,classContainer= vector<T>,classCompare= less<typenameContainer::value_type>>classpriority_queue;

优先级队列就是一个堆，默认是大堆，有关堆知识的传送门

priority_queue()/priority_queue(first, last)构造一个空的优先级队列empty( )检测优先级队列是否为空，是返回true，否则返回 falsetop( )返回优先级队列中最大(最小元素)，即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素，即堆顶元素

voidtest_priority_queue(){
    priority_queue<int, vector<int>> pq;

    pq.push(5);
    pq.push(7);
    pq.push(4);
    pq.push(2);
    pq.push(6);while(!pq.empty()){
        cout << pq.top()<<" ";
        pq.pop();}
    cout << endl;}

🏆2.priority_queue模拟实现

2.1priority_queue框架

模拟实现需要用到堆的知识，C++有关堆的其实有相关函数，传送门

模板中有第三个参数Compare(仿函数，类)，明确优先级队列是升序还是降序的

//优先级队列-大堆(<), 小堆(>)template<classT,classContainer= vector<T>,classCompare= less<T>>//默认是大堆classpriority_queue{public:private:
        Container _con;//利用适配器控制优先级队列};

2.2仿函数

注意，由于仿函数是个类，所以我们在使用时要重载(),使得可以像函数一样使用，仿函数是模板函数，速度比一般函数慢，但本质上简化了代码。

template<classT>//小于structless{booloperator()(const T& x,const T&  y)const{return x < y;}};//大于template<classT>structgreater{booloperator()(const T& x,const T&  y)const{return x > y;}};

仿函数就是用一个类封装一个成员函数operator()，使得这个类的对象可以像函数一样去调用。

less<int> le;
cout <<le(2,3)<< endl;// 该类实例化出的对象可以具有函数行为

库函数中less和greater存放在< functional >头文件中

2.3priority_queue模拟实现

voidAdjustUp(int child){int parent =(child -1)/2;while(child >0){//if (_con[child] > _con[parent])  //<  建小堆  > 建大堆if(_comFunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);
            child = parent;
            parent =(child -1)/2;}else{break;}}}voidAdjustDown(int parent){
    size_t child = parent *2+1;while(child < _con.size()){//if (child+1 < _con.size() && _con[child] < _con[child+1])  if(child +1< _con.size()&&_comFunc(_con[child], _con[child +1])){++child;}//if (_con[parent] < _con[child]) //建大堆if(_comFunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);
            parent = child;
            child = parent *2+1;}else{break;}}}//先将顶部元素和队尾元素交换，在删除队尾元素，在向下调整建立大堆或者小堆voidpop(){assert(!_con.empty());swap(_con[0], _con[_con.size()-1]);
    _con.pop_back();AdjustDown(0);}//先在队尾插入数据，然后向上调整建大堆或者小堆voidpush(const T& x){
    _con.push_back(x);AdjustUp(_con.size()-1);}const T&top(){return _con[0];}

size_t size(){return _con.size();}boolempty(){return _con.empty();}