C++:stack、queue、priority_queue增删查改模拟实现、deque底层原理

C++:stack、queue、priority_queue增删查改模拟实现

  • 前言
  • 一、C++stack的介绍和使用
    • 1.1 引言
    • 1.2 satck模拟实现
  • 二、C++queue的介绍和使用
    • 2.1 引言
    • 2.2 queue增删查改模拟实现
  • 三、STL标准库中stack和queue的底层结构:deque
    • 3.1 deque的简单介绍(了解)
    • 3.2 deque的缺陷
    • 3.3 为什么选择deque作为stack和queue的底层默认容器
  • 四、priority_queue的介绍和实现
    • 4.1 priority_queue的介绍
    • 4.1 priority_queue的介绍增删查改模拟实现
      • 前言
      • 4.1.1 push()
    • 4.1.2 pop()
      • 4.3 top()、size()、empty()
    • 4.1 priority_queue（优先级队列）增删查改模拟实现
  • 五、所有代码

前言

一、C++stack的介绍和使用

1.1 引言

我们先来看看
stack的相关接口有哪些：
在这里插入图片描述
从栈的接口，我们可以知道栈的接口是一种特殊的vector，所以我们完全可以使用vector来模拟实现stack。

1.2 satck模拟实现

在这里插入图片描述

因此我们可以将底层容器定义成模板，然后将容器类变量作为成员变量进行封装。在实现satck的各种接口时，通过成员变量来调用底层容器的接口。（这就是容器适配器，将容器作为底层复用）

namespace achieveStack
{//对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，template<class T, class Container = deque<T>>//底层容器可以是: vector、list、deque(后续会说明)class stack{public:void push(const T& x){//调用容器_con的尾插_con.push_back(x);}void pop(){//调用容器_con的头删_con.pop_back();}const T& top(){//调用容器_con的接口backreturn _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

二、C++queue的介绍和使用

2.1 引言

同样，我们下来看看queue的接口究竟有哪些：
在这里插入图片描述

2.2 queue增删查改模拟实现

因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实现queue。和stack一样，queue默认底层容器为deque(后续会介绍)，此外还可以用list。
具体如下：
在这里插入图片描述

namespace achieveQueue
{template<class T, class Container = 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;};
}

三、STL标准库中stack和queue的底层结构:deque

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

3.1 deque的简单介绍(了解)

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

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
在这里插入图片描述
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
在这里插入图片描述
那deque是如何借助其迭代器维护其假想连续的结构呢？具体如下：
在这里插入图片描述

3.2 deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

3.3 为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

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

四、priority_queue的介绍和实现

4.1 priority_queue的介绍

和前面一样，我们先来看看priority_queue的接口。
priority_queue（优先级队列）默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆(如需修改为小堆，可以将传入的默认仿函数less改为greater)。
在这里插入图片描述

4.1 priority_queue的介绍增删查改模拟实现

接下来如向下调整、向上调整等都是堆的知识，不懂的参考：【数据结构入门指南】二叉树顺序结构: 堆及实现（全程配图，非常经典）

前言

由于优先队列是一种容器适配器，所以我们可以使用模板将容器作为其成员变量，根据实际传入的容器生成实例化出具体版本。同时我们不仅要实现小堆还有大队，所以我们可以增加一个比较函数的模板参数，根据传入的函数来决定是大队还是小堆。
大致如下：

namespace achievePriority_queue//命名空间
{template<class T, class Container=vector<T>,class Compare = less<T>>class priority_queue{public:priority_queue()//默认构造{}private:Compare com;Container _con;};
}

4.1.1 push()

【分析】：我们可以先尾插数据，由于priority_queue的数据是一个堆结构，还需要将数据调整到合适位置。而插入的数据影响的只是当前元素到祖先之间父子节点关系，所以我们可以采用向上调整算法。
【例子】：
在这里插入图片描述
【代码如下】：

//向上调整
void adjust_up(int child)
{int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void push(const T& x)
{_con.push_back(x);//调用_con对于容器尾插接口adjust_up(_con.size() - 1);//向上调整
}

4.1.2 pop()

【分析】：删除元素，即删除堆顶元素。我们可以先将堆顶元素和堆尾元素交换，在将堆尾元素删除（这样可以防止大量挪动数据）。但交换后的元素还需要调整到合适位置，即采用向下调整算法。
【例子】：
在这里插入图片描述

【代码如下】：

void adjust_down(int parent)//向下调整算法
{int child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = 2 * parent + 1;}else{break;}}
}void pop()
{swap(_con[0], _con[_con.size() - 1]);//堆顶和堆尾元素交换_con.pop_back();//调用_con对于容器的尾删接口adjust_down(0);//向下调整算法
}

4.3 top()、size()、empty()

这些接口比较简单就不一一介绍了，具体代码如下：

const T& top()
{return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}

4.1 priority_queue（优先级队列）增删查改模拟实现

五、所有代码

