当前位置: 首页 > news >正文

简易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 的实现

封装&#xff1a; std::queue 在底层容器的基础上 提供了封装。默认情况下&#xff0c;std::queue 使用 std::deque 作为其底层容器&#xff0c;但也可以配置为使用 std::list 或 其他符合要求的容器 时间复杂度&#xff1a; 入队和出队操作 通常是 常数时间复杂度&#xff08…...

【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 仓库中的子模块&#xff08;submodules&#xff09;。这个命令在 Git 仓库中包含对其他 Git 仓库作为依赖时…...

面试问我LLM中的RAG,咱就是说秒过!!!

前言 本篇文章涉及了 RAG 流程中的数据拆分、向量化、查询重写、查询路由等等&#xff0c;在做 RAG 的小伙伴一定知道这些技巧的重要性。推荐仔细阅读&#xff0c;建议收藏&#xff0c;多读几遍&#xff0c;好好实践。 本文是对检索增强生成&#xff08;Retrieval Augmented …...

python程序操作pdf

python代码进行多个图片合并为pdf&#xff1a; #python代码进行多个图片合并为pdf&#xff1a; from PIL import Image from fpdf import FPDF import osdef images_to_pdf(image_paths, output_pdf, quality85):"""将多个图片合并为一个PDF文件&#xff0c;并…...

【Python报错】ImportError: DLL load failed while importing _network: 找不到指定的模块。

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

外包干了5天,技术明显退步

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

正则表达式 | Python、Julia 和 Shell 语法详解

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

JavaScript全面指南(一)

​ &#x1f308;个人主页&#xff1a;前端青山 &#x1f525;系列专栏&#xff1a;JavaScript篇 &#x1f516;人终将被年少不可得之物困其一生 依旧青山,本期给大家带来JavaScript篇专栏内容:JavaScript全面指南(一) 1、介绍一下JS的内置类型有哪些&#xff1f; 基本数据类型…...

docker-compose与docker

“docker-compose” 是一个用于定义和运行多容器 Docker 应用程序的工具。它使用一个名为 docker-compose.yml 的配置文件来描述应用程序的服务、网络和卷&#xff0c;然后通过简单的命令就可以管理整个应用。 以下是一些常用的 docker-compose 命令及其用法&#xff1a; 启动…...

DDPM浅析

在机器学习和人工智能领域&#xff0c;生成模型一直是一个备受关注的研究方向。近年来&#xff0c;一种新型的生成模型——扩散概率模型&#xff08;Diffusion Probabilistic Models&#xff0c;简称DDPM&#xff09;引起了广泛的关注。本文将探讨DDPM的原理、优势以及应用。 …...

力扣刷题-算法基础

hello各位小伙伴们,为了进行算法的学习,小编特意新开一个专题来讲解一些算法题 1.移除元素. - 力扣(LeetCode) 本题大概意思是给定一个数组和一个数val删除与val相同的元素,不要改变剩余元素的顺序,最后返回剩余元素的个数。 我们在这里使用双指针,这里的双指针并不是…...

理解 Python 中的 Hooks 和装饰器

Python 中的 hooks 和装饰器&#xff0c;虽然它们看起来都有些魔法加成&#xff0c;但实际上各有妙用。下面看看他们到底是做什么的吧。 什么是 Hooks&#xff1f; Hooks 是指在某些操作或事件发生时&#xff0c;可以将自定义的代码插入和执行的一种机制。它们常用于扩展和修…...

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&#xff08;GNU…...

PHP 函数 func_num_args() 的作用

func_num_args() 是 PHP 中的一个内置函数&#xff0c;用于获取传递给当前用户定义函数的参数个数。这个函数特别有用于处理可变数量的参数&#xff08;也称为可变参数列表&#xff09;。 语法 int func_num_args ( void ) 返回值 func_num_args() 返回一个整数&#xff0c…...

深入解析单片机原理及其物联网应用:附C#示例代码

深入解析单片机原理及其物联网应用&#xff1a;附C#示例代码 随着物联网技术的快速发展&#xff0c;单片机作为嵌入式系统的核心&#xff0c;已经广泛应用于各类智能设备中。本文将从单片机的原理出发&#xff0c;结合C#编程的物联网示例&#xff0c;带你深入了解如何利用单片…...

HTTP 和 WebSocket

目录 HTTP是什么HTTP局限性&#xff08;HTTP1.1&#xff09;请求和响应HTTP的主要特点&#xff1a;HTTP版本&#xff1a; HTTP与TCP关系数据封装传输过程1. **协议层次模型**&#xff1a;2. **封装过程**&#xff1a;1. **应用层&#xff08;HTTP&#xff09;**&#xff1a;2. …...

科技云报到:大模型时代下,向量数据库的野望

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

贪吃蛇游戏(代码篇)

我们并不是为了满足别人的期待而活着。 前言 这是我自己做的第五个小项目---贪吃蛇游戏&#xff08;代码篇&#xff09;。后期我会继续制作其他小项目并开源至博客上。 上一小项目是贪吃蛇游戏&#xff08;必备知识篇&#xff09;&#xff0c;没看过的同学可以去看看&#xf…...

数控走心机系统可以定制吗

当然&#xff0c;走心机系统是可以定制的。随着数控技术的不断发展&#xff0c;走心机的数控系统越来越灵活&#xff0c;可以根据用户的具体需求进行定制和优化。下面&#xff0c;我将从几个方面来详细解答这个问题&#xff1a; ‌一、系统定制的必要性‌ ‌1. 满足不同加工需求…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...

rm视觉学习1-自瞄部分

首先先感谢中南大学的开源&#xff0c;提供了很全面的思路&#xff0c;减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接&#xff1a;https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架&#xff1a; 代码框架结构&#xff1a;readme有…...