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.rhkb.cn/news/465176.html

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

相关文章

vue3动态监听div高度案例

vue3动态监听div高度案例

案例场景 场景描述&#xff1a;现在左边的线条长度需要根据右边盒子的高度进行动态变化 实践代码案例 HTML部分 <div v-for"(device, index) in devices" :key"index"><!-- 动态设置 .left-bar 的高度 --><div class"left-bar"…
阅读更多...
华为OD机试真题（Python/JS/C/C++）- 考点 - 细节

华为OD机试真题（Python/JS/C/C++）- 考点 - 细节

华为OD机试 2024E卷题库疯狂收录中&#xff0c;刷题 点这里。 本专栏收录于《华为OD机试真题&#xff08;Python/JS/C/C&#xff09;》。
阅读更多...
Spring源码学习（五）：Spring AOP

Spring源码学习（五）：Spring AOP

免责声明 本人还处于学习阶段&#xff0c;如果内容有错误麻烦指出&#xff0c;敬请见谅&#xff01;&#xff01;&#xff01;Demo <dependency><groupId>org.aspectj</groupId><artifactId>aspectjweaver</artifactId><version>1.8.8<…
阅读更多...
vue 使用docx-preview 预览替换文档内的特定变量

vue 使用docx-preview 预览替换文档内的特定变量

在开发合同管理中&#xff0c;需要使用到此功能&#xff0c;就是替换合同模板内的一些字符串&#xff0c;如&#xff1a;甲乙方名称&#xff0c;金额日期等&#xff0c;合同内容不变。效果如下&#xff1a; 使用docx-preview 好处是只预览不可编辑内容。 前端vue import { re…
阅读更多...
若依项目搭建

若依项目搭建

若依的大版本 基本环境搭建 搭建注意点
阅读更多...
（11）(2.1.6) Hobbywing DroneCAN ESC（二）

（11）(2.1.6) Hobbywing DroneCAN ESC（二）

文章目录 前言 2 配置ESC 3 测试 4 设置视频 5 参数说明 前言 具有 CAN 接口&#xff08;including these&#xff09;的业余 ESC 支持 DroneCAN&#xff0c;它允许自动驾驶仪通过 CAN 控制 ESC /电机&#xff0c;并检索单个转速、电压、电流和温度。 2 配置ESC 默认情…
阅读更多...
JVM结构图

JVM结构图

JVM&#xff08;Java虚拟机&#xff09;是Java编程语言的核心组件之一&#xff0c;负责将Java字节码翻译成机器码并执行。JVM由多个子系统组成&#xff0c;包括类加载子系统、运行时数据区、执行引擎、Java本地接口和本地方法库。 类加载子系统&#xff08;Class Loading Subsy…
阅读更多...
【智能算法改进】混沌映射策略--一网打尽

【智能算法改进】混沌映射策略--一网打尽

摘要 本文研究了多种混沌映射策略在智能算法中的改进效果&#xff0c;提出了一种综合不同混沌映射策略的多元混合方法&#xff0c;以提高算法的全局优化能力和收敛速度。通过引入不同的混沌映射&#xff08;如 Logistic、Tent、Sine 等&#xff09;生成初始种群分布&#xff0…
阅读更多...
QML —— QML调用C++两种方法（附完整测试源码）

QML —— QML调用C++两种方法（附完整测试源码）

代码效果 说明 QML 其实是对JavaScript 的扩展，融合了Qt Object 系统，它是一种新的解释型的语言， QML 引擎虽然由Qt C++ 实现，但QML 对象的运行环境，说到底和C++ 对象的上下文环境是不同的，是平行的两个世界。如果你想在QML 中访问C++ 对象，那么必然要找到一种途径来在两…
阅读更多...
剧本杀小程序，市场发展下的新机遇

剧本杀小程序，市场发展下的新机遇

剧本杀作为休闲娱乐的一种游戏方式&#xff0c;在短时间内进入了大众视野中&#xff0c;受到了广泛关注。近几年&#xff0c;剧本杀行业面临着创新挑战&#xff0c;商家需求寻求新的发展机遇&#xff0c;在市场饱和度下降的趋势下&#xff0c;获得市场份额。 随着科技的不断进…
阅读更多...
mysql error：1449权限问题 及 用户授权