gitee：C++:stack、queue、priority_queue增删查改模拟实现

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/232058.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Spring Boot实现数据加密脱敏：注解 + 反射 + AOP

Spring Boot实现数据加密脱敏：注解 + 反射 + AOP

文章目录 1. 引言2. 数据加密和脱敏的需求3. Spring Boot项目初始化4. 敏感数据加密注解设计5. 实现加密和脱敏的工具类6. 实体类和加密脱敏注解的使用7. 利用AOP实现加密和脱敏8. 完善AOP切面9. 测试10. 拓展功能与未来展望10.1 加密算法的选择10.2 动态注解配置 11. 总结 &am…
阅读更多...
IoTDB 集群部署——windows

IoTDB 集群部署——windows

本文的测试环境为window server2016&#xff0c;版本包为1.1.0&#xff0c;jdk版本为1.8 首先下载IoTDB版本包&#xff0c;链接地址如下 https://archive.apache.org/dist/iotdb/1.1.0/apache-iotdb-1.1.0-all-bin.zip 本次部署将使用1个ConfigNode 和3个DataNode模式&#…
阅读更多...
Rancher 单节点 docker 部署备份与恢复

Rancher 单节点 docker 部署备份与恢复

Rancher 单节点 docker 部署备份与恢复 1. 备份集群 获取 rancher server 容器名&#xff0c;本例为 angry_aryabhata docker ps | grep rancher/rancher6a27b8634c80 rancher/rancher:v2.5.14 xxx angry_aryabhata停止容器 docker stop angry_aryabhata创建备…
阅读更多...
深入理解Vue3中的自定义指令

深入理解Vue3中的自定义指令

Vue3是一个流行的前端框架&#xff0c;它引入了许多新特性和改进&#xff0c;其中之一是自定义指令。自定义指令是一种强大的功能&#xff0c;可以让开发者在模板中直接操作 DOM 元素。本文将深入探讨 Vue3中的自定义指令&#xff0c;包括自定义指令的基本用法、生命周期钩子函…
阅读更多...
uniappVue3版本中组件生命周期和页面生命周期的详细介绍

uniappVue3版本中组件生命周期和页面生命周期的详细介绍

一、什么是生命周期&#xff1f; 生命周期有多重叫法&#xff0c;有叫生命周期函数的&#xff0c;也有叫生命周期钩子的&#xff0c;还有钩子函数的&#xff0c;其实都是代表&#xff0c;在 Vue 实例创建、更新和销毁的不同阶段触发的一组钩子函数&#xff0c;这些生命周期函数…
阅读更多...
Flutter 混合开发 - aar打包

Flutter 混合开发 - aar打包

背景 项目接入 Flutter 后有两种方式&#xff0c;一种是 module 引入开发&#xff0c;一种是 aar 依赖开发。当前项目中在 Debug 阶段为了方便调试采用 module 开发&#xff0c;在发版时&#xff08;即 Release 阶段&#xff09;采用 aar 依赖引入。为了配合这种模式就需要在 …
阅读更多...
个人笔记：分布式大数据技术原理（一）Hadoop 框架

个人笔记：分布式大数据技术原理（一）Hadoop 框架

Apache Hadoop 软件库是一个框架&#xff0c;它允许使用简单的编程模型&#xff0c;实现跨计算机集群的大型数据集的分布式处理。它最初的设计目的是为了检测和处理应用程序层的故障&#xff0c;从单个机器扩展到数千台机器&#xff08;这些机器可以是廉价的&#xff09;&#…
阅读更多...
学会视频剪辑方法：从视频中提取封面，增加视频观看量

学会视频剪辑方法：从视频中提取封面，增加视频观看量

在数字媒体时代&#xff0c;视频已经成为信息传递的主要方式之一。那如何让视频在众多内容中脱颖而出&#xff0c;吸引更多的观众呢&#xff1f;除了内容本身的质量外&#xff0c;视频的封面也是吸引的关键因素之一。下面一起看云炫AI智剪如何通过视频剪辑方法从视频中提取封面…
阅读更多...
Vue框架底层

Vue框架底层

一、前端框架的由来 1、服务端渲染 sequenceDiagram 浏览器->>服务器: https://www.bilibili.com/ Note right of 服务器: 组装页面(服务端渲染) 服务器->>-浏览器: 完整页面2、前后端分离 sequenceDiagram 浏览器->>服务器: https://www.bilibili.com/ 服务…
阅读更多...
2023 年中国高校大数据挑战赛赛题B DNA 存储中的序列聚类与比对-解析与参考代码

2023 年中国高校大数据挑战赛赛题B DNA 存储中的序列聚类与比对-解析与参考代码

题目背景&#xff1a;目前往往需要对测序后的序列进行聚类与比对。其中聚类指的是将测序序列聚类以判断原始序列有多少条&#xff0c;聚类后相同类的序列定义为一个簇。比对则是指在聚类基础上对一个簇内的序列进行比对进而输出一条最有 可能的正确序列。通过聚类与比对将会极大…
阅读更多...
Vue页面传值：Props属性与$emit事件的应用介绍

