stack和queue ---＞容器适配器

不支持迭代器，迭代器无法满足他们的性质

边出边判断

实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
int main()
{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;
}

//用适配器的方式实现栈

//Stack.h#pragma once
#include<vector>
#include<list>
//模板
//template<class T>
//class stack
//{
//	T* _a;
//	size_t _top;
//	size_t _capacity;
//};//传什么就是什么
//stack<int,vector<int>> s1;
//stack<int,list<int>> s1;namespace DD
{
//加上模板的方式template<class T, class Container>class stack{public:void push(const T& x)//入栈{_con.push_back(x);}void pop()//出栈{_con.pop_back();}const T& top() const//取栈顶元素{return _con.back();}size_t size()const//size{return _con.size();}bool empty() const//判空{return _con.empty();}private:Container _con;};
}

//Test.cpp#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
#include"Stack.h"
int main()
{//显示传一个容器//DD::stack<int,vector<int>> st;//实现的数组栈DD::stack<int,list<int>> st;//实现链式栈st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;return 0;
}
//4 3 2 1

//也可以是缺省的

 template<class T, class Container=vector<int>>
//也可以是缺省的
DD::stack<int>st;//4 3 2 1

//用适配器的方式实现队列

//Queue.h#pragma once
#include<vector>
#include<list>
#include<deque>namespace DD
{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() const{return _con.front();}const T& back() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}
//Test.cpp#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
#include"Queue.h"//.h是用来展开的
int main()
{//DD::queue<int>q;     //1 2 3 4//DD::queue<int, list<int>>q;  //1 2 3 4DD::queue<int, vector<int>>q;//不支持，会报错q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty())//队列不为空取队头数据{cout << q.front() << " ";q.pop();}cout << endl;return 0;
}

deque的介绍

deque（双端队列）：是一种双开口的“连续”空间的数据结果，双开口的含义是：可以在头尾两端进行插入和删除操作，并且数据复杂度为O（1）

vector 插入数据需要扩容，与vector比较，头插效率高，不需要搬移元素

list不支持随机访问

与list相比其底层是连续空间，空间利用率比较高，不需要存储额外字段

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

为什么选择deque（核心是迭代器支撑的）作为stack和queue的底层默认容器

stack是一种先进后出的特殊线性结构，因此只要具有push_back()和pop_back()操作的线性结构都可以作为stack的底层容器，vector和list都可以

queue是先进先出的特殊线性数据结构，只要具有push_back()和pop_front()操作的线性结构都可以作为queue的底层容器，比如list

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

1）stack和queue不需要遍历（没有迭代器），只需要在固定的一端或者两端进行操作

2）在stack中元素增长时，deque比vector的效率高，不需要挪动数据，；queue中的元素增长时，deque不仅效率高，而且内存使用率高

结合了deque的缺点，完美地避开了他的缺点

deque借助其迭代器维护其假想连续的结构的方式

头插和尾插

priority_queue的模拟实现

通过对priority_queue的底层结构是堆，依次此处秩序堆堆进行通用的封装即可

