[STL]stack和queue使用介绍

[STL]stack和queue使用介绍

文章目录

  • [STL]stack和queue使用介绍
    • stack使用介绍
      • stack介绍
      • 构造函数
      • empty函数
      • push函数
      • top函数
      • size函数
      • pop函数
    • queue使用介绍
      • queue介绍
      • 构造函数
      • empty函数
      • push函数
      • front函数
      • back函数
      • size函数
      • pop函数
    • deque介绍

stack使用介绍

stack介绍

  1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。
  2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。
  3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:
    • empty:判空操作
    • back:获取尾部元素操作
    • push_back:尾部插入元素操作
    • pop_back:尾部删除元素操作
  4. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器, 默认情况下使用deque

构造函数

stack只有默认构造函数,构造一个空栈。

stack<int> st;

同样是构造一个空栈,stack还可以指定底层容器进行构造。

stack<int, vector<int>> st;

empty函数

empty函数用于判断stack是否为空。

#include <iostream>
#include <stack>
using namespace std;
int main()
{
	stack<int> st;
	cout << st.empty() << endl; //输出为1
	return 0;
}

push函数

push函数用于往stack中压入数据。

#include <iostream>
#include <stack>
using namespace std;
int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	cout << st.empty() << endl; //输出为0
	return 0;
}

top函数

top函数用于获取stack的顶部数据。

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	cout << st.top() << endl; //输出为3
	return 0;
}

size函数

size函数用于获取stack内的数据个数。

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	cout << st.size() << endl; //输出为3
	return 0;
}

pop函数

pop函数用于弹出stack顶部的数据。

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.pop();
	cout << st.top() << endl; //输出为2
	return 0;
}

queue使用介绍

queue介绍

  1. queue是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端 提取元素。
  2. queue作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列,从队头出队列。
  3. 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
    • empty:检测队列是否为空
    • size:返回队列中有效元素的个数
    • front:返回队头元素的引用
    • back:返回队尾元素的引用
    • push_back:在队列尾部入队列
    • pop_front:在队列头部出队列
  4. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则默认使用标准容器deque

构造函数

queue只有默认构造函数,构造一个空队列。

queue<int> q;

同样是构造一个空队列,queue还可以指定底层容器进行构造。

queue<int, list<int>> q;

empty函数

empty函数用于判断queue是否为空。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	cout << q.empty() << endl; //输出为1
	return 0;
}

push函数

push函数用于往将数据尾插至队列。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	cout << q.empty() << endl; //输出为0
	return 0;
}

front函数

front函数用于获取队头的数据。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	cout << q.front() << endl; //输出为1
	return 0;
}

back函数

back函数用于获取队尾的数据。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	cout << q.back() << endl; //输出为3
	return 0;
}

size函数

size函数用于获取队列内的数据个数。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	cout << q.size() << endl; //输出为3
	return 0;
}

pop函数

pop函数用于删除队头的数据。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.pop();
	cout << q.front() << endl; //输出为2
	return 0;
}

deque介绍

STL中stack和list的底层实现都使用的是deque容器。

deque(双端队列)兼容了vector和list的使用接口,使得deque可以在头尾两端进行插入和删除操作,并且还支持数据的随机访问。deque的结构示意图如下:

image-20230730165637318

deque设计了一个中控数组,往中控数组中插入数据需要从中间开始插入,然后从中间开始进行头插和尾插,中控数组中的结点存储着指针,指向一段连续的空间,中控数据空间不够了会进行扩容,并将原有数据拷贝。由于每个结点指向的连续空间内存储的数据个数和容量是已知的,因此要进行随机访问,可以通过计算得到相应的结点和连续空间内的相应位置来实现,当然往deque内中间位置插入数据也是从中间结点指向的空间开始插入,向deque头插(删)或尾插(删)只需要从中控数据的头结点和尾结点寻找数据,在指向的空间内找到对应位置进行操作。

优点:

  • 相比vector, 扩容代价更低。
  • 头插头删、尾插尾删效率相对vector更高,且时间复杂度为O(1)。
  • 相比list,空间利用率比较高。
  • 支持随机访问。

