C++STL(stack类、queue类)

文章目录

  • 1.stack类和queue类的介绍
  • 2.stack类和queue类的基本用法
    • 2.1 (stack)下列代码的运行结果是( )
    • 2.2 (queue)下列代码的运行结果是( )
  • 3.stack类和queue类的底层(模拟实现)
    • 3.1 deque类(双端队列)
    • 3.2 适配器模式
    • 3.3 stack类的模拟实现
    • 3.4 queue类的模拟实现


1.stack类和queue类的介绍

stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。
stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。在这里插入图片描述

队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。
在这里插入图片描述

2.stack类和queue类的基本用法

其和前面的string、vector、list用法差不多,这里就不专门介绍了,以几道立体来说明!
在这里插入图片描述

2.1 (stack)下列代码的运行结果是( )

在这里插入图片描述

2.2 (queue)下列代码的运行结果是( )

在这里插入图片描述

3.stack类和queue类的底层(模拟实现)

栈和队列没有像前面的list、vector一样使用传统的方法底层实现!
在这里插入图片描述

在实现stack类和queue类之前,需要介绍一个新的容器deque
还有就是适配器模式
这两个概念需要我们学习一下!

3.1 deque类(双端队列)

是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。在这里插入图片描述

在这里插入图片描述

①与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。
②与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。
③但是,deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构。

3.2 适配器模式

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

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque。
.h文件在这里插入图片描述
.cpp文件在这里插入图片描述

3.3 stack类的模拟实现

mystack.h:

#pragma once
#include<vector>
#include<list>
#include<deque>

namespace bit
{
    // 适配器模式 -- 转换
    // 传什么就是什么栈,想用谁就用谁!
    // stack<int, vector<int>> st1;
	// stack<int, list<int>> st2;
    // stack<int, deque<int>> st3;
    template<class T, class Con = std::deque<T>>//模板参数也可以有缺省参数
    //template<class T, class Con = vector<T>>
    //template<class T, class Con = list<T>>
    //template<class T, class Con >//没有缺省参数
    class stack
    {
    public:
        stack() {}
        void push(const T& x) { _c.push_back(x); }
        void pop() { _c.pop_back(); }
        T& top() { return _c.back(); }
        const T& top()const { return _c.back(); }
        size_t size()const { return _c.size(); }
        bool empty()const { return _c.empty(); }
    private:
        Con _c;
    };
};

test.cpp:

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<deque>
#include<algorithm>
#include"mystack.h"

using namespace std;

void test_stack1()
{
	//bit::stack<int, list<int>> st;
	//bit::stack<int, vector<int>> st;
	bit::stack<int, deque<int>> st;
	//bit::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;
}

int main()
{
	test_stack1();
	return 0;
}

3.4 queue类的模拟实现

myqueue.h:

#pragma once
#include<deque>
#include <list>
namespace bite
{
	template<class T, class Con = std::deque<T>>//模板参数也可以有缺省参数
   //template<class T, class Con = vector<T>>
   //template<class T, class Con = list<T>>
   //template<class T, class Con >//没有缺省参数
	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;
	};
}

