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

STL容器适配器 -- stack和queue(使用+实现)(C++)

stack和queue

  • stack
    • stack的介绍
    • stack的使用
    • stack的实现
  • queue
    • queue的介绍
    • queue的使用
    • queue的实现
  • deque
    • 简单介绍deque(双端队列)
      • 双开口
      • 连续打引号的原因
    • deque底层结构
    • deque的迭代器封装结构(复杂)
    • deque的优缺点

栈和队列数据结构+画图分析如果对栈和队列的结构不了解的,可以先看该链接的内容

stack

使用stack时需要头文件#include<stack>

stack的介绍

stack是一种容器适配器,用于具有后进先出(LIFO)的环境中。只能从容器的一端(栈顶),执行删除、插入和提取操作。

stack是作为容器适配器实现的,容器适配器是对特定容器类封装,作为其底层的容器。vector、deque、list均符合特定的底层容器需求,如果没有指定特定的底层容器,默认使用deque

stack的使用

函数接口说明
stack()构造空的栈
empty()判断栈是否为空
size()返回栈中的元素个数
top()返回栈顶元素的引用
push()将val压栈
pop()出栈顶元素

test:


void test_stack()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);cout << st.size() << endl;while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;
}

注意:从栈的接口可以看出,栈实际是一种特殊的vector,使用vector完全可以模拟实现stack

stack的实现

stack接口的实现是对deque容器接口的封装。

#include <deque>namespace kpl
{//容器可以使用vector,deque容器在本博客最后一个知识点介绍//template<class T, class Container = vector<T>>//template<class T, class Container = list<T>>template<class T, class Container = deque<T>>class stack{public:stack(){}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top() const{return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

queue

使用queue时需要头文件#include<queue>

queue的介绍

queue是一种容器适配器,用于具有先进先出(FIFO)的环境中。从容器的一端插入元素,另一端提取元素。

queue作为容器适配器实现,容器适配器是对特定容器类封装,作为其底层的容器。deque、list符合特定的底层容器需求,如果没有为queue实列化指定特定的底层容器,默认使用deque

queue的使用

函数接口说明
queue()构造空的队列
empty()判断队列是否为空
size()返回队列中的元素个数
front()返回队头元素的引用
back()返回队尾元素的引用
push()在队尾将val入列
pop()在队头元素出队列

test:

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);cout << "size:" << q.size() << endl;cout << "front:" << q.front() << endl;q.pop();cout << "back:" << q.back() << endl;while (!q.empty()){cout << "front:" << q.front() << " ";q.pop();}cout << endl;
}

queue的实现

因为queue的接口有头插和尾插,使用vector封装效率底,所以可以借助list模拟实现。这里我们依旧使用的默认容器deque

queue接口的实现是对deque容器接口的封装。

#include <deque>namespace kpl
{//template<class T, class Container = list<T>>template<class T, class Container = deque<T>>class queue{public:queue(){}bool empty(){return _con.empty();}size_t size(){return _con.size();}T& front(){return _con.front();}const T& front() const{return _con.front();}T& back(){return _con.back();}const T& back() const{return _con.back();}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}private:Container _con;};
}

deque

简单介绍deque(双端队列)

概念:是一种双开口“连续”空间的数据结构。

双开口

双开口

连续打引号的原因

原因:deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成,分段连续。

deque底层结构

底层结构

deque的迭代器封装结构(复杂)

deque的迭代器

deque的优缺点

deque的优缺点决定了它适合当stack和queue的底层数据结构
deque的优缺点

  1. stack和queue不需要遍历(deque不适合遍历),只需要在固定的一端或者两端操作即可。
  2. stack元素在增长时,deque比vector的效率高(不需要搬移数据),queue元素在增长是,内存使用率高,效率也高。

相关文章:

STL容器适配器 -- stack和queue(使用+实现)(C++)

