简易STL实现 | Queue 的实现
封装: std::queue 在底层容器的基础上 提供了封装。默认情况下,std::queue 使用 std::deque 作为其底层容器,但也可以配置为使用 std::list 或 其他符合要求的容器
时间复杂度: 入队和出队操作 通常是 常数时间复杂度(O(1)),这意味着 操作的时间不会随着队列大小的增加 而显著增加
空间复杂度: 由于 std::queue 使用底层容器来存储元素,其空间复杂度 取决于 所使用的底层容器
例如,使用 std::deque 时,空间复杂度通常是线性的(O(n)),其中 n 是队列中元素的数量
1、实现
template <typename T, typename Container = std::deque<T>>
class MyQueue {
private:Container data; // 使用底层容器存储队列的元素public:// 将元素添加到队尾void push(const T& value) {data.push_back(value);}// 移除队头元素void pop() {if (!empty()) {data.pop_front();} else {throw std::runtime_error("Queue is empty.");}}// 访问队头元素的引用T& front() {if (!empty()) {return data.front();} else {throw std::runtime_error("Queue is empty.");}}// 访问队尾元素的引用T& back() {if (!empty()) {return data.back();} else {throw std::runtime_error("Queue is empty.");}}// 检查队列是否为空bool empty() const {return data.empty();}// 返回队列的大小size_t size() const {return data.size();}
};
2、常见面试题
1、阻塞队列 在队列为空时 会阻塞出队操作,在队列满时 会阻塞入队操作。非阻塞队列 不会阻塞线程;如果 操作不能立即进行,则会失败 或 返回特定值
2、循环队列的实现
循环队列 可以使用 一个固定大小的数组 和 两个指针(头指针和尾指针,前闭后闭)来实现。当尾指针到达数组的末尾时,它会循环回到数组的开始位置。循环队列的优势 在于它可以重复使用空间,减少了 因为扩容而带来的性能开销
所有 + 的地方 要加上 % size
有两个重要条件:
队列为空:当 front == -1
队列已满:当 (rear + 1) % size == front
#include <iostream>
using namespace std;class CircularQueue {
private:int *queue; // 动态数组存储队列元素int front; // 指向队列头部的索引int rear; // 指向队列尾部的索引int size; // 队列容量public:// 构造函数,初始化队列CircularQueue(int maxSize) {size = maxSize;queue = new int[size];front = -1;rear = -1;}// 析构函数,释放动态内存~CircularQueue() {delete[] queue;}// 检查队列是否为空bool isEmpty() {return (front == -1);}// 检查队列是否已满bool isFull() {return ((rear + 1) % size == front);}// 向队列中插入元素void enqueue(int value) {if (isFull()) {cout << "队列已满,无法插入元素 " << value << endl;return;}if (isEmpty()) {front = 0; // 如果队列为空,则插入第一个元素时将 front 指向 0}rear = (rear + 1) % size; // 更新 rear 为下一个位置(循环)queue[rear] = value;cout << "插入元素: " << value << endl;}// 从队列中删除元素int dequeue() {if (isEmpty()) {cout << "队列为空,无法删除元素" << endl;return -1;}int value = queue[front];if (front == rear) {// 队列中只有一个元素,删除后队列为空front = -1;rear = -1;} else {// 更新 front 为下一个位置(循环)front = (front + 1) % size;}cout << "删除元素: " << value << endl;return value;}// 获取队列头部的元素int peekFront() {if (isEmpty()) {cout << "队列为空,无法获取头部元素" << endl;return -1;}return queue[front];}// 获取队列尾部的元素int peekRear() {if (isEmpty()) {cout << "队列为空,无法获取尾部元素" << endl;return -1;}return queue[rear];}// 显示队列中的元素void displayQueue() {if (isEmpty()) {cout << "队列为空" << endl;return;}cout << "队列元素: ";int i = front;while (true) {cout << queue[i] << " ";if (i == rear) {break;}i = (i + 1) % size;}cout << endl;}
};
https://kamacoder.com/ 手写简单版本STL,内容在此基础上整理补充
相关文章:
简易STL实现 | Queue 的实现
封装: std::queue 在底层容器的基础上 提供了封装。默认情况下,std::queue 使用 std::deque 作为其底层容器,但也可以配置为使用 std::list 或 其他符合要求的容器 时间复杂度: 入队和出队操作 通常是 常数时间复杂度(…...

【hot100-java】LRU 缓存
链表篇 灵神题解 class LRUCache {private static class Node{int key,value;Node prev,next;Node (int k,int v){keyk;valuev;}}private final int capacity;//哨兵节点private final Node dummynew Node(0,0);private final Map<Integer,Node> keyToNode new HashMap&l…...

Centos7安装ZLMediaKit
一 获取代码 git clone https://gitee.com/xia-chu/ZLMediaKit cd ZLMediaKit git submodule update --init git submodule update --init 命令用于初始化和更新 Git 仓库中的子模块(submodules)。这个命令在 Git 仓库中包含对其他 Git 仓库作为依赖时…...

面试问我LLM中的RAG,咱就是说秒过!!!
前言 本篇文章涉及了 RAG 流程中的数据拆分、向量化、查询重写、查询路由等等,在做 RAG 的小伙伴一定知道这些技巧的重要性。推荐仔细阅读,建议收藏,多读几遍,好好实践。 本文是对检索增强生成(Retrieval Augmented …...
python程序操作pdf
python代码进行多个图片合并为pdf: #python代码进行多个图片合并为pdf: from PIL import Image from fpdf import FPDF import osdef images_to_pdf(image_paths, output_pdf, quality85):"""将多个图片合并为一个PDF文件,并…...

【Python报错】ImportError: DLL load failed while importing _network: 找不到指定的模块。
【Python报错】ImportError: DLL load failed while importing _network: 找不到指定的模块。 问题描述报错原因解决方案参考 问题描述 此段Python代码(在Conda环境下运行)昨天还能运行,但在我手痒更新conda(我有罪)之…...

外包干了5天,技术明显退步
我是一名本科生,自2019年起,我便在南京某软件公司担任功能测试的工作。这份工作虽然稳定,但日复一日的重复性工作让我逐渐陷入了舒适区,失去了前进的动力。两年的时光匆匆流逝,我却在原地踏步,技术没有丝毫…...

正则表达式 | Python、Julia 和 Shell 语法详解
正则表达式在网页爬虫、脚本编写等众多任务中都有重要的应用。为了系统梳理其语法,以及 Python、Julia 和 Shell 中与正则表达式相关的工具,本篇将进行详细介绍。 相关学习资源:编程胶囊。 基础语法 通用语法 在大多数支持正则表达式的语…...

JavaScript全面指南(一)
🌈个人主页:前端青山 🔥系列专栏:JavaScript篇 🔖人终将被年少不可得之物困其一生 依旧青山,本期给大家带来JavaScript篇专栏内容:JavaScript全面指南(一) 1、介绍一下JS的内置类型有哪些? 基本数据类型…...
docker-compose与docker
“docker-compose” 是一个用于定义和运行多容器 Docker 应用程序的工具。它使用一个名为 docker-compose.yml 的配置文件来描述应用程序的服务、网络和卷,然后通过简单的命令就可以管理整个应用。 以下是一些常用的 docker-compose 命令及其用法: 启动…...
DDPM浅析
在机器学习和人工智能领域,生成模型一直是一个备受关注的研究方向。近年来,一种新型的生成模型——扩散概率模型(Diffusion Probabilistic Models,简称DDPM)引起了广泛的关注。本文将探讨DDPM的原理、优势以及应用。 …...

力扣刷题-算法基础
hello各位小伙伴们,为了进行算法的学习,小编特意新开一个专题来讲解一些算法题 1.移除元素. - 力扣(LeetCode) 本题大概意思是给定一个数组和一个数val删除与val相同的元素,不要改变剩余元素的顺序,最后返回剩余元素的个数。 我们在这里使用双指针,这里的双指针并不是…...
理解 Python 中的 Hooks 和装饰器
Python 中的 hooks 和装饰器,虽然它们看起来都有些魔法加成,但实际上各有妙用。下面看看他们到底是做什么的吧。 什么是 Hooks? Hooks 是指在某些操作或事件发生时,可以将自定义的代码插入和执行的一种机制。它们常用于扩展和修…...
Android 原生程序使用gdb, addr2line, readelf调试
Platform: RK3368 OS: Android 6.0 Kernel: 3.10.0 文章目录 一 gdb1. 原生程序添加调试符号2. 主机上adb push 编译好的原生程序到设备3. 设备上使用gdbserver运行原生程序4. 主机上设置adb端口转发5. 主机上运行gdb调试 二 addr2line三 readelf 一 gdb GDB(GNU…...
PHP 函数 func_num_args() 的作用
func_num_args() 是 PHP 中的一个内置函数,用于获取传递给当前用户定义函数的参数个数。这个函数特别有用于处理可变数量的参数(也称为可变参数列表)。 语法 int func_num_args ( void ) 返回值 func_num_args() 返回一个整数,…...
深入解析单片机原理及其物联网应用:附C#示例代码
深入解析单片机原理及其物联网应用:附C#示例代码 随着物联网技术的快速发展,单片机作为嵌入式系统的核心,已经广泛应用于各类智能设备中。本文将从单片机的原理出发,结合C#编程的物联网示例,带你深入了解如何利用单片…...
HTTP 和 WebSocket
目录 HTTP是什么HTTP局限性(HTTP1.1)请求和响应HTTP的主要特点:HTTP版本: HTTP与TCP关系数据封装传输过程1. **协议层次模型**:2. **封装过程**:1. **应用层(HTTP)**:2. …...

科技云报到:大模型时代下,向量数据库的野望
科技云报到原创。 自ChatGPT爆火,国内头部平台型公司一拥而上,先后发布AGI或垂类LLM,但鲜有大模型基础设施在数据层面的进化,比如向量数据库。 在此之前,向量数据库经历了几年的沉寂期,现在似乎终于乘着Ch…...

贪吃蛇游戏(代码篇)
我们并不是为了满足别人的期待而活着。 前言 这是我自己做的第五个小项目---贪吃蛇游戏(代码篇)。后期我会继续制作其他小项目并开源至博客上。 上一小项目是贪吃蛇游戏(必备知识篇),没看过的同学可以去看看…...
数控走心机系统可以定制吗
当然,走心机系统是可以定制的。随着数控技术的不断发展,走心机的数控系统越来越灵活,可以根据用户的具体需求进行定制和优化。下面,我将从几个方面来详细解答这个问题: 一、系统定制的必要性 1. 满足不同加工需求…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...

图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...