STL —— stack、queue

图片名称

 
博主首页: 有趣的中国人
 
专栏首页: C++专栏
 

目录

 1. 容器适配器

2. 栈的模拟实现

3. 队列的模拟实现

4. 双端队列deque 

4.1 deque的原理介绍

 4.2 deque的缺陷

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


本篇文章主要讲解  stack 和 queue  的相关内容

 std::stack 是一个模板类,定义在 <stack> 头文件中,它基于其他的底层容器来实现栈的功能。默认情况下,std::stack 使用 std::deque 作为其底层容器,但也可以使用其他 STL 容器,如 std::vectorstd::list

基本操作

  1. 压入元素: 使用 push() 成员函数将元素推入栈顶。

  2. 弹出元素: 使用 pop() 成员函数从栈顶移除元素。

  3. 访问栈顶元素: 使用 top() 成员函数获取栈顶元素的引用,但不会将其从栈中移除。

  4. 判断栈是否为空: 使用 empty() 成员函数检查栈是否为空。

  5. 获取栈的大小: 使用 size() 成员函数获取栈中元素的数量。

std::queue 是一个模板类,定义在 <queue> 头文件中,它基于其他的底层容器来实现队列的功能。默认情况下,std::queue使用 std::queue 作为其底层容器,但也可以使用其他 STL 容器,如 std::list

基本操作

  1. 入队操作: 使用 push() 成员函数将元素推入队列的末尾。

  2. 出队操作: 使用 pop() 成员函数从队列的头部移除元素。

  3. 访问队列头部元素: 使用 front() 成员函数获取队列头部元素的引用,但不会将其从队列中移除。

  4. 访问队列尾部元素: 使用 back() 成员函数获取队列尾部元素的引用,但不会将其从队列中移除。

  5. 判断队列是否为空: 使用 empty() 成员函数检查队列是否为空。

  6. 获取队列的大小: 使用 size() 成员函数获取队列中元素的数量。


 1. 容器适配器

如果按照正常的思路实现stack,那么其中的元素应该有:

class stack
{

private:
	int _top;
	int _size;
	int _capacity;
};

但是,在C++中,用了适配器的模式,何为适配器呢?

我们知道stack模拟实现的过程与vector类似,那我们能否用vector来实现stack呢?

肯定是可以的,容器适配器是一种设计模式,它提供了一种简单的方式来修改或扩展现有容器的接口,以满足特定的需求或限制。


2. 栈的模拟实现

我们在实现栈的时候就可以用到容器适配器的模式,只需要在传模板参数的时候多加一个参数即可:

template<class T, class Container = vector<T>>
class stack
{
public:
	void push(const T& val)
	{
		_con.push_back(val);
	}
	void pop()
	{
		_con.pop_back();
	}
	size_t size() const
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
	T& top()
	{
		return _con.back();
	}
private:
	Container _con;
};
void stack_test1()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
}


3. 队列的模拟实现

类似的,我们可以用容器适配器来模拟实现队列:

template<class T, class Container = vector<T>>
class stack
{
public:
	void push(const T& val)
	{
		_con.push_back(val);
	}
	void pop()
	{
		_con.pop_back();
	}
	size_t size() const
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
	T& top()
	{
		return _con.back();
	}
private:
	Container _con;
};
void stack_test1()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
}


4. 双端队列deque 

4.1 deque的原理介绍

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

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


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


那deque是如何借助其迭代器维护其假想连续的结构呢?


 4.2 deque的缺陷

vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。


list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。


但是,deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vectorlistdeque的应用并不多,而目前能看到的一个应用就是,STL用其作为stackqueue的底层数据结构

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

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()pop_back()操作的线性结构,都可以作为stack的底层容器,比如vectorlist都可以;queue是先进先出的特殊线性数据结构,只要具有push_backpop_front操作的线性结构,都可以作为queue的底层容器,比如list。但是STL中对stackqueue默认选择deque作为其底层容器,主要是因为:

  1. stackqueue不需要遍历(因此stackqueue没有迭代器),只需要在固定的一端或者两端进行操作。
  2. stack中元素增长时,dequevector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。结合了deque的优点,而完美的避开了其缺陷.。

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

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