stack和queue stackstack的介绍stack的使用stack的实现 queuequeue的介绍queue的使用queue的实现 deque简单介绍deque&#xff08;双端队列&#xff09;双开口连续打引号的原因 deque底层结构deque的迭代器封装结构&#xff08;复杂&#xff09;deque的优缺点 栈和队列数据结构…...

K8s operator从0到1实战

Operator基础知识 Kubernetes Operator是一种用于管理和扩展Kubernetes应用程序的模式和工具。它们是一种自定义的Kubernetes控制器&#xff0c;可以根据特定的应用程序需求和业务逻辑扩展Kubernetes功能。 Kubernetes Operator基于Kubernetes的控制器模式&#xff0c;通过自…...

【LangChain学习】基于PDF文档构建问答知识库(三)实战整合 LangChain、OpenAI、FAISS等

接下来&#xff0c;我们开始在web框架上整合 LangChain、OpenAI、FAISS等。 一、PDF库 因为项目是基于PDF文档的&#xff0c;所以需要一些操作PDF的库&#xff0c;我们这边使用的是PyPDF2 from PyPDF2 import PdfReader# 获取pdf文件内容 def get_pdf_text(pdf):text "…...

阿里云国际站对象储存OSS的常见问题?

1.什么是阿里云OSS&#xff1f; 阿里云对象存储服务OSS&#xff08;Object Storage Service&#xff09;&#xff0c;是阿里云提供的海量、安全、低成本、高持久性的云存储服务&#xff0c;并可无限扩展。其数据设计持久性不低于99.9999999999%&#xff08;12个9&#xff09;&a…...

spss什么是描述性分析,以及如何去处理。

描述性分析是数据分析的第一步&#xff0c;是了解和认识数据基本特征和结构的方法&#xff0c;只有在完成了描述性统计分析&#xff0c;充分的了解和认识数据特征后&#xff0c;才能更好地开展后续更复杂的数据分析。因此&#xff0c;描述性分析是开展数据分析过程中最基础且必…...

OSCS 闭门研讨第一期实录:软件供应链安全建设价值

2023 年 7 月 18 日晚 19:30&#xff0c;软件供应链安全技术交流群&#xff08;OSCS&#xff09;组织了第一次线上的闭门研讨会&#xff0c;本次研讨会我们收到 71 个来自各个企业关注软件供应链安全的技术专家的报名&#xff0c;根据研讨会参与规则要求&#xff0c;我们对报名…...

STM32入门——ADC模数转换

ADC简介 ADC&#xff08;Analog-Digital Converter&#xff09;模拟-数字转换器ADC可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量&#xff0c;建立模拟电路到数字电路的桥梁12位逐次逼近型ADC&#xff0c;1us转换时间输入电压范围&#xff1a;0~3.3V&#xff0c;…...

【Fegin技术专题】「原生态」打开Fegin之RPC技术的开端,你会使用原生态的Fegin吗?(下)

内容简介 在项目开发中&#xff0c;除了考虑正常的调用之外&#xff0c;负载均衡和故障转移也是关注的重点&#xff0c;这也是feign ribbon的优势所在&#xff0c;基于上面两篇文章的基础&#xff0c;接下来我们开展最后一篇原生态fegin结合ribbon服务进行服务远程调用且实现负…...

【leetcode】454. 四数相加 II(medium)

给你四个整数数组 nums1、nums2、nums3 和 nums4 &#xff0c;数组长度都是 n &#xff0c;请你计算有多少个元组 (i, j, k, l) 能满足&#xff1a; 0 < i, j, k, l < nnums1[i] nums2[j] nums3[k] nums4[l] 0 思路&#xff1a;如果要暴力&#xff0c;那么时间复杂…...

PHP先等比缩放再无损裁剪图片【实例源码】