mysql error：1449权限问题 及 用户授权

一、权限问题 Got error: 1449: The user specified as a definer (skip-grants userskip-grants host) does not exist when using LOCK TABLES 在迁移数据库时&#xff0c;定义的definer&#xff0c;在两个数据库之间不同步时&#xff0c;要将不存在的definer改成数据库中已…
阅读更多...
Spark 的Standalone集群环境安装与测试

Spark 的Standalone集群环境安装与测试

目录 一、Standalone 集群环境安装 &#xff08;一&#xff09;理解 Standalone 集群架构 &#xff08;二&#xff09;Standalone 集群部署 二、打开监控界面 &#xff08;一&#xff09;master监控界面 &#xff08;二&#xff09;日志服务监控界面 三、集群的测试 &a…
阅读更多...
基于SpringBoot+Vue实现新零售商城系统

基于SpringBoot+Vue实现新零售商城系统

作者主页&#xff1a;编程千纸鹤 作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验&#xff0c;被多个学校常年聘为校外企业导师&#xff0c;指导学生毕业设计并参…
阅读更多...
SAP RFC 用户安全授权

SAP RFC 用户安全授权

一、SAP 通讯用户 对于RFC接口的用户&#xff0c;使用五种用户类型之一的“通讯”类型&#xff0c;这种类型的用户没有登陆SAPGUI的权限。 二、对调用的RFC授权 在通讯用户内部&#xff0c;权限对象&#xff1a;S_RFC中&#xff0c;限制进一步可以调用的RFC函数授权&#xff…
阅读更多...
【Java Web】搭建Web环境以及初识JSP Tomcat

【Java Web】搭建Web环境以及初识JSP Tomcat

文章目录 程序架构Web服务器TomcatJSP概述主要特点基本语法综合示例程序调试和排错 代码示例 程序架构 C/S&#xff08;Client/Server&#xff0c;客户端/服务器&#xff09;和 B/S&#xff08;Browser/Server&#xff0c;浏览器/服务器&#xff09;是两种常见的软件系统架构模…
阅读更多...
如何建购物网站提升用户体验

如何建购物网站提升用户体验

在构建一个购物网站时&#xff0c;用户体验是至关重要的&#xff0c;它直接影响到顾客的满意度和转化率。为了提升用户体验&#xff0c;可以从以下几个方面入手。 首先&#xff0c;网站设计应简洁明了。确保导航栏清晰易懂&#xff0c;让用户在寻找商品时不会迷失。此外&#x…
阅读更多...
qt QTableView详解

qt QTableView详解

1、概述 QTableView 是 Qt 框架中的一个高级视图类&#xff0c;用于以表格形式展示二维数据。它基于 QAbstractItemView&#xff0c;并与模型&#xff08;通常是 QAbstractTableModel 或 QStandardItemModel&#xff09;结合使用&#xff0c;以实现数据的展示和交互。QTableVi…
阅读更多...
Android TextView自动换行文本显示不全解决

Android TextView自动换行文本显示不全解决

某些情况下&#xff0c;TextView自动换行后&#xff0c;会出现每行结尾处显示不全的问题&#xff0c; 如图&#xff1a; 常见解决方案&#xff1a; 设置TextView的“ellipsize”属性为“end” 实测无效&#xff01;将TextView外部的Layout改为RelativeLayout 实测无效&…
阅读更多...
Rust 力扣 - 1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

Rust 力扣 - 1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 长度为k的二进制子串所有取值的集合为[0, sum(k)]&#xff0c;其中sum(k)为1 2 4 … 1 << (k - 1) 我们只需要创建一个长度为sum(k) 1的数组 f &#xff0c;其中下标为 i 的元素用来标记字符串中子串…
阅读更多...
typescript的简介

typescript的简介

简介 tsc npm install -g typescripttsc -v作用 检查类型和语法错误&#xff0c;提前纠错 ts的类型 如何穿件带有ts的vue工程 作用 常见类型 用法 编写一个ts文件 let username:string "John";let age:number 25;let isUpdated:boolean true;let data:any &q…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023