相关文章

MDK-ARM Keil5.38 下载安装环境搭建

一、keil软件介绍 KEIL是公司的名称&#xff0c;有时候也指KEIL公司的所有软件开发工具&#xff0c;目前2005年Keil由ARM公司收购&#xff0c;成为ARM的公司之一。 MDK&#xff08;Microcontroller Development Kit&#xff09; 也称MDK-ARM、KEIL MDK、RealView MDK、KEIL For…

IDEA 设置类注释模板作者、日期、描述等信息(推荐标准!)

idea注释模版配置 idea作为越来越多程序员使用的开发工具&#xff0c;平时的代码注释也非常的关键&#xff0c;类上注释和方法上注释每次换电脑或者新同事入职都要统一修改&#xff0c;找了网上好多教程都写的乱七八糟的啥都有&#xff0c;为方便统一就自己写一个操作方法&…

【yolov5小技巧(2)】---将yolov5中的特征图以热力图的方式进行可视化

文章目录 &#x1f680;&#x1f680;&#x1f680;前言一、1️⃣ 将特征图可视化的文章CFPNet二、2️⃣yolov5自带的特征图可视化工具三、3️⃣如何将特征图转换成热力图 &#x1f440;&#x1f389;&#x1f4dc;系列文章目录 【yolov5小技巧(1)】—可视化并统计目标检测中的…

Leetcode二叉树刷题

给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true public boolean isSymmetric(TreeNode root) {if(rootnull)return true;return compare(root.left,root.right);}public boole…

Python学习笔记(37)——用xlwings库生成excel