缺点:

  • 中间部分的数据的插入和删除存在取舍问题 – 保持随机访问的效率,会降低头尾数据操作的效率;保持头尾数据操作的效率,会降低随机访问的效率。
  • 优点方面的表现没有vector或list突出。

deque迭代器示意图如下:

image-20230730171911724

deque迭代器包含四个指针:

  • cur – 指向当前数据
  • first – 指向连续空间的开始位置
  • last – 指向连续空间的结束位置
  • node – 指向中控数组当前使用的结点位置

stack和queue选择deque的原因:

  1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
  2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长 时,deque不仅效率高,而且内存使用率高。

总结: stack和queue使用deque发挥了其优点,规避了其缺点,使得效率在各种场景下都保持一定的水准。

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

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

相关文章

Tensorflow报错protobuf requires Python ‘>=3.7‘ but the running Python is 3.6.8

报错信息 仔细观察下方命令后&#xff0c;可得运行:python -m pip install --upgrade pip即可 完成后再次执行性安装命令 成功&#xff01;&#xff01;&#xff01;

爆肝!《Java 权威面试指南(阿里版)》,冲击“金九银十”有望了

这次金九银十你准备好了吗&#xff1f; 莫慌莫慌&#xff0c;“面试造火箭&#xff0c;工作拧螺丝” 说得不无道理&#xff0c;偶然从朋友那得到的这份 Alibaba 内部疯传《Java 权威面试指南&#xff08;阿里版&#xff09;》堪称精品&#xff0c;或可能助你一臂之力&#xff…

Doris注意事项,Doris部署在阿里云,写不进去数据

1.Doris官网 Doris官网https://doris.apache.org/ 2.根本原因 本地idea访问FE&#xff0c;FE会返回BE的地址&#xff0c;但是在服务器上通过ip addr查看&#xff0c;发现只有局域网IP&#xff0c;所以FE返回了局域网的IP&#xff0c;导致idea连接不上BE 3.解决办法 重写Ba…

Jmeter并发测试

基本步骤 1、新建线程组 测试计划右键——>添加——>线程&#xff08;用户&#xff09;——>线程组 2、 添加HTTP请求 线程组右键——>添加——>取样器——>HTTP请求 3、 添加HTTP信息头管理器 线程组右键——>添加——>配置元件——>HTTP信息头…

ChatGPT炒股:自动批量提取股票公告中的表格并合并数据

在很多个股票公告中&#xff0c;都有同样格式的“日常性关联交易”的表格&#xff0c;如何合并到一张Excel表格中呢&#xff1f; 首先&#xff0c;在ChatGPT中输入提示词&#xff1a; 写一段Python代码&#xff1a; F盘文件夹“新三板 2023年日常性关联交易20230704”中很多…

2023 7-30

题目1 lee2331.计算布尔二叉树的值 对于一棵完整的二叉树(每一个根节点孩子的个数不是0就是2) 叶子节点是1或者是0,其中1代表true,0代表false非叶子节点的值是2或者3,其中2代表逻辑或or,3代表逻辑与and计算方式 如果节点是个叶子节点,那么节点的 值 为它本身,即 True 或者…

一、创建自己的docker python容器环境;支持新增python包并更新容器;离线打包、加载image

1、创建自己的docker python容器环境 参考&#xff1a;https://blog.csdn.net/weixin_42357472/article/details/118991485 首先写Dockfile&#xff0c;注意不要有txt等后缀 Dockfile # 使用 Python 3.9 镜像作为基础 FROM python:3.9# 设置工作目录 WORKDIR /app# 复制当前…

创造自己的宠物医院预约服务小程序,步骤详解

在现代社会&#xff0c;越来越多的人开始养宠物&#xff0c;而宠物的健康管理也成为了一个重要的话题。为了方便宠物主人随时随地进行宠物医院的管理和服务&#xff0c;开发一个宠物医院管理小程序是很有必要的。今天我们将分享一些制作宠物医院管理小程序的技巧&#xff0c;帮…

基于Open3D的点云处理12-体素化

体素化Voxelization 体素&#xff08;voxel&#xff09;是像素&#xff08;pixel&#xff09;、体积&#xff08;volume&#xff09;和元素&#xff08;element&#xff09;的组合词&#xff0c;相当于3D空间中的像素; 体素化是通过用空间均匀大小的体素网格(voxel grid)来模…