Vue页面传值：Props属性与$emit事件的应用介绍

一、vue页面传值 在Vue页面中传值有多种方式&#xff0c;简单介绍以下两种 通过props属性传递值&#xff1a;父组件在子组件上定义props属性&#xff0c;子组件通过props接收父组件传递的值。通过$emit触发事件传递值&#xff1a;子组件通过$emit方法触发一个自定义事件&#…
阅读更多...
Linux第18步_安装“Ubuntu系统下的C语言编译器ＧＣＣ”

Linux第18步_安装“Ubuntu系统下的C语言编译器ＧＣＣ”

Ubuntu系统没有提供C/C的编译环境&#xff0c;因此还需要手动安装build-essential软件包&#xff0c;它包含了 GNU 编辑器&#xff0c;GNU 调试器&#xff0c;和其他编译软件所必需的开发库和工具。本节用于重点介绍安装“Ubuntu系统下的C语言编译器&#xff27;&#xff23;&a…
阅读更多...
Hierarchical Clusting模型

Hierarchical Clusting模型

介绍&#xff1a; Hierarchical Clustering 是一种常用的聚类方法&#xff0c;它通过构建一个层次化的聚类树&#xff08;或者称为聚类图&#xff09;&#xff0c;将数据点逐步合并组成不同的聚类簇。 Hierarchical Clustering 的主要思想是将相似的数据点归为一类&#xff0c…
阅读更多...
竞赛保研 基于深度学习的人脸专注度检测计算系统 - opencv python cnn

竞赛保研 基于深度学习的人脸专注度检测计算系统 - opencv python cnn

文章目录 1 前言2 相关技术2.1CNN简介2.2 人脸识别算法2.3专注检测原理2.4 OpenCV 3 功能介绍3.1人脸录入功能3.2 人脸识别3.3 人脸专注度检测3.4 识别记录 4 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 基于深度学习的人脸专注度…
阅读更多...
作业三详解

作业三详解

作业3&#xff1a; 在作业1的基础上&#xff0c;整合修改、删除功能&#xff0c;可实现如下功能 1.进入新增页面&#xff0c;页面填入新增数据&#xff0c;提交表单&#xff0c;然后跳转到查询列表页面&#xff0c;列表页面显示所有记录&#xff08;多一条新增的数据&#xff…
阅读更多...
Eureka服务注册与发现中心

Eureka服务注册与发现中心

简介 Spring Cloud封装了Netflix 公司开发的Eureka模块来实现服务治理 在传统的RPC远程调用框架中&#xff0c;管理每个服务与服务之间依赖关系比较复杂&#xff0c;管理比较复杂&#xff0c;所以需要使用服务治理&#xff0c;管理服务于服务之间依赖关系&#xff0c;可以实现…
阅读更多...
vue简单实现滚动条

vue简单实现滚动条

背景&#xff1a;产品提了一个需求在一个详情页&#xff0c;一个form表单元素太多了&#xff0c;需要滚动到最下面才能点击提交按钮&#xff0c;很不方便。他的方案是&#xff0c;加一个滚动条&#xff0c;这样可以直接拉到最下面。 优化&#xff1a;1、支持滚动条&#xff0c;…
阅读更多...
Beauty algorithm（三）腮红

Beauty algorithm（三）腮红

查阅资料了解到腮红位于苹果肌处，同样使用关键点确定目标区域，然后对该区域进行渲染达到美妆效果。考虑到如果使用简单的RGB是很难做到特效，本篇采用模板方式进行区域融合。 一、skills 前瞻 1、png图像读取 cv::imread(imgPath, cv::IMREAD_UNCHANGED) IMREAD_UNCHANGE…
阅读更多...
C++ OpenGL 3D GameTutorial 1：Making the window with win32 API学习笔记

C++ OpenGL 3D GameTutorial 1：Making the window with win32 API学习笔记

视频地址https://www.youtube.com/watch?vjHcz22MDPeE&listPLv8DnRaQOs5-MR-zbP1QUdq5FL0FWqVzg 一、入口函数 首先看入口函数main代码&#xff1a; #include<OGL3D/Game/OGame.h>int main() {OGame game;game.Run();return 0; } 这里交代个关于C语法的问题&#x…
阅读更多...
Swift爬虫使用代理IP采集唯品会商品详情

Swift爬虫使用代理IP采集唯品会商品详情

目录 一、准备工作 二、代理IP的选择与使用 三、使用Swift编写唯品会商品爬虫 四、数据解析与处理 五、注意事项与优化建议 六、总结 一、准备工作 在开始编写爬虫之前&#xff0c;需要准备一些工具和库&#xff0c;以确保数据抓取的顺利进行。以下是所需的工具和库&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发