C++ 栈 / 队列 / 堆使用及模拟

2022-10-26
湖南
本文字数：6433 字
阅读完需：约 21 分钟

零、前言

本章主要讲解学习 C++中的容器 stack（栈），queue（队列），priority_queue（优先级队列，相当于数据结构中的 heap（堆）），在熟悉使用后进行模拟实现

一、stack 的介绍和使用

1、stack 的介绍

stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作
stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出
stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：empty：判空操作 back：获取尾部元素操作 push_back：尾部插入元素操作 pop_back：尾部删除元素操作
标准容器 vector、deque、list 均符合这些需求，默认情况下，如果没有为 stack 指定特定的底层容器，默认情况下使用 deque(双端队列，也是一种容器)

示图：

2、stack 的使用

例题 1：用栈实现队列

力扣链接：232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)

实现思路：

这里需要两个栈，一个栈用来入数据，一个栈用来出数据
push：只往入数据栈入数据
pop：只让出数据栈出数据，如果没有数据，则需将入数据中的数据全部依次出栈并随后入栈到出数据栈中
以此实现队列先进先出的特性

实现代码：

class MyQueue {public:    MyQueue() {//不需要写什么，对于自定义类型stack会自动调用其构造函数    }        void push(int x) {        //入栈栈入数据        st1.push(x);    }        int pop() {        int ret;        //出栈栈有无数据        if(!st2.empty())        {            ret=st2.top();            st2.pop();            return ret;        }        else        {            //将数据入栈出栈            while(!st1.empty())            {                st2.push(st1.top());                st1.pop();            }            //pop数据            ret=st2.top();            st2.pop();            return ret;        }    }        int peek() {        if(!st2.empty())        {            return st2.top();        }        else        {            while(!st1.empty())            {                st2.push(st1.top());                st1.pop();            }            return st2.top();        }    }        bool empty() {        return st1.empty()&&st2.empty();    }    private:    stack<int> st1;    stack<int> st2;};

复制代码

二、queue 的介绍和使用

1、queue 的介绍

队列是一种容器适配器，专门用于在 FIFO 上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素；元素从队尾入队列，从队头出队列
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:empty：检测队列是否为空 size：返回队列中有效元素的个数 front：返回队头元素的引用 back：返回队尾元素的引用 push_back：在队列尾部入队列 pop_front：在队列头部出队列
标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque(双端队列)

示图：

2、queue 的使用

例题 2：用队列实现栈

力扣链接：225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)

实现思路：

这里我们也需要两个队列
push：往有数据的队列入队列
pop：将有数据队列的数据（除最后一个数据）给依次出队列并入队列到另一个队列中，最后将最后一个数据给出队列
以此实现栈的先进后出的特性

实现代码：

class MyStack {public:    MyStack() {
    }        void push(int x) {        //入有数据队列        if(q1.empty())        {            q2.push(x);        }        else        {            q1.push(x);        }    }        int pop() {        //确定哪个队列有数据        queue<int>*q=&q1;        queue<int>*nonq=&q2;        if(q1.empty())        {            q=&q2;            nonq=&q1;        }        //出队列再入队列        while(q->size()>1)        {            nonq->push(q->front());            q->pop();        }        //pop数据        int ret=q->front();        q->pop();        return ret;    }        int top() {        if(!q1.empty())        {            return q1.back();        }        else        {            return q2.back();        }    }        bool empty() {        return q1.empty()&&q2.empty();    }    private:    queue<int> q1;    queue<int> q2;};

复制代码

三、priority_queue 的介绍和使用

1、priority_queue 的介绍

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的（默认的优先级队列）
优先级队列类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素
标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用 vector
需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作（也是封装）

注：以大堆为例

示图：物理结构
示图：逻辑结构

总结：

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

注意：默认情况下 priority_queue 是大堆

2、priority_queue 的使用

使用示例：

#include <vector>#include <queue>#include <functional> // greater算法的头文件
void TestPriorityQueue(){    // 默认情况下，创建的是大堆，其底层按照小于号比较    vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };    priority_queue<int> q1;    for (auto& e : v)        q1.push(e);    cout << q1.top() << endl;    // 如果要创建小堆，将第三个模板参数换成greater比较方式    priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());    cout << q2.top() << endl;    // 堆排序输出数据    while (!q1.empty())    {        cout << q1.top() << " ";        q1.pop();    }cout << endl;    while (!q2.empty())    {        cout << q2.top() << " ";        q2.pop();    }cout << 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 TestPriorityQueue2(){    // 大堆，需要用户在自定义类型中提供<的重载    priority_queue<Date> q1;    q1.push(Date(2021, 10, 19));    q1.push(Date(2021, 10, 29));    q1.push(Date(2021, 12, 16));    q1.push(Date(2021, 8, 18));    q1.push(Date(2021, 9, 15));    cout << q1.top() << endl;    // 如果要创建小堆，需要用户提供>的重载    priority_queue<Date, vector<Date>, greater<Date>> q2;    q2.push(Date(2021, 10, 19));    q2.push(Date(2021, 10, 29));    q2.push(Date(2021, 12, 16));    q2.push(Date(2021, 8, 18));    q2.push(Date(2021, 9, 15));    cout << q2.top() << endl;    while (!q1.empty())    {        cout << q1.top() << " ";        q1.pop();    }cout << endl;    while (!q2.empty())    {        cout << q2.top() << " ";        q2.pop();    }cout << endl;}

复制代码

结果：

四、容器适配器

概念：

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)
该种模式是将一个类的接口转换成客户希望的另外一个接口
也就是将容器将其接口进行适当封装来得到想要的功能和特性

stack/queue/priority_queue 的底层结构：

虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称容器适配器
因为 stack 和队列只是对其他容器的接口进行了包装（STL 中 stack 和 queue 默认使用 deque，priority_queue 则使用了 vector 来封装实现其特性）

示图：

五、deque 的简单介绍

注：对于 deque 只做了解

介绍：

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

示图：

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

示图：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了 deque 的迭代器身上，因此 deque 的迭代器设计就比较复杂

示图：

迭代器如何维护空间：

总结

优势：

与 vector 比较，deque 头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素；与 list 比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段，可以进行随机访问（结合了 vector 和 list 的优点）

缺点：

不适合遍历，deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下（因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多，而目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构）

为什么选择 deque 作为底层默认容器

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

六、stack 的模拟实现

实现代码：

namespace cole{    template<class T,class Container=std::deque<T>>    class stack    {    public:        void push(const T& x)        {            con.push_back(x);        }
        void pop()        {            con.pop_back();        }
        const T& top()        {            return con.back();        }
        size_t size()        {            return con.size();        }
        bool empty()        {            return con.empty();        }    private:        Container con;    };}

复制代码

七、queue 的模拟实现

实现代码：

namespace cole{    template<class T,class Container=std::deque<T>>    class 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()        {            return con.size();        }
        bool empty()        {            return con.empty();        }    private:        Container con;    };}

复制代码

八、priority_queue 的模拟实现

实现代码：

namespace cole{    //仿函数-函数对象（该类对象可以像函数一样使用）    template<class T>    struct less    {        bool operator()(const T& a, const T& b)        {            return a < b;        }    };    template<class T>    struct greater    {        bool operator()(const T& a, const T& b)        {            return a > b;        }    };
    template<class T,class Container=std::deque<T>,class Compare=less<T>>//默认大堆    class priority_queue    {    public:        //向上调整数据        void Adjustup(size_t child)        {            size_t parent = (child - 1) / 2;            while (child > 0)            {                //是否调整                if (cmp(con[parent], con[child]))                {                    swap(con[child], con[parent]);                    child = parent;                    parent = (child - 1) / 2;                }                else                {                    break;                }            }        }        //向下调整数据        void Adjustdown(size_t parent)        {            size_t child = parent * 2 + 1;            while (child < con.size())            {                //比较左右子节点                if (child + 1 < con.size() && cmp(con[child], con[child + 1]))                {                    ++child;                }                //是否调整                if (cmp(con[parent], con[child]))                {                    swap(con[child], con[parent]);                    parent = child;                    child = parent * 2 + 1;                }                else                {                    break;                }            }        }
        void push(const T& x)        {            con.push_back(x);            Adjustup(con.size() - 1);        }
        void pop()        {            swap(con[0], con[con.size() - 1]);            con.pop_back();            Adjustdown(0);        }
        const T& top()        {            return con[0];        }
        size_t size()        {            return con.size();        }
        bool empty()        {            return con.empty();        }    private:        Container con;        Compare cmp;    };}

复制代码

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/5ae9925cd221b09e8579a1678】。文章转载请联系作者。

可口也可樂

关注

还未添加个人签名 2022-04-28 加入

还未添加个人简介

发布

暂无评论

创作场景

C++ 栈 / 队列 / 堆使用及模拟

零、前言

一、stack 的介绍和使用

1、stack 的介绍

2、stack 的使用

二、queue 的介绍和使用

1、queue 的介绍

2、queue 的使用

三、priority_queue 的介绍和使用

1、priority_queue 的介绍

2、priority_queue 的使用

四、容器适配器

五、deque 的简单介绍

六、stack 的模拟实现

七、queue 的模拟实现

八、priority_queue 的模拟实现

可口也可樂

评论