很多人在使用程序裁剪图片时,是在原图上直接裁剪,这样的裁剪结果是使得图片变得不完整了,理想的做法是先等比缩小图片,再把多余的部分裁掉,这样会保留更多的图片信息。 实现代码: <?php/*** 说明:函数功能是把一个图像裁剪为任意大小的图像,图像不变形** @param …...

共享广告主项目:广告也能共享?全民广告时代来袭

科思创业汇 大家好&#xff0c;这里是科思创业汇&#xff0c;一个轻资产创业孵化平台。赚钱的方式有很多种&#xff0c;我希望在科思创业汇能够给你带来最快乐的那一种&#xff01; 广告是我们日常生活中在衣食住行中可以看到的一种宣传方式。广告作为互联网社会的信息传播方…...

Flink-间隔联结

间隔联结只支持事件时间间隔联结如果遇到迟到数据&#xff0c;则会关联不上&#xff0c;比如来了一个5秒的数据&#xff0c;它可以关联前2秒的数据&#xff0c;后3秒的数据&#xff0c;就是可以关联3秒到8秒的数据&#xff0c;然后又来了一个6秒的数据&#xff0c;可以关联4秒到…...

redis的持久化

第一章、redis的持久化 1.1&#xff09;持久化概述 ①持久化可以理解为将数据存储到一个不会丢失的地方&#xff0c;Redis 的数据存储在内存中&#xff0c;电脑关闭数据就会丢失&#xff0c;所以放在内存中的数据不是持久化的&#xff0c;而放在磁盘就算是一种持久化。 ②为…...

藏语翻译器:多功能翻译软件

这是是一款能够将藏语翻译成其他语言或将其他语言翻译成藏语的软件。该软件能够识别并翻译藏语中的常用词汇和短语&#xff0c;并且支持多种常见语言的翻译&#xff0c;例如英语、汉语、法语、德语等等。此外&#xff0c;藏语翻译器还具有简单易用的用户界面&#xff0c;方便用…...

Java课题笔记~ JavaWeb概述/开发基础

JavaWeb概述/开发基础 1.XML基础 &#xff08;1&#xff09;XML概述 &#xff08;2&#xff09;XML语法 &#xff08;3&#xff09;DTD约束 &#xff08;4&#xff09;Schema约束&#xff08;XML Schema 比 DTD 更强大&#xff09; 2.Web基础知识 Web是一个分布式的超媒…...

【解放ipad生产力】如何在平板上使用免费IDE工具完成项目开发

我的博客即将同步至腾讯云开发者社区&#xff0c;邀请大家一同入驻&#xff1a;https://cloud.tencent.com/developer/support-plan?invite_code3o19zyy2pneoo 前言 很多人应该会像我一样吧&#xff0c;有时候身边没电脑突然要写项目&#xff0c;发现自己的平板没有一点作用&…...

IDEA快捷键总结

切换窗口 Alt&#xff08;1-9&#xff09; Alt1 打开或者关闭左侧project Alt4 Run窗口 Alt5 Debug窗口 Alt7 类结构窗口 生成构造函数、get、set等方法 Altinsert 快速生成输出语句 Soutenter键 运行程序 chtlshiftf10 运行程序 shiftf9 debug方式运行程序 代码…...

OpenJDK Maven 编译出错: package jdk.nashorn.internal.runtime.logging does not exist

前言 OpenJDK 1.8.0Maven 3.8.5TencentOS Server 3.1 错误信息 [ERROR] Failed to execute goal org.apache.maven.plugins:maven-compiler-plugin:3.1:compile (default-compile) on project tour-common: Compilation failure: Compilation failure: [ERROR] /opt/tour-c…...

.Net Framework请求外部Api

要在.NET Framework 4.5中进行外部API的POST请求&#xff0c;你可以使用HttpClient类。 1. Post请求 using System; using System.Net.Http; using System.Threading.Tasks;class Program {static async Task Main(string[] args){// 创建一个HttpClient实例using (HttpClien…...

线程池工作原理深入解析

目录 1. 线程正常的生命周期 2. 为什么要用线程池&#xff1f; 3. 线程池的核心原理 4. 怎样创建线程池&#xff1f; 5.线程池的代码实现 6. ThreadPoolExecutor 源码分析 7. ThreadPoolExecutor 工作原理展示&#xff08;重点&#xff09; 1. 线程正常的生命周期 我们知…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...