【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;
  };
}
相关文章
|
19天前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
51 21
|
1月前
|
C++ 开发者
C++学习之继承
通过继承,C++可以实现代码重用、扩展类的功能并支持多态性。理解继承的类型、重写与重载、多重继承及其相关问题,对于掌握C++面向对象编程至关重要。希望本文能为您的C++学习和开发提供实用的指导。
55 16
|
2月前
|
算法 网络安全 区块链
2023/11/10学习记录-C/C++对称分组加密DES
本文介绍了对称分组加密的常见算法(如DES、3DES、AES和国密SM4)及其应用场景,包括文件和视频加密、比特币私钥加密、消息和配置项加密及SSL通信加密。文章还详细展示了如何使用异或实现一个简易的对称加密算法,并通过示例代码演示了DES算法在ECB和CBC模式下的加密和解密过程,以及如何封装DES实现CBC和ECB的PKCS7Padding分块填充。
65 4
2023/11/10学习记录-C/C++对称分组加密DES
|
4月前
|
编译器 C语言 C++
配置C++的学习环境
【10月更文挑战第18天】如果想要学习C++语言,那就需要配置必要的环境和相关的软件,才可以帮助自己更好的掌握语法知识。 一、本地环境设置 如果您想要设置 C++ 语言环境,您需要确保电脑上有以下两款可用的软件,文本编辑器和 C++ 编译器。 二、文本编辑器 通过编辑器创建的文件通常称为源文件,源文件包含程序源代码。 C++ 程序的源文件通常使用扩展名 .cpp、.cp 或 .c。 在开始编程之前,请确保您有一个文本编辑器,且有足够的经验来编写一个计算机程序,然后把它保存在一个文件中,编译并执行它。 Visual Studio Code:虽然它是一个通用的文本编辑器,但它有很多插
|
4月前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
60 1
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
68 19
|
1月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
47 13
|
1月前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
48 5
|
1月前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
38 5
|
1月前
|
Serverless 编译器 C++
【C++面向对象——类的多态性与虚函数】计算图像面积(头歌实践教学平台习题)【合集】
本任务要求设计一个矩形类、圆形类和图形基类,计算并输出相应图形面积。相关知识点包括纯虚函数和抽象类的使用。 **目录:** - 任务描述 - 相关知识 - 纯虚函数 - 特点 - 使用场景 - 作用 - 注意事项 - 相关概念对比 - 抽象类的使用 - 定义与概念 - 使用场景 - 编程要求 - 测试说明 - 通关代码 - 测试结果 **任务概述:** 1. **图形基类(Shape)**:包含纯虚函数 `void PrintArea()`。 2. **矩形类(Rectangle)**:继承 Shape 类,重写 `Print
47 4