【C++/STL】stack和queue(容器适配器、优先队列、双端队列)-阿里云开发者社区

stack的介绍

stack是一种容器适配器。

stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素。

stack的底层容器应该支持以下操作：empty 、back、push_back、pop_back

标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

stack常用接口

queue的介绍

队列是一种容器适配器。

底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty，size，front，back，push_back，pop_front。

标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。（vector不满足，因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低）

queue的使用

容器适配器

什么是适配器

适配器是一种设计模式，该种模式是将一个类的接口转换成客户希望的另外一个接口。

STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque。

deque的简单介绍

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

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。

deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素。
与list比较，其底层是连续空间，空间利用率比较高。
在实际中，需要线性结构时，大多数情况下优先考虑vector和list，目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

STL的六大组件

模拟实现

stack

queue

stack和queue的模拟实现基本一样。

优先队列

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

常用接口

简单使用

我们插入时，是乱序插入的，取出来却是降序的。因为优先队列默认是大堆，不过它并没有在里面进行排序，它在里面依旧是乱序的，只是取出来的是堆顶，是最大的。

如果我们想让他是小堆，就得改一下他的仿函数。

sort函数排序

sort排序默认是升序，想要降序就得改仿函数。注意这里是函数模板，要传对象，所以有括号。而优先队列那里没有括号，是因为那里是类模板。

在C语言中，我们排序如果要控制升序降序，传的是函数指针。而这里我们传的是仿函数。

上方是仿函数的简单模拟。

