队列的使用以及模拟实现(C++版本)

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中)
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:讲解队列的使用以及模拟实现
金句分享:
✨来日方长,未来是星辰大海般璀璨,✨
✨不必踌躇于过去的半亩方塘.✨

目录

  • 一、队列的介绍
  • 二、队列的使用
    • 🍭练练手(用队列模拟栈)
  • 三、队列的模拟实现:
    • (1) 浅提一下双端队列`deque`
    • (2) 模拟实现

一、队列的介绍

C++中的队列是一种容器,使用队列可以实现先进先出(FIFO)的数据结构。队列可以添加元素到队列的末尾,也可以从队列的开头删除元素。
队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的
成员函数来访问其元素。元素从队尾入队列,从队头出队列。
C++中的队列通常使用STL库中的queue类实现。

队列的基本操作包括:

  • push(element):将元素插入队列的末尾。
  • pop():将队列的第一个元素删除。
  • front():返回队列的第一个元素。
  • back():返回队列的最后一个元素。
  • empty():判断队列是否为空。

队列具有先进先出FIFO(First In First Out)

入队列:进行"插入"操作的一端称为队尾
出队列:进行"删除"操作的一端称为队头

在这里插入图片描述

二、队列的使用

文档链接

在这里插入图片描述

接口名解释
empty()判断是否为空队列
size()返回队列中有效元素的个数
front()返回队首元素的引用
back()返回队尾元素的引用
push()将新元素入队列
emplace()将新元素入队列
pop()将队首元素出队

相信大家对队列的基本操作十分简单,下面演示一下具体使用,使用十分简单,就不过分介绍了.

测试代码:

#include <iostream>
#include <queue>
using namespace std;void test1()
{queue<int> q1;//创建一个存储整形数据的队列q1.push(1);	//入队列q1.push(2);q1.push(3);q1.emplace(4);	//在stack使用时有详细介绍cout << "q1.front=" << q1.front() << endl;	//取队头元素cout << "q1.back=" << q1.back() << endl;	//取队尾元素//利用front的返回值,修改队首元素int& top = q1.front();top = 22;//利用back的返回值,修改队尾元素int& back = q1.back();top = -22;cout << endl;while (!q1.empty())		//只要队列不为空,就打印队头元素和出队列{cout << q1.front() << endl;q1.pop();//出队列}
}int main()
{test1();return 0;
}

运行结果:

q1.front=1
q1.back=4
22
2
3
4

🍭练练手(用队列模拟栈)

题目链接:

同样,在C语言阶段,我们已经"十分痛苦"的写过这道题,现在C++阶段,再来写要轻松很多了.

用队列实现栈(C语言版本)

C++实现版本:

class MyStack {
public:MyStack() {}void push(int x) {if (!(q1.empty() && q2.empty())) {//往空栈里面插入数据q1.push(x);}else q2.push(x);}int pop() {queue<int>* empty_q ;queue<int>* un_empty_q;if (q1.empty()) {//找到两个队列中的空队列empty_q = &q1;un_empty_q = &q2;}else {empty_q = &q2;un_empty_q = &q1;}while (un_empty_q->size() > 1) {//将非空队列除了最后一个元素以外,其他全部插入到另一个队列empty_q->push(un_empty_q->front());un_empty_q->pop();}int front = un_empty_q->front();un_empty_q->pop();//删除剩下的最后一个元素->return front;}int top() {int top;if (q1.empty()) {top = q2.back();}else  top = q1.back();return top;}bool empty() {return q1.empty() && q2.empty();}
private:queue<int> q1;queue<int> q2;
};

三、队列的模拟实现:

(1) 浅提一下双端队列deque

在介绍队列的,模拟实现前,先介绍一下deque.
双端队列(Double-Ended Queue),是一种具有队列和栈的特点的数据结构。它允许从两端插入和删除元素,具有以下特点:

  1. 可以从队列两端进行插入和删除操作。
  2. 支持常数级别的访问和修改元素,即在队列头和尾进行操作的时间复杂度都为O(1)。
  3. 在中间进行操作时,性能较差,时间复杂度为O(n)。

是的,这个双端队列不仅支持头插头删,尾插尾删的同时,还支持随机访问.
那这不就意味着链表listvector都被淘汰了吗?
这里就不过多介绍deque的底层了,我们可以暂时理解为,类似于链表,但是链接起来的是一个个数组,这样就实现了这些功能.
但是,他并不能代替链表listvector.原因如下:

vector比较
deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不
需要搬移大量的元素
劣势:但是它的访问需要计算,在大量访问元素的场景时,与vector比就落后了.

list比较
优势:其底层是连续空间,空间利用率比较高,不需要存储额外字段。
缺点:deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多.

巧合的是,stackqueue都不需要访问中间的元素,访问头部数据效率还是很高的.
所以STLdeque作为stackqueue的底层数据结构再合适不过了.

(2) 模拟实现

队列也是一种容器适配器,我们底层采用deque实现还是很轻松的.

在这里插入图片描述

#pragma once
#include <iostream>
#include <deque>
using namespace std;namespace cjn
{template<class T, class Con = deque<T>>//默认采用deque进行复用class queue{public:queue(){}void push(const T& x){      //入队列元素相当于尾插_c.push_back(x);}void pop(){_c.pop_front();         //出队列是从队首元素出队,所以相当于头删}T& back(){                  //返回队尾元素return _c.back();}const T& back()const{return _c.back();}T& front(){                 //返回队首元素return _c.front();}const T& front()const{return _c.front();}size_t size()const{         //返回队列中有效元素的个数return _c.size();}bool empty()const{          //判断队列是否为空return _c.empty();}private:Con _c;};
}

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

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

相关文章

【每日一题】2703. 返回传递的参数的长度

2703. 返回传递的参数的长度 - 力扣&#xff08;LeetCode&#xff09; 请你编写一个函数 argumentsLength&#xff0c;返回传递给该函数的参数数量。 示例 1&#xff1a; 输入&#xff1a;args [5] 输出&#xff1a;1 解释&#xff1a; argumentsLength(5); // 1只传递了一个值…

OpenHarmony应用核心技术理念与需求机遇简析

一、核心技术理念 图片来源&#xff1a;OpenHarmony官方网站 二、需求机遇简析 新的万物互联智能世界代表着新规则、新赛道、新切入点、新财富机会;各WEB网站、客户端( 苹果APP、安卓APK)、微信小程序等上的组织、企业、商户等;OpenHarmony既是一次机遇、同时又是一次大的挑战&…

【python+appium】自动化测试

pythonappium自动化测试系列就要告一段落了&#xff0c;本篇博客咱们做个小结。 首先想要说明一下&#xff0c;APP自动化测试可能很多公司不用&#xff0c;但也是大部分自动化测试工程师、高级测试工程师岗位招聘信息上要求的&#xff0c;所以为了更好的待遇&#xff0c;我们还…

竞赛无人机搭积木式编程(四)---2023年TI电赛G题空地协同智能消防系统(无人机部分)

竞赛无人机搭积木式编程&#xff08;四&#xff09; ---2023年TI电赛G题空地协同智能消防系统&#xff08;无人机部分&#xff09; 无名小哥 2023年9月15日 赛题分析与解题思路综述 飞控用户在学习了TI电赛往届真题开源方案以及用户自定义航点自动飞行功能方案讲解后&#x…

从零学算法(LCR 191)

为了深入了解这些生物群体的生态特征&#xff0c;你们进行了大量的实地观察和数据采集。数组 arrayA 记录了各个生物群体数量数据&#xff0c;其中 arrayA[i] 表示第 i 个生物群体的数量。请返回一个数组 arrayB&#xff0c;该数组为基于数组 arrayA 中的数据计算得出的结果&am…

移动端和PC端对比【组件库+调试vconsole +单位postcss-pxtorem+构建vite/webpack+可视化echarts/antv】

目录 组件库 移动端 vue vant PC端 react antd vue element 调试&#xff1a;vconsole vs dev tools中的控制台&#xff08;Console&#xff09; vconsole&#xff1a;在真机上调试 postcss-pxtorem&#xff1a;移动端不同的像素密度 构建工具 webpack 原理 Ba…

Linux 进程层次分析

Linux 进程组 每个进程都有一个进程组号 (PGID) 进程组&#xff1a;一个或多个进程的集合 (集合中的进程并不孤立)进程组中的进程通常存在父子关系&#xff0c;兄弟关系&#xff0c;或功能相近 进程组可方便进程管理 (如&#xff1a;同时杀死多个进程&#xff0c;发送一个信…

RISC-V 基础指令汇总

加载指令 存储指令 PC寻址指令 auipc rd, imm这条指令把 imm &#xff08;立即数&#xff09;左移12位并带符号扩展到64位后&#xff0c;得到一个新的立即数&#xff0c;这个新的立即数是一个有符号的立即数&#xff0c;再加上当前 PC 值&#xff0c;然后存储到 rd 寄存器中。…

解释器风格架构C# 代码

/*解释器风格架构是一种基于组件的设计架构&#xff0c;它将应用程序分解为一系列组件&#xff0c;每个组件负责处理特定的任务。这种架构有助于提高代码的可维护性和可扩展性。以下是如何使用C#实现解释器风格架构的步骤&#xff1a;定义组件&#xff1a;首先&#xff0c;定义…

表的增删改查

文章目录 1. Create(创建)1.1 insert1.2 插入否则更新1.3 替换 2. Retrieve(查询)2.1 SELECT 列2.2 WHERE 条件2.3 结果排序2.4 筛选分页结果 3. Update(更新)4. Delete(删除)4.1 删除数据4.2 截断表 5. 插入查询结果 1. Create(创建) 1.1 insert 下面我们用这个表来操作&…

【算法分析与设计】动态规划(上)

目录 一、学习要点二、算法总体思想三、动态规划基本步骤四、矩阵连乘问题4.1 完全加括号的矩阵连乘积4.2 穷举法4.3 动态规划4.3.1 分析最优解的结构4.3.2 建立递归关系4.3.3 计算最优值4.3.4 用动态规划法求最优解 五、动态规划算法的基本要素5.1 最优子结构5.2 重叠子问题5.…

采集SEO方法-优化内链与外链建设

采集大量的文章数据&#xff0c;要想批量做SEO优化添加内链外链方法&#xff0c;可以使用简数采集器的处理规则实现。 简数采集器的一个处理规则&#xff0c;可以包含多种SEO方法&#xff0c;还可自由组合&#xff0c;强大灵活方便。 优化内链外链的SEO技巧&#xff1a; 1&a…

新手教程,蛋糕小程序的搭建流程一网打尽

作为一名新手&#xff0c;想要搭建一个蛋糕小程序可能会觉得有些困惑。但是&#xff0c;不用担心&#xff01;今天我将为大家详细介绍蛋糕小程序的搭建流程&#xff0c;并带大家一步步完成。 首先&#xff0c;我们需要登录乔拓云网的后台。在登录成功后&#xff0c;点击进入商城…

python使用mitmproxy和mitmdump抓包在手机上抓包(三)

现在手机的使用率远超过电脑&#xff0c;所以这篇记录用mitmproxy抓手机包&#xff0c;实现手机流量监控。 环境&#xff1a;win10 64位&#xff0c;Python 3.10.4&#xff0c;雷电模拟器4.0.78&#xff0c;android版本7.1.2&#xff08;设置-拉至最底部-关于平板电脑&#xf…

多线程总结(线程池 线程安全 常见锁)

本篇文章主要是对线程池进行详解。同时引出了单例模式的线程池&#xff0c;也对线程安全问题进行了解释。其中包含了智能指针、STL容器、饿汉模式的线程安全。也对常见的锁&#xff1a;悲观锁&#xff08;Pessimistic Locking&#xff09;、乐观锁&#xff08;Optimistic Locki…

DevOps持续集成与交付

概述 Jenkins是一个支持容器化部署的、使用Java运行环境的开源软件&#xff0c;使用Jenkins平台可以定制化不同的流程与任务、以自动化的机制支持DevOps领域中的CI与CD&#xff0c;在软件开发与运维的流程中自动化地执行软件工程项目的编译、构建、打包、测试、发布以及部署&a…

使用Vue-cli构建spa项目及结构解析

一&#xff0c;Vue-cli是什么&#xff1f; 是一个官方发布的Vue脚手架工具&#xff0c;用于快速搭建Vue项目结构&#xff0c;提供了现代前端开发所需要的一些基础功能&#xff0c;例如&#xff1a;Webpack打包、ESLint语法检查、单元测试、自动化部署等等。同时&#xff0c;Vu…

qml保姆级教程一:布局组件

&#x1f482; 个人主页:pp不会算法v &#x1f91f; 版权: 本文由【pp不会算法v】原创、在CSDN首发、需要转载请联系博主 &#x1f4ac; 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦 QML系列教程 QML教程一&#xff1a;布局组件 文章目录 锚布局anchors属…

JVM——11.JVM小结

这篇文章我们来小结一下JVM JVM&#xff0c;即java虚拟机&#xff0c;是java代码运行时的环境。我们从底层往上层来说&#xff0c;分别是硬件部分&#xff0c;操作系统&#xff0c;JVM&#xff0c;jre&#xff0c;JDK&#xff0c;java代码。JVM是直接与操作系统打交道的。JVM也…

基于复旦微的FMQL45T900全国产化ARM开发开发套件(核心板+底板)

TES745D是我司自主研制的一款基于上海复旦微电子FMQL45T900的全国产化ARM核心板&#xff08;模块&#xff09;。该核心板将复旦微的FMQL45T900&#xff08;与XILINX的XC7Z045-2FFG900I兼容&#xff09;的最小系统集成在了一个87*117mm的核心板上&#xff0c;可以作为一个核心模…