test,cpp:

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<deque>
#include<algorithm>
#include"myqueue.h"
using namespace std;
void test_queue2()
{
	//bit::stack<int, list<int>> st;
	//bit::stack<int, vector<int>> st;
	bite::queue<int, deque<int>> st;
	//bit::stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);

	while (!st.empty())
	{
		cout << st.front() << " ";
		st.pop();
	}
	cout << endl;
}
int main()
{
	test_queue2();

	return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

python创建word文档并向word中写数据

一、docx库的安装方法 python创建word文档需要用到docx库&#xff0c;安装命令如下&#xff1a; pip install python-docx 注意&#xff0c;安装的是python-docx。 二、使用方法 使用方法有很多&#xff0c;这里只介绍创建文档并向文档中写入数据。 import docxmydocdocx.Do…

CSS导读 (复合选择器 上)

&#xff08;大家好&#xff0c;今天我们将继续来学习CSS的相关知识&#xff0c;大家可以在评论区进行互动答疑哦~加油&#xff01;&#x1f495;&#xff09; 目录 二、CSS的复合选择器 2.1 什么是复合选择器 2.2 后代选择器(重要) 2.3 子选择器(重要) Questions 小提…

【CSS基础】9.形变transform

1. transform介绍 CSS transform属性允许对某个一个元素进行形变&#xff0c;包括旋转、位移、缩放、倾斜等并非所有的盒子都可以形变&#xff08;通常来说行内级盒子不能进行形变&#xff09; 2. transform的用法 transform可以增加多个transform function&#xff0c;通过空…

短视频转gif怎么做?三十秒在线转换gif

在现在这个快节奏的时代&#xff0c;gif动画相较于长时间的视频更受大众的欢迎。当我们需要将短视频、电影等视频制作成gif动画图片的时候就可以使用gif动画图片&#xff08;https://www.gif.cn/&#xff09;制作网站-GIF中文网&#xff0c;无需下载软件&#xff0c;手机、pc均…

K8s 命令行工具

文章目录 K8s 命令行工具kubectl 工具在任意节点使用kubectl方式创建对象命令显示和查找资源更新资源修补资源编辑资源Scale 资源删除资源查看pod信息节点相关操作 K8s 命令行工具 在搭建集群的时候&#xff0c;我们通过yum 下载了kubeadm kubelet kubectl 三个命令行工具&…

C 语言贪吃蛇源码解析

贪吃蛇是一款经典的电子游戏&#xff0c;玩家控制一条不断成长的蛇&#xff0c;需要避免撞到自己的身体或者游戏边界&#xff0c;同时吃掉出现在屏幕上的食物以增长身体长度。 下面是一个简单的贪吃蛇游戏的C语言实现&#xff0c;使用了标准输入输出库conio.h和时间库windows.h…

(弟)递归•斐波那契数、n的k次方

这里是目录哦 题目一&#xff1a;递归计算斐波那契数斐波那契数的定义代码运行截图递归过程递归停止条件&#xff08;1个参数&#xff09;✨非递归实现方法 题目二&#xff1a;递归实现n的k次方代码运行截图递归过程递归停止条件&#xff08;不止1个参数&#xff09;✨ 加油&am…

DETR论文粗读

一.前情提要 1.本文理论为主&#xff0c;并且仅为个人理解&#xff0c;能力一般&#xff0c;不喜勿喷 2.本文理论知识较为散碎 3.如有需要&#xff0c;以下是原文&#xff0c;更为完备 DETR 论文精读【论文精读】_哔哩哔哩_bilibili 二.正文 示意图&#xff1a; 1.不同与…

限制立方样条(RCS)做生存分析

一、引言 在医学和统计学领域&#xff0c;生存分析是一种分析个体生命长度和生存时间的重要方法。了解人们生存的期限和影响因素&#xff0c;对于制定健康政策、优化医疗资源的分配以及个体护理方案的制定都至关重要。传统的生存分析方法如Kaplan-Meier曲线和Cox比例风险模型已…

minikube环境搭建

&#x1f4d5;作者简介&#xff1a; 过去日记&#xff0c;致力于Java、GoLang,Rust等多种编程语言&#xff0c;热爱技术&#xff0c;喜欢游戏的博主。 &#x1f4d8;相关专栏Rust初阶教程、go语言基础系列、spring教程等&#xff0c;大家有兴趣的可以看一看 &#x1f4d9;Jav…

B004-表达式 类型转换 运算符

目录 表达式数据类型转换自动转换强制转换 运算符数学运算符自增自减运算符i与 i的区别 赋值运算符比较运算符位运算符(了解)逻辑运算符三目运算符 表达式 /*** 表达式定义&#xff1a;由常量 变量 运算符 括号组成的算式&#xff0c;为了按照一定的运算规则计算出结果值* 括…

HTML 入门 ( 一 )

HTML文档创建 首先创建一个txt文本文档 修改文件后缀 HTML标签 标签结构 标签又称为元素,是HTML的基本组成单位分为: 双标签与单标签推荐小写标签名 结构: 双标签示例代码: <marquee> My name is Kvein. </marquee>单标签示例代码: <input>标签的并列与嵌…

Autosar Dcm配置-手动配置RID及Routine功能实现-基于ETAS软件

文章目录 前言Routine介绍Routine配置DcmDsdDcmDspDcmDspRoutinesSWC配置总结前言 之前介绍了DID的配置,本文介绍UDS诊断中,另外一种常用的功能Routine的配置,及生成代码的使用。 Routine介绍 Routine一般用于ECU较复杂的控制功能。使用UDS服务ID为0x31 31后面跟的是子服…

【智能算法】智能算法空间搜索图GIF,探索开发对比图,动态展示理解更清晰~

目录 1.前文回顾2.空间搜索图3.探索开发对比图4.参考文献 1.前文回顾 前文已经提到智能算法统计指标&#xff0c;本文将进一步扩展算法空间搜索图GIF&#xff0c;探索开发对比图&#xff0c;动态展示理解更清晰&#xff1a; 【智能算法】省时方便&#xff0c;智能算法统计指标…

Python基于大数据的微博的舆论情感分析,微博评论情感分析可视化系统,附源码

博主介绍&#xff1a;✌Java徐师兄、7年大厂程序员经历。全网粉丝13w、csdn博客专家、掘金/华为云等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3fb; 不…

ExpressLRS硬件实测性能分析

ExpressLRS硬件实测性能分析 1. 源由2. 远航测试3. 实验室测试3.1 芯片RSSI与实测功率差异3.2 SNR信噪比稳定3.3 140db衰减器衰减&#xff0c;40个频点信号稳定 4. 外场测试4.1 无屏蔽样品4.2 有屏蔽样品4.3 有屏蔽vs无屏蔽样品 5. 估算6. 总结7. 补充说明 -- 50mW视频 1. 源由…

从0到1落地接口自动化测试(超详细)

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 前段时间写了一系列自动化测试相关的文章&#xff0c;当然更多的是方法和解决问题的思路角度去阐…

【AHK】显示画布\贴图周数\设置一个时钟显示周数

AHK没有直接显示画布的工具&#xff0c;但可以通过自定义GUI删去菜单栏显示。 具体逻辑&#xff0c;通过时间戳获取天数&#xff0c;然后再拿当前日期和开学日期作差&#xff0c;获取天数之后和数字7相除&#xff0c;再向下取整。 显示下过如图 ;先控制属性&#xff0c;下面依…

php:实现压缩文件上传、解压、文件更名、压缩包删除功能

效果图 1.上传文件 2.压缩包文件 3.itemno1文件 4.上传到系统路径\ItemNo 5.更名后的itemno1文件(命名&#xff1a;当天日期六位随机数) 代码 <form action"<?php echo htmlspecialchars($_SERVER[PHP_SELF], ENT_QUOTES, UTF-8); ?>" method"post…

机器人瓶胚检测工作站(H3U脉冲轴控制)

1、变量定义 2、程序监控1 2、 程序监控2 3、程序监控3 机器人输送料和机构的动作安全尤为重要&#xff0c;下面我们讨论下安全联锁控制逻辑 4、相机拍照触发信号 5、相机拍照触发时序