模拟实现(简单版)

    template<class T,class Container=vector<T>>
    class priority_queue
    {
    public:
        void adjust_up(size_t child)
        {
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (_con[child] > _con[parent])
                {
                    swap(_con[child], _con[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }
 
        void push(const T& x)
        {
            _con.push_back(x);
            adjust_up(_con.size() - 1);
        }
 
        void adjust_down(size_t parent)
        {
            size_t child = parent * 2 + 1;
            while (child<_con.size()) 
            {
                if (child + 1 < _con.size() && _con[child + 1] > _con[child])
                {
                    ++child;
                }
 
                if (_con[child] > _con[parent])
                {
                    swap(_con[child], _con[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }
 
        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;
    };

上面是默认的大堆。如果想要它是小堆，要怎么办呢?

如下图修改：

这样做的优势是，我们只需要传不同的仿函数即可修改为升序或者降序。不传默认是大堆。

自定义类型

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

上面是日期类，Date类型，比较时，只需要重载运算符即可。如果我们传的是Date*又该怎么办呢？

可以看到，第二行每次的结果都是不一样的。空间并不一定越晚开，地址就越高。这里不能通过重载运算符解决，因为重载必须包含自定义类型，而指针是内置类型。解决方法是：专门写一个仿函数。

从这个样例可以得出，仿函数不仅可以控制比较逻辑，还可以控制如何比较。

测试完整代码

queue.h

#pragma once
#include<deque>
 
namespace qjh
{
    template<class T, class Container = deque<T>> //有了Container就可以根据需要实现链式栈或数组栈了
    class queue
    {
    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;
    };
 
    template<class T>
    struct less
    {
        bool operator()(const T& x, const T& y)
        {
            return x < y;
        }
    };
 
    template<class T>
    struct greater
    {
        bool operator()(const T& x, const T& y)
        {
            return x > y;
        }
    };
 
    //大堆
    template<class T,class Container=vector<T>,class Compare=less<T>>
    class priority_queue
    {
    public:
        void adjust_up(size_t child)
        {
            Compare com; 
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                //if (_con[child] > _con[parent])
                //if (_con[parent]<_con[child] )
                if (com(_con[parent] , _con[child]))
                {   
                    swap(_con[child], _con[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }
 
        void push(const T& x)
        { 
            _con.push_back(x);
            adjust_up(_con.size() - 1);
        }
 
        void adjust_down(size_t parent)
        {
            Compare com;
            size_t child = parent * 2 + 1;
            while (child<_con.size()) 
            {
                //if (child + 1 < _con.size() && _con[child + 1] > _con[child])
                //if (child + 1 < _con.size() && _con[child]<_con[child + 1] )
                if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))              
                {
                    ++child;
                }
 
                //if (_con[child] > _con[parent])
                //if ( _con[parent]< _con[child])
                if (com(_con[parent] , _con[child]))
                {
                    swap(_con[child], _con[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }
 
        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;
    };
}

stack.h

#pragma once
#include<vector>
#include<list>
#include<deque>
 
namespace qjh
{
 
    //设计模式
    //适配器模式--转换
    //stack<int,vector<int>> st1;
    //stack<int,list<int>> st2;
    template<class T,class Container=deque<T>> //有了Container就可以根据需要实现链式栈或数组栈了
    class 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;
    };
}

test.cpp

#include<iostream>
using namespace std;
 
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include"stack.h"
#include"queue.h"   
 
void test_queue1()
{
    qjh::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;
}
 
 
void test_stack1()
{
    qjh::stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
 
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
}
 
void test_priority_queue1()
{
    //默认大的优先级高，底层是大堆
    //priority_queue<int> pq;
 
    //大堆
    //qjh::priority_queue<int> pq; //类模板，传类型 
    //小堆
    qjh::priority_queue<int,vector<int>,greater<int>> pq; //类模板，传类型 
 
    pq.push(2);
    pq.push(1);
    pq.push(4);
    pq.push(3);
    pq.push(7);
    pq.push(8);
 
 
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
 
    //vector<int> v = { 3,1,7,4,6,3 };
    默认升序
    //sort(v.begin(), v.end());
    //for (auto e : v)
    //{
    //  cout << e << " ";
    //}
    //cout << endl;
 
    降序
 
    //sort(v.begin(), v.end(),greater<int>()); //匿名对象，函数模板
    //for (auto e : v)
    //{
    //  cout << e << " ";
    //}
    //cout << endl;
}
 
class Date
{
    friend ostream& operator<<(ostream& _cout, const Date& d);
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);
    }
 
private:
    int _year;
    int _month;
    int _day;
};
 
ostream& operator<<(ostream& _cout, const Date& d)
{
    _cout << d._year << "-" << d._month << "-" << d._day;
    return _cout;
}
 
 
struct GreaterPDate
{
    bool operator()(const Date* p1, const Date* p2)
    {
        return *p1>*p2;
    }
};
 
void test_priority_queue2()
{
    qjh::priority_queue<Date, vector<Date>, greater<Date>> pq; 
 
    Date d1(2024, 4, 8);
    pq.push(d1);
    pq.push(Date(2024,4,10));
    pq.push({2024,2,15});
 
 
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
 
    qjh::priority_queue<Date*, vector<Date*>, GreaterPDate> pqptr;
 
    pqptr.push(new Date(2024, 4, 14));
    pqptr.push(new Date(2024, 4, 11));
    pqptr.push(new Date(2024, 4, 15));
 
 
    while (!pqptr.empty())
    {
        cout << *(pqptr.top()) << " ";
        pqptr.pop();
    }
    cout << endl;
}
 
//仿函数/函数对象
//它的对象可以像函数一样的去使用
template<class T>
struct Less
{
    bool operator()(const T& x, const T& y)
    {
        return x < y;
    }
};
 
int main()
{
    //test_stack1();
    //test_queue1();
    test_priority_queue2();
    //Less<int> lessfunc;
    //cout << lessfunc(1, 2) << endl;
    //cout << lessfunc.operator()(1, 2) << endl;
    return 0;
}

【C++/STL】stack和queue(容器适配器、优先队列、双端队列)

stack的介绍

stack常用接口

queue的介绍

queue的使用

容器适配器

什么是适配器

STL标准库中stack和queue的底层结构

deque的简单介绍

deque的缺陷

STL的六大组件

模拟实现

stack

queue

优先队列

常用接口

简单使用

sort函数排序

模拟实现(简单版)

自定义类型

测试完整代码

queue.h

stack.h

test.cpp

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++/STL】stack和queue(容器适配器、优先队列、双端队列)

stack的介绍

stack常用接口

queue的介绍

queue的使用

容器适配器

什么是适配器

STL标准库中stack和queue的底层结构

deque的简单介绍

deque的缺陷

STL的六大组件

模拟实现

stack

queue

优先队列

常用接口

简单使用

sort函数排序

模拟实现(简单版)

自定义类型

测试完整代码

queue.h

stack.h

test.cpp

热门文章

最新文章

相关课程

相关电子书

相关实验场景