//PriorityQueue.h#pragma once
#include<vector>
namespace DD
{//默认用vector适配template<class T,class Container=vector<T>>class priority_queue{public:void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){//小堆if (_con[child] < _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}}//优先级队列的插入void push(const T& x){//要向上调整_con.push_back(x);AdjustUp(_con.size() - 1);//size是最后一个数据的下一个位置}void AdjustDown(int 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();//从根位置向下调整AdjustDown(0);}//判空bool empty(){return _con.empty();}const T& top(){return _con[0];//返回堆顶位置的数据就是根位置的数据}size_t size(){return _con.size();}private:Container _con;};
}
//Test.cpp#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
#include"Stack.h"
#include"Queue.h"//.h是用来展开的#include"PriorityQueue.h"
int main()
{//默认是大的优先级高DD::priority_queue<int>pq;//4 3 2 1//可以改成小的优先级高//priority_queue<int,vector<int>,greater<int>>pq;//1 2 3 4pq.push(4);pq.push(2);pq.push(1);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}//我们是小堆 所以是 1 2 3 4

优先级队列还支持迭代器区间构造

//PoriorityQueue.h#pragma once
#include<vector>
namespace DD
{//默认用vector适配template<class T,class Container=vector<T>>class priority_queue{public://我们不写编译器会自动生成，自动生成会调用Container _con的默认构造//强制生成默认构造priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){//建堆//从最后一个结点的叶子结点开始，叶子结点不需要我们建，所以建倒着走的第一个非叶子结点，他是最后一个结点的父亲for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--);//_con.size()-1是最后一个叶子结点的下标{AdjustDown(i);}}void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){//小堆if (_con[child] < _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}}//优先级队列的插入void push(const T& x){//要向上调整_con.push_back(x);AdjustUp(_con.size() - 1);//size是最后一个数据的下一个位置}void AdjustDown(int 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();//从根位置向下调整AdjustDown(0);}//判空bool empty(){return _con.empty();}const T& top(){return _con[0];//返回堆顶位置的数据就是根位置的数据}size_t size(){return _con.size();}private:Container _con;};
}
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"PriorityQueue.h"
int main()
{
//迭代器区间可以是我们容器的，也可以是指向数组的指针int a[] = { 1,4,2,5,6,3,2 };DD::priority_queue<int>pq1(a, a + sizeof(a) / sizeof(int));

仿函数

//仿函数
//仿函数是一个类
//这个类型的对象可以像函数一样使用，因为重载了operator（）
template<class T>
struct Less
{//重载了opertor（）bool operator()(const T& x, const T& y)const{return x < y;}
};
int main()
{//lessFunc是这个类型的对象Less<int>lessFunc;cout << lessFunc(1, 2) << endl;cout << lessFunc.operator()(1, 2) << endl;//本质是调用operator（）}//1
//1

外：

仿函数可以用来建堆，以及日期类的比较

传小于是大堆

多参数构造函数支持隐式类型转换

我们默认没传是大堆

sort(aq1.begin(),dq1.end(),less<int>());  //是函数对应的参数，要加（）priority_queue<int,vector<int>,less<int>> pq;   //是类对应的参数，不加（）

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

UE5 材质篇 1 如何偏移顶点

UE5 材质篇 1 如何偏移顶点

顶点偏移 start content里的plane长这样 我们进行一点顶点偏移就能长这样 XY加起来乘个缩放系数扔给sin结果乘个缩放系数即可
阅读更多...
MySQL45讲 第十六讲 “order by”是怎么工作的？

MySQL45讲 第十六讲 “order by”是怎么工作的？

文章目录 MySQL45讲 第十六讲 “order by”是怎么工作的&#xff1f;一、引言二、全字段排序&#xff08;一&#xff09;索引创建与执行情况分析&#xff08;二&#xff09;执行流程&#xff08;三&#xff09;查看是否使用临时文件 三、rowid 排序&#xff08;一&#xff09;参…
阅读更多...
Ansys HFSS：外壳的屏蔽效果演示

Ansys HFSS：外壳的屏蔽效果演示

欢迎回来&#xff01;随着电子系统变得越来越复杂和集成&#xff0c;确保适当的屏蔽以减轻电磁干扰 &#xff08;EMI&#xff09; 变得越来越重要。 继续讨论屏蔽效果&#xff0c;我们现在将重点转移到另一个强大的工具上&#xff1a;Ansys HFSS&#xff08;高频结构仿真器&am…
阅读更多...
无人机避障——（局部规划方法）DWA（动态窗口法）

无人机避障——（局部规划方法）DWA（动态窗口法）

传统的DWA算法更加倾向于车辆等差速无人车&#xff0c;旋翼无人机是全速的&#xff0c;全向的。 全局路径是通过A*算法生成的 局部路径规划效果&#xff1a; DWA算法效果&#xff1a; 过程图&#xff1a; 完整过程&#xff1a; PID算法效果&#xff1a; 过程图&#xff1a…
阅读更多...
数据库-＞视图

数据库-＞视图

目录 一、视图 1.什么是视图 ​编辑 2.创建视图 1.语法 3.使用视图 4.视图的功能 1.屏蔽相关字段 2.对外提供统一访问规范 3.视图和真实表进行表连接查询 5.修改数据 6.注意事项 7.删除视图 1.语法 8.视图的优点 1. 简单性 2. 安全性 3. 逻辑数据独⽴性 4. 重…
阅读更多...
el-scrollbar 动态更新内容 鼠标滚轮无效

el-scrollbar 动态更新内容 鼠标滚轮无效

有以下功能逻辑&#xff0c;实现了一个时间轴组件&#xff0c;点击、-号后像地图那样放大组件以显示不同的UI。 默认显示年月&#xff1a; 当点击一下加号时切换为年&#xff1a; 当点击减号时切换为日&#xff1a; 即加号、减号点击就是在年月日显示进行切换。给Scrollvie…
阅读更多...
动态ip如何自动更换ip

动态ip如何自动更换ip

在探讨如何自动更换动态IP地址时&#xff0c;我们首先需要理解动态IP的基本概念。IP地址&#xff0c;即互联网协议地址&#xff0c;分配给每台连接到互联网的设备的唯一标识符。与传统静态IP地址不同&#xff0c;动态IP地址是由网络服务提供商&#xff08;ISP&#xff09;动态分…
阅读更多...
关于金属氢化物（储氢）PCT曲线拟合、ZBS有效导热系数模型、JMAK类型吸放氢动力学方程的笔记

关于金属氢化物（储氢）PCT曲线拟合、ZBS有效导热系数模型、JMAK类型吸放氢动力学方程的笔记

参考文献&#xff1a;Experimental and numerical study of metal hydride beds with Ti0.92Zr0.10Cr1.0Mn0.6Fe0.4 alloy for hydrogen compressionhttps://www.sciencedirect.com/science/article/pii/S1385894723043851?via%3Dihub#s0010 一、PCT曲线拟合 根据以下文献内容…
阅读更多...
力扣最热一百题——验证二叉搜索树

力扣最热一百题——验证二叉搜索树

目录 题目链接&#xff1a;98. 验证二叉搜索树 - 力扣&#xff08;LeetCode&#xff09; 题目描述 示例 提示&#xff1a; 二叉搜索树的要求 解法一&#xff1a;采用中序遍历 中序遍历的定义 为什么二叉搜索树的中序遍历是严格递增的 二叉搜索树&#xff08;BST&#x…
阅读更多...
如何无缝更换WordPress主题：关键步骤详解

如何无缝更换WordPress主题：关键步骤详解

更换WordPress主题对于希望刷新网站外观或改善用户体验的站长来说&#xff0c;是一项常见但不容忽视的任务。无论是为了提升性能还是实现新的设计风格&#xff0c;在更换主题时&#xff0c;确保不遗漏任何重要细节至关重要。本文将详细介绍更换WordPress主题的关键步骤&#xf…
阅读更多...
科技改变阅读习惯：最新研究揭示电子阅读器的普及趋势

科技改变阅读习惯：最新研究揭示电子阅读器的普及趋势

据QYResearch调研团队最新报告“全球电子阅读器市场报告2023-2029”显示&#xff0c;预计2029年全球电子阅读器市场规模将达到6.9亿美元&#xff0c;未来几年年复合增长率CAGR为0.4%。 如上图表/数据&#xff0c;摘自QYResearch最新报告“全球电子阅读器市场研究报告2023-2029.…
阅读更多...
ServletContext 对象介绍

ServletContext 对象介绍

文章目录 1、ServletContext对象介绍1_方法介绍2_用例分析 2、ServletContainerInitializer1_整体结构2_工作原理3_使用案例 3、Spring案例源码分析1_注册DispatcherServlet2_注册配置类3_SpringServletContainerInitializer 4_总结 ServletContext 表示上下文对象&#xff0c;…
阅读更多...
高频面试题（含笔试高频算法整理）基本总结回顾48

高频面试题（含笔试高频算法整理）基本总结回顾48

干货分享&#xff0c;感谢您的阅读&#xff01; &#xff08;暂存篇---后续会删除&#xff0c;完整版和持续更新见高频面试题基本总结回顾&#xff08;含笔试高频算法整理&#xff09;&#xff09; 备注&#xff1a;引用请标注出处&#xff0c;同时存在的问题请在相关博客留言…
阅读更多...
yolov8涨点系列之引入CBAM注意力机制

yolov8涨点系列之引入CBAM注意力机制

文章目录 YOLOv8 中添加注意力机制 CBAM 具有多方面的好处特征增强与选择通道注意力方面空间注意力方面 提高模型性能计算效率优化&#xff1a; yolov8增加CBAM具体步骤CBAM代码(1)在__init.pyconv.py文件的__all__内添加‘CBAM’(2)conv.py文件复制粘贴CBAM代码(3)修改task.py…
阅读更多...
python实现tkinter解密剧情文本游戏

python实现tkinter解密剧情文本游戏

目录 需求 效果 代码实现 代码说明 需求 python实现tkinter解密剧情文本游戏 效果 代码实现 import tkinter as tkclass StoryGame:def __init__(self, master):self.master mastermaster.title("剧情游戏")# 初始化故事节点self.current_node 0# 故事节点数…
阅读更多...
C 学习（5）

C 学习（5）

哈哈哈哈哈&#xff0c;终于想起来了&#xff01;贴一下主要的参考&#xff1a; 基本语法 - 《阮一峰《C 语言教程》》 - 书栈网 BookStack 内容写的比较浅显有疏漏&#xff0c;如果看不明白&#xff0c;再结合一下百度。 注释 C 语言的注释有两种表示方法。 第一种方法是…
阅读更多...
解读《ARM Cortex-M3 与Cortex-M4 权威指南》——第3章 技术综述

解读《ARM Cortex-M3 与Cortex-M4 权威指南》——第3章 技术综述

加载—存储架构 ISA(指令集架构) 指令集架构 (ISA) 是计算机处理器能够理解和执行的指令集合。它定义了计算机系统中硬件和软件之间的接口 ISA 是硬件与软件之间的接口规范，它定义了处理器能执行哪些操作，程序员和编译器可以依此编写代码。 常见的 ISA 类型： CISC (Comp…
阅读更多...
【Linux】linux c语言调用send()接口内核调用流程

【Linux】linux c语言调用send()接口内核调用流程

1、C语言测试代码&#xff1a; #include <errno.h> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <err.h> #include <sys/types.h> #include <sys/socket.h> #include <net…
阅读更多...
【Windows修改Docker Desktop(WSL2)内存分配大小】

【Windows修改Docker Desktop(WSL2)内存分配大小】

记录一下遇到使用Docker Desktop占用内存居高不下的问题 自从使用了Docker Desktop&#xff0c;电脑基本每天都需要重启&#xff0c;内存完全不够用&#xff0c;从16g扩展到24&#xff0c;然后到40G&#xff0c;还是不够用&#xff1b;打开Docker Desktop 运行时间一长&#x…
阅读更多...
使用 ABAP GIT 发生 IF_APACK_MANIFEST dump

使用 ABAP GIT 发生 IF_APACK_MANIFEST dump

错误重现 使用经典的 ABAP 系统运行 ZABAPGIT 或者 ZABAPGIT_STANDALONE然后添加在线或者离线项目点击 PullShort dump SYNTAX_ERROR Dump 界面&#xff1a; 解决方案 它发生在 CREATE OBJECT lo_manifest_provider TYPE (ls_manifest_implementation-clsname) 语句中。 该语…
阅读更多...
最新文章

Copyright @ 2022~2023