【C++】开源:grpc远程过程调用(RPC)配置与使用

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍grpc远程过程调用&#xff08;RPC&#xff09;配置与使用。 无专精则不能成&#xff0c;无涉猎则不能通。。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜…

【编程规范】一文讲解开发中的命名规范

命名规范 好的代码本身就是注释, 所以我们需要统一命名风格。 ​ 在本文中&#xff0c;将从大到小&#xff0c;从外到内&#xff0c;总结Java编程中的命名规范。文中将会涉及到日常工作中常见的命名示例&#xff0c;如包命名&#xff0c;类命名&#xff0c;接口命名&#xff0c…

页面生成图片或PDF node-egg

没有特别的幸运&#xff0c;那么就特别的努力&#xff01;&#xff01;&#xff01; 中间件&#xff1a;页面生成图片 node-egg 涉及到技术node egg Puppeteer 解决文书智能生成多样化先看效果环境准备初始化项目 目录结构核心代码 完整代码https://gitee.com/hammer1010_ad…

数组中出现次数超过一半的数字——剑指 Offer 39

文章目录 题目描述法一 哈希表法二 摩尔投票 题目描述 法一 哈希表 使用哈希映射&#xff08;HashMap&#xff09;来存储每个元素以及出现的次数。对于哈希映射中的每个键值对&#xff0c;键表示一个元素&#xff0c;值表示该元素出现的次数。 class Solution { public:int maj…

【Python机器学习】实验03 logstic回归

文章目录 简单分类模型 - 逻辑回归1.1 准备数据1.2 定义假设函数Sigmoid 函数 1.3 定义代价函数1.4 定义梯度下降算法gradient descent(梯度下降) 1.5 绘制决策边界1.6 计算准确率1.7 试试用Sklearn来解决2.1 准备数据(试试第二个例子)2.2 假设函数与前h相同2.3 代价函数与前相…

【语音识别】- 声学,词汇和语言模型

一、说明 语音识别是指计算机通过处理人类语言的音频信号&#xff0c;将其转换为可理解的文本形式的技术。也就是说&#xff0c;它可以将人类的口语语音转换为文本&#xff0c;以便计算机能够进一步处理和理解。它是自然语言处理技术的一部分&#xff0c;被广泛应用于语音识别助…

Linux 之 systemctl

systemctl 可以控制软件&#xff08;一般指服务&#xff09;的启动、关闭、开机自启动 能被systemctl 管理的软件&#xff0c;一般也称 服务 系统内置服务均可被 systemctl 控制第三方软件&#xff0c;如果 自动注册了 可被systemctl 控制第三方软件&#xff0c;如果没有自动…

better scoll右 联左

这是先拿一个数组装进我们所有 获取到的dom节点的 高度 因为算的 都是 到最上面的 高度&#xff0c;所以我们 要减去他的 高度 就得到自身的高度 然后给右边加一个滚动事件&#xff0c;得到每一次滑动的高度&#xff0c;在循环上面的数组&#xff0c;就是我们右边的 y就在算出…

微信小程序实现日历功能、日历转换插件、calendar

文章目录 演示htmlJavaScript 演示 效果图 微信小程序实现交互 html <view wx:if"{{calendarArr.length}}"><view class"height_786 df_fdc_aic"><view class"grid_c7_104"><view class"font_weight_800 text_align…

Debezium日常分享系列之:定制Debezium 信号发送和通知

Debezium日常分享系列之&#xff1a;定制Debezium 信号发送和通知 一、自定义信号和通知通道二、结论 Debezium 2.3 在信号和通知功能方面引入了新的改进。除了 Debezium 提供的预定义信号和通知通道之外&#xff0c;您还可以设置新的信号和通知通道。此功能使用户能够自定义系…

微服务——服务异步通讯RabbitMQ

前置文章 消息队列——RabbitMQ基本概念容器化部署和简单工作模式程序_北岭山脚鼠鼠的博客-CSDN博客 消息队列——rabbitmq的不同工作模式_北岭山脚鼠鼠的博客-CSDN博客 消息队列——spring和springboot整合rabbitmq_北岭山脚鼠鼠的博客-CSDN博客 目录 Work queues 工作队列…