C++中stack和queue的模拟实现

目录

1.容器适配器  

1.1什么是适配器      

1.2STL标准库中stack和queue的底层结构

1.3deque的简单介绍

1.3.1deque的原理介绍 

1.3.2deque的优点和缺陷

1.3.3deque和vector进行排序的性能对比

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

2.stack的介绍和模拟实现

2.1stack的介绍

2.2stack的模拟实现 

2.2.1传统栈的结构

2.2.2利用vector作为stack的底层容器 

 2.2.3模板中加一个容器类型参数，实现不同容器作为stack的底层容器

3.queue的介绍和模拟实现 

3.1queue的介绍

3.2queue的模拟实现 

3.2.1传统队列的结构

3.2.2利用list作为queue的底层容器 

3.2.3模板中加一个容器类型参数，实现不同容器作为queue的底层容器 

1.容器适配器  

1.1什么是适配器      

        适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另一个接口。

        如上图，需要将两个插口的插头转换为插座能使用的三个插口的插头，就需要一个适配器进行转换，适配器也可以叫做转换器。

1.2STL标准库中stack和queue的底层结构

        虽然stack和queue中也可以存放元素，但是STL中并没有将其划分在容器的行列，而是将其称为容器适配器,这里因为stack和queue只是对其他容器的接口进行了包装，所以stack和queue相当于上述三个抽口的插头，底层容器相当于两个插口的插头，用户需要一个stack或queue的结构，就调用其他的底层容器来弄出一个stack或queue,比如：

1.3deque的简单介绍

1.3.1deque的原理介绍 

        deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两段进行插入和删除操作(普通队列只能在一段插入另一端删除),且时间复杂度为O(1).与vector相比，头插效率高，不需要挪动元素；与list相比，空间利用率高。

        deque并不是真正连续的空间，而是由一段段小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示： 

        双端队列底层是一段假想的连续空间，实际是分段连续的，为了维护其"整体连续"以及随机访问的假想，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂,如下图所示: 

        如上图，deque的存储空间放在一个中控器(可以理解为内存中开辟的一块用于存储deque里面数据的空间)里面，里面的每一方框就是一个缓冲器(这里的缓冲区相当于二维数组的每一行)。上述表明deque的迭代器中有4个东西：(1)node：表示指向的是哪一个缓冲区(相当于表面指向二维数组里面的哪一行)。(2)cur：表面在这个缓冲区的位置。(3)first和last：记录该缓冲区的起始位置和结束位置。具体怎么进行维护的这里就不过多的进行介绍了。

1.3.2deque的优点和缺陷

(1)优点：与vector相比，deque的优势是：头部的插入和删除时，不需要挪动元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此在头部进行插入和删除效率比vector高。与list相比，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

(2)缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某一小空间的边界，导致效率低下，而序列场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，而目前能看到的一个应用就是STL中作为stack和queue的底层数据结构。

