【C++初阶学习】stack/queue/priority_queue的使用和模拟(3)

简介: 【C++初阶学习】stack/queue/priority_queue的使用和模拟(3)

五、deque的简单介绍


注:对于deque只做了解


  • 介绍:


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


  • 示图:


image.png


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


  • 示图:


edc595e4a26f495993c08cb6e9884f72.png


  1. deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的(类似于一个动态的二维数组)
  • 示图:


image.png


image.png


总结

优势:

与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;
  };
}
目录
打赏
0
0
0
0
2
分享
相关文章
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
214 1
|
6月前
|
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
135 21
|
6月前
|
C++学习之继承
通过继承,C++可以实现代码重用、扩展类的功能并支持多态性。理解继承的类型、重写与重载、多重继承及其相关问题,对于掌握C++面向对象编程至关重要。希望本文能为您的C++学习和开发提供实用的指导。
111 16
2023/11/10学习记录-C/C++对称分组加密DES
本文介绍了对称分组加密的常见算法(如DES、3DES、AES和国密SM4)及其应用场景,包括文件和视频加密、比特币私钥加密、消息和配置项加密及SSL通信加密。文章还详细展示了如何使用异或实现一个简易的对称加密算法,并通过示例代码演示了DES算法在ECB和CBC模式下的加密和解密过程,以及如何封装DES实现CBC和ECB的PKCS7Padding分块填充。
151 4
2023/11/10学习记录-C/C++对称分组加密DES
配置C++的学习环境
【10月更文挑战第18天】如果想要学习C++语言,那就需要配置必要的环境和相关的软件,才可以帮助自己更好的掌握语法知识。 一、本地环境设置 如果您想要设置 C++ 语言环境,您需要确保电脑上有以下两款可用的软件,文本编辑器和 C++ 编译器。 二、文本编辑器 通过编辑器创建的文件通常称为源文件,源文件包含程序源代码。 C++ 程序的源文件通常使用扩展名 .cpp、.cp 或 .c。 在开始编程之前,请确保您有一个文本编辑器,且有足够的经验来编写一个计算机程序,然后把它保存在一个文件中,编译并执行它。 Visual Studio Code:虽然它是一个通用的文本编辑器,但它有很多插
213 6
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
114 1
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
43 0
c++的类(附含explicit关键字,友元,内部类)
本文介绍了C++中类的核心概念与用法,涵盖封装、继承、多态三大特性。重点讲解了类的定义(`class`与`struct`)、访问限定符(`private`、`public`、`protected`)、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数(构造函数、析构函数、拷贝构造、赋值重载)以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员(变量与函数)、友元(友元函数与友元类)的概念及其使用场景,并简要介绍了内部类的特性。
110 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问