老规矩先pip入xlwings库 STEP1:下载xlwings库 windowsr>>cmd>>pip install xlwings (如果需要不同版本可以到pypi上搜&#xff09; STEP2:完成EXCEL初级创建 请打开您的编写软件~~~~~&#xff08;小编的显示结果为PYCHARM编写的&#xff0c;因为颜色标注好看(…

113.PyQt5_QtPrintSupport_打印操作

我 的 个 人 主 页&#xff1a;&#x1f449;&#x1f449; 失心疯的个人主页 &#x1f448;&#x1f448; 入 门 教 程 推 荐 &#xff1a;&#x1f449;&#x1f449; Python零基础入门教程合集 &#x1f448;&#x1f448; 虚 拟 环 境 搭 建 &#xff1a;&#x1f449;&…

光电传感器的工作原理简介

光电传感器是一种利用光电效应将光信号转换为电信号的传感器。 工作原理 光照射&#xff1a;光电传感器通过光源&#xff08;如LED或激光&#xff09;照射在其表面。 光电转换&#xff1a;光线与传感器材料发生光电反应&#xff0c;产生电信号。这种转换过程涉及到光子与电子的…

论文解读 --- 《针对PowerShell脚本的有效轻量级去混淆和语义感知攻击检测》

开篇 今天我们继续来解读安全行业优秀论文&#xff0c;通过学习他人的智慧成果&#xff0c;可以不断丰富我们的安全视野&#xff0c;使用它山之石来破解自身的难题。 这次要解读的论文为《Effective and Light-Weight Deobfuscation and Semantic-Aware Attack Detection for…

解决宝塔的FTP无法使用被动模式

问题&#xff1a;宝塔安装完ftp管理软件之后&#xff0c;无法使用被动模式连接 解决&#xff1a; 提示&#xff1a; 如果还是不行&#xff0c;那么要看看防火墙和安全组有没有放行被动模式的端口&#xff0c;宝塔安装的pure-ftpd软件的被动模式端口默认是39000至400…

使用稳压管和三极管射极输出器电路驱动PMOS

当电源电压大于PMOS 管的最大栅源电源时&#xff0c;不能直接把栅极拉到地&#xff0c;需要一点特殊的电路来限制栅极驱动电压。有的地方是用电阻分压器做的&#xff0c;比如这种&#xff1a; NPN 三极管导通时&#xff0c;MOS 管栅极电压是两个电阻中间的电压。这种设计最大的…

“华为杯“华南理工大学程序设计竞赛 L-再一道好题

题目 #include<bits/stdc.h> using namespace std; #define int long long #define pb push_back #define fi first #define se second const int maxn 1e6 5; const int inf 1e9 5;using namespace std;int n, m;void solve(){int res 0;int q;string s;int k;cin …

华为ensp中nat server 公网访问内网服务器

作者主页&#xff1a;点击&#xff01; ENSP专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年4月15日17点30分 NAT服务器是一种在网络边界设备上配置的服务&#xff0c;它允许外部网络的用户访问内部网络中的服务或主机&#xff0c;同时隐藏了内部网络的真实IP地…

Eigen笔记2:矩阵拼接

直接贴代码吧&#xff0c;使用的MatrixXd 和<<运算符&#xff1a; int main(int argc, char *argv[]) {Eigen::MatrixXd B(2, 2);B << 1, 2,3, 4;Eigen::MatrixXd C(2, 2);C << 5, 6,7, 8;Eigen::MatrixXd D(2, 2);D << 9, 10,11, 12;Eigen::MatrixXd…

《由浅入深学习SAP财务》:第2章 总账模块 - 2.6 定期处理 - 2.6.5 年末操作:维护新财政年度会计凭证编号范围

2.6.5 年末操作&#xff1a;维护新财政年度会计凭证编号范围 财务系统的维护者要在每年年末预先设置好下一年度的会计凭证编号范围&#xff08;number range&#xff09;&#xff0c;以便下一年度会计凭证能够顺利生成。这一操作一定要在下一年度1月1日以前预先完成。 …

基于SSM项目高校在线请假与审批系统

采用技术 基于SpringBoot框架实现的web的智慧社区系统的设计与实现~ 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringMVCMyBatis 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 简介 本系统实现了管理员&#xff0c;教师&#xff0c;学生三个模…

《QT实用小工具·二十五》日志重定向输出

1、概述 源码放在文章末尾 日志重定向输出&#xff0c;包含如下功能&#xff1a; 支持动态启动和停止。支持日志存储的目录。支持网络发出打印日志。支持输出日志上下文信息比如所在代码文件、行号、函数名等。支持设置日志文件大小限制&#xff0c;超过则自动分文件&#xf…

JS - 关于DOM的介绍和使用01

DOM&#xff08;Document Object Model&#xff09;是一种用于表示和操作HTML、XML等文档结构的编程接口。在JavaScript中&#xff0c;通过DOM可以访问和操作网页中的各种元素、属性和事件。 获取元素&#xff1a; 通过ID获取元素&#xff1a;使用document.getElementById(el…

4.Godot图片素材的获取和编辑

游戏开发中经常遇到图片素材的需求 1. 图片素材的准备 术语&#xff1a;Sprite 精灵&#xff0c;游戏开发中指一张图片来源不明的图片&#xff0c;切勿在商业用途使用&#xff0c;以免引起版权风险。 1. 在学习阶段&#xff0c;可以百度或者从一些资源网站获取&#xff0c;这…

面试题总结:HashMap底层原理

不仅仅是一道题&#xff0c;之后的某一天&#xff0c;它可能是破局的关键。 关于HashMap的知识点有哪些呢&#xff1f;分层次展示 1.基础知识&#xff1a; 存储键值对结构、底层数据结构、红黑树和链表 2.位运算与实现 位运算、put、get方法的实现 3.关于锁 segment锁和桶锁、线…

OpenCV基本图像处理操作(三)——图像轮廓

轮廓 cv2.findContours(img,mode,method) mode:轮廓检索模式 RETR_EXTERNAL &#xff1a;只检索最外面的轮廓&#xff1b;RETR_LIST&#xff1a;检索所有的轮廓&#xff0c;并将其保存到一条链表当中&#xff1b;RETR_CCOMP&#xff1a;检索所有的轮廓&#xff0c;并将他们组…