1.3.3deque和vector进行排序的性能对比

        这里在vs2022的Release下对vector和deque进行排序的性能比较，第一个是分别在各自容器中进行排序之后时间消耗的比较，第二个是将deque中的数据copy到vector进行排序后返回到deque中与deque中自己排序的时间消耗进行比较。

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;void test_op1()
{srand(time(0));const int N = 1000000;deque<int> dq;vector<int> v;for (int i = 0; i < N; i++){auto e = rand() + i;v.push_back(e);dq.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();sort(dq.begin(), dq.end());int end2 = clock();cout << "vector: " << end1 - begin1 << endl;cout << "deque:  " << end2 - begin2 << endl;
}void test_op2()
{srand(time(0));const int N = 1000000;deque<int> dq1;deque<int> dq2;for (int i = 0; i < N; ++i){auto e = rand() + i;dq1.push_back(e);dq2.push_back(e);}int begin1 = clock();sort(dq1.begin(), dq1.end());int end1 = clock();int begin2 = clock();// 拷贝到vectorvector<int> v(dq2.begin(), dq2.end());sort(v.begin(), v.end());dq2.assign(v.begin(), v.end());int end2 = clock();printf("deque sort:%d\n", end1 - begin1);printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}int main()
{test_op1();test_op2();return 0;
}

1.4为什么选择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不仅效率高，而且内存使用率高。

2.stack的介绍和模拟实现

2.1stack的介绍

2.2stack的模拟实现 

2.2.1传统栈的结构

template <class T>
class Stack
{
private:T* _a;    //用数组存储元素size_t _top;size_t _capacity;
};

2.2.2利用vector作为stack的底层容器 

        这里在stack类里面有一个vector的对象，所有的stack接口通过调用vector的接口进行实现。

namespace XiaoC
{template<class T>class stack{public://会调用vector的构造函数进行构造stack(){}void push(const T& x){_c.push_back(x);	//调用vector的push_back接口}void pop(){_c.pop_back();}//取栈顶元素T& top() const{return _c.back();}size_t size() const{return _c.size();}bool empty() const{return _c.empty();}private:std::vector<T> _c;};
}

 2.2.3模板中加一个容器类型参数，实现不同容器作为stack的底层容器

        这里默认给的容器是deque,对于stack来说只要支持push_back()和pop_back()线性结构容器就能用来当作底层容器。

#pragma once
#include <deque>
namespace XiaoC
{template <class T, class Container = deque<T>>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{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

3.queue的介绍和模拟实现 

3.1queue的介绍

3.2queue的模拟实现 

3.2.1传统队列的结构

// 链式结构：表示队列中每个节点的结构
typedef struct QListNode
{ struct QListNode* _pNext; QDataType _data; 
}QNode;// 队列的结构，用两个指针来维护一个队列
typedef struct Queue
{ QNode* _front; QNode* _rear; 
}Queue;

3.2.2利用list作为queue的底层容器 

         这里queue里面有一个list对象，所有queue的接口通过调用list的接口进行实现。

#pragma once
#include <deque>namespace XiaoC
{template<class T>class queue{public:queue(){}void empty(){return _c.empty();}void size(){return _c.size();}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_front();}T& front(){return _c.front();}const T& front(){return _c.front();}T& back(){return _c.back();}const T& back() const{return _c.back();}private:std::list<T> _c;};
}

3.2.3模板中加一个容器类型参数，实现不同容器作为queue的底层容器 

        这里默认给的容器是deque,对于queue来说只要支持push_back()和pop_front()线性结构容器就能用来当作底层容器。

namespace XiaoC
{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;};
}

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

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

相关文章

数据库第8章编程题2

数据库第8章编程题2

10-1 查询选修某两门课程的学生&#xff08;MSSQL) 本题目要求编写SQL语句&#xff0c; 检索出 sc表中至少选修了’C001’与’C002’课程的学生学号。 提示&#xff1a;MSSQLServer 评测SQL语句。 表结构: 请在这里写定义表结构的SQL语句。例如&#xff1a; -- 学生选课成…
阅读更多...
前端组件化开发

前端组件化开发

假设这个页面是vue开发的&#xff0c;如果一整个页面都是编写在一个vue文件里面&#xff0c;后期不好维护&#xff0c;会特别的庞大&#xff0c;那么如何这个时候需要进行组件化开发。组件化开发后必然会带来一个问题需要进行组件之间的通信。组要是父子组件之间通信&#xff0…
阅读更多...
SuperMap iClient for MapLibreGL 根据SQL条件过滤显示动态图层

SuperMap iClient for MapLibreGL 根据SQL条件过滤显示动态图层

查阅发现iClient 有子图层控制类 LayerStatus 可实现&#xff1a;子图层显示参数类。此类存储了各个子图层的名称、是否可见的状态、SQL 过滤条件等参数。 API详情&#xff1a;http://support.supermap.com.cn:8090/iserver/iClient/forJavaScript/docs/maplibregl/LayerStatus…
阅读更多...
Kafka和RabbitMQ区别

Kafka和RabbitMQ区别

RabbitMQ的消息延迟是微秒级&#xff0c;Kafka是毫秒级&#xff08;1毫秒1000微秒&#xff09; 延迟消息是指生产者发送消息发送消息后&#xff0c;不能立刻被消费者消费&#xff0c;需要等待指定的时间后才可以被消费。 Kafka的单机呑吐量是十万级&#xff0c;RabbitMQ是万级…
阅读更多...
Webpack模式-Resolve-本地服务器

Webpack模式-Resolve-本地服务器

目录 ResolveMode配置搭本地服务器区分环境配置 Resolve 前面学习时使用了各种各样的模块依赖&#xff0c;这些模块可能来自于自己编写的代码&#xff0c;也可能来自第三方库&#xff0c;在 Webpack 中&#xff0c;resolve 是用于解析模块依赖的配置项&#xff0c;它决定了 We…
阅读更多...
特权访问管理阻力最小的途径

特权访问管理阻力最小的途径

特权访问管理 (PAM) 已经存在 20 多年&#xff0c;它将关键帐户放入保险库中&#xff0c;以确保只有特定人员才能安全地访问它们。 从那时起&#xff0c;PAM 不断发展&#xff0c;现在专注于控制访问本身&#xff0c;这意味着防止广泛访问特定数据&#xff0c;并提供有关谁有访…
阅读更多...
JS基础练习|点击按钮更改背景色

JS基础练习|点击按钮更改背景色

效果图 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title><link rel"…
阅读更多...
《易泊车牌识别相机：精准识别的智能之选》

《易泊车牌识别相机：精准识别的智能之选》

在如今的智能交通领域&#xff0c;车牌识别技术起着至关重要的作用。而易泊车牌识别相机以其卓越的性能脱颖而出。 易泊车牌识别相机的识别率极高。无论是在白天还是夜晚&#xff0c;无论是清晰的车牌还是稍有磨损的车牌&#xff0c;它都能迅速准确地识别出车牌号码。这得益于其…
阅读更多...
多区域OSPF路由协议

多区域OSPF路由协议

前言 之前也有过关于OSPF路由协议的博客&#xff0c;但都不是很满意&#xff0c;不是很完整。现在也是听老师讲解完OSPF路由协议&#xff0c;感触良多&#xff0c;所以这里重新整理一遍。这次应该是会满意的 一些相关概念 链路状态 链路指路由器上的一个接口&#xff0c;链路状…
阅读更多...
C++ | Leetcode C++题解之第452题用最少数量的箭引爆气球

C++ | Leetcode C++题解之第452题用最少数量的箭引爆气球

题目&#xff1a; 题解&#xff1a; class Solution { public:int findMinArrowShots(vector<vector<int>>& points) {if (points.empty()) {return 0;}sort(points.begin(), points.end(), [](const vector<int>& u, const vector<int>&…
阅读更多...
【重学 MySQL】五十一、更新和删除数据

【重学 MySQL】五十一、更新和删除数据

【重学 MySQL】五十一、更新和删除数据 更新数据删除数据注意事项 在MySQL中&#xff0c;更新和删除数据是数据库管理的基本操作。 更新数据 为了更新&#xff08;修改&#xff09;表中的数据&#xff0c;可使用UPDATE语句。UPDATE语句的基本语法如下&#xff1a; UPDATE ta…
阅读更多...
秒懂Linux之线程

秒懂Linux之线程

目录 线程概念 线程理解 地址空间&#xff08;页表&#xff0c;内存&#xff0c;虚拟地址&#xff09; 线程的控制 铺垫 线程创建 ​编辑 线程等待 线程异常 线程终止 代码 线程优点 线程缺点 线程特点 线程概念 线程是进程内部的一个执行分支&#xff0c;线程是C…
阅读更多...
【转载翻译】消息队列 - ActiveMQ、RabbitMQ、Kafka、ZeroMQ

【转载翻译】消息队列 - ActiveMQ、RabbitMQ、Kafka、ZeroMQ

转载自本人博客&#xff1a;【转载翻译】消息队列 - ActiveMQ、RabbitMQ、Kafka、ZeroMQ 转载自&#xff1a;The System Design Cheat Sheet: Message Queues - ActiveMQ, RabbitMQ, Kafka, ZeroMQ 本文由 Aleksandr Gavrilenko 发布于2023年12月21日 1. 前言 消息队列是异步服…
阅读更多...
TypeScript 算法手册 【归并排序】

TypeScript 算法手册 【归并排序】

文章目录 1. 归并排序简介1.1 归并排序定义1.2 归并排序特点 2. 归并排序步骤过程拆解2.1 分割数组2.2 递归排序2.3 合并有序数组 3. 归并排序的优化3.1 原地归并排序3.2 混合插入排序案例代码和动态图 4. 归并排序的优点5. 归并排序的缺点总结 【 已更新完 TypeScript 设计模式…
阅读更多...
酒店业CRM和酒店数据管理大数据—未来之窗行业应用跨平台架构

酒店业CRM和酒店数据管理大数据—未来之窗行业应用跨平台架构

一酒店架构图 二、客户数据 三、客户数据源
阅读更多...
Java | Leetcode Java题解之第452题用最少数量的箭引爆气球

Java | Leetcode Java题解之第452题用最少数量的箭引爆气球

题目&#xff1a; 题解&#xff1a; class Solution {public int findMinArrowShots(int[][] points) {if (points.length 0) {return 0;}Arrays.sort(points, new Comparator<int[]>() {public int compare(int[] point1, int[] point2) {if (point1[1] > point2[1…
阅读更多...
STM32-MPU6050+DAM库源码（江协笔记）

STM32-MPU6050+DAM库源码（江协笔记）

目录 1、MPU6050简介 2、MPU6050参数 3、MPU6050硬件电路 4、MPU6050结构 5、MPU6000和MPU6050的区别 6、MPU6050应用场景 7、MPU6050电气参数 8、MPU6050时钟源选择 9、MPU6050中断源 10、MPU6050的I2C读写操作 11、DMP库移植 1、MPU6050简介 10轴传感器&#xff1…
阅读更多...
AS-REP Roasting 实验

AS-REP Roasting 实验

1. 实验网络拓扑 kali: 192.168.72.128win2008: 192.168.135.129 192.168.72.139win7: 192.168.72.149win2012:(DC) 192.168.72.131 2. 攻击原理 如果设置了不需要Kerberos预认证&#xff1a; 那么就可以直接发AS_REQ请求TGT票据&#xff0c;由于不要求预身份认证&#xff0…
阅读更多...
Golang | Leetcode Golang题解之第453题最小操作次数使数组元素相等

Golang | Leetcode Golang题解之第453题最小操作次数使数组元素相等

题目&#xff1a; 题解&#xff1a; func minMoves(nums []int) (ans int) {min : nums[0]for _, num : range nums[1:] {if num < min {min num}}for _, num : range nums {ans num - min}return }
阅读更多...
awd基础学习

awd基础学习

一、常用防御手段 1、改ssh密码 passwd [user] 2、改数据库密码 进入数据库 mysql -uroot -proot 改密码 update mysql.user set passwordpassword(新密码) where userroot; 查看用户信息密码 select host,user,password from mysql.user; 改配置文件 &#xff08;否则会宕机…
阅读更多...
最新文章

Copyright @ 2022~2023