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

stack和queue(1)

一、stack的简单介绍和使用

1.1 stack的介绍

1.stack是一种容器适配器,专门用在具有先进后出,后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入和弹出操作。

2.stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器尾部(即栈顶)被压入和弹出。

3.stack的底层容器可以是任何标准的容器类模板或者一些其他待定的容器类,这些容器类需要支持以下的一些操作:

  • empty :判空操作
  • back:获取尾部元素
  • push_back:尾部插入元素
  • pop_back:尾部删除元素

 4.标准容器vector、deque、list等均符合这些需求,默认情况下没有为stack指定特定的底层容器时,默认情况下就使用deque。

1.2 stack的使用

下面是stack的接口函数及其功能介绍:

函数说明接口说明
stack()构造空的栈
empty()检测stack是否为空
size()返回stack中的元素的个数
top()返回栈顶元素的作用
push()将元素val压入到stack中
pop()

将stack中栈顶元素弹出

下面我们来看下stack在一些问题中的使用:

我们先来看几道算法设计题:

leetcode155,最小栈

 对于这个题目我们可以使用两个stack来实现这个最小栈,首先给一个主体栈s和一个辅助栈min_s

里面存储最小值,当我们的元素入栈时如果辅助栈是空的或者val的值小于min_s的栈顶元素就将val入栈。出栈时如果我们主体栈的栈顶元素和我们的辅助栈的栈顶元素相等的话辅助栈的栈顶元素也出栈。取栈顶元素top()就直接返回s.top()即可,取最小值时就直接返回min_s.top()即可。

下面是参考代码:

class MinStack {
public:MinStack() {}void push(int val) {//将val压入主体栈中s.push(val);//如果最小栈为空或者val小于最小栈的栈顶元素就将val也压入进最小栈中if(min_s.empty() || val <= min_s.top()){min_s.push(val);}}void pop() {//出栈时如果主体栈的栈顶元素和最小栈的栈顶元素相同时最小栈也将栈顶元素弹出if(s.top() == min_s.top()){min_s.pop();}s.pop();}//返回主体栈的top即可int top() {return s.top();}//返回最小栈的栈顶元素即可int getMin() {return min_s.top();}
private://定义一个主体栈和一个存放最小值的栈stack<int> s;stack<int> min_s;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

牛客网JZ31,栈的压入弹出序列

对于这一题就是一个进栈出栈的一个过程模拟,我们先定义出一个栈然后定义一个维护出栈序列的下标,最后我们将进栈序列中的元素进栈,如果栈不为空并且栈顶元素和出栈元素相同就将栈顶元素出栈,然后将指向出栈序列的popi向后走一步。出循环后如果栈为空就是匹配返回true,如果栈不为空就返回false。

下面是参考代码:

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code here//定义一个栈,模拟进栈过程stack<int> s;//定义一个出栈下标,维护出栈序列int popi = 0;//进栈for(auto e : pushV){s.push(e);//如果栈不为空并且出栈队列对应值等于栈顶元素就将栈顶元素弹出,然后将出栈序列向后走一步while(!s.empty() && popV[popi] == s.top()){s.pop();popi++;}}//如果栈为空则匹配否则不匹配return s.empty();}
};

通过这两到例题我们应该也就了解了stack的使用,下面我们来看下queue的用法。

二、queue的简单介绍和使用

2.1 queue的介绍

1.queue也就是队列,也是一种容器适配器,专门用于先进先出的上下文操作中,从容器一端进数据,另一端出数据。

2.queue作为容器适配器实现,容器适配器就是将特定的容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素,元素从队尾入队列,从队头出队列。

3.底层容器可以是标准容器类模版之一,也可以是其他专门设计的容器类。queue的底层容器至少需要支持一下操作:

  • empty:判断队列是否为空
  • size:返回队列中有效元素中的个数
  • front:返回队头元素的引用
  • back:返回队尾元素的引用
  • push_back:在队列尾部入队列
  • pop_back:在队列头部出队列

4. 标准容器类deque和list符合这些要求,默认情况下,如果没有为queue实例化指定容器类,则默认使用deque。

2.2 queue的使用

下面是queue的接口函数以及它的接口功能:

接口函数接口说明
queue()构造空的队列
empty()检测队列是否为空,为空就放回true,否则返回false
size()返回队列中的有效元素个数
front返回队头元素的引用
back()返回队尾元素的引用
push()将元素进队列
pop()将元素出队列

下面我们通过一个题目来了解一下queue的使用:

leetcode102,二叉树的层序遍历

对于这一题我们可以借助队列queue来解决,我们先定义一个二维数组来存放返回值,然后定义一个queue辅助遍历,定义一个level_size来存放没层的节点,然后先将头结点入队,如果队列不为空就进行外层循环,内层循环负责将遍历到的值放进管理这一层节点的数组v中,然后再将下一层的节点带入,出内层循环后更新level_size和ret数组,即将level_size更新为目前队列中的元素个数,将该层的节点数组v,尾插到ret数组中,最后返回ret数组即可。

参考代码如下:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {// 定义一个二维数组作为返回数组vector<vector<int>> ret;// 如果二叉树是空树就直接返回空数组if (root == nullptr) {return ret;}// 定义一个辅助队列queue<TreeNode*> q;// 将root入栈q.push(root);// 记录每层的节点数int level_size = 1;//队列不为空就进行循环while (!q.empty()) {//定义一个数组记录每层的节点vector<int> v;//遍历这一层的节点并将下一层的节点带入while (level_size--) {TreeNode* front = q.front();v.push_back(front->val);q.pop();if (front->left) {q.push(front->left);}if (front->right) {q.push(front->right);}}//更新层节点个数level_size = q.size();//将这一层的节点放到返回数组中去ret.push_back(v);}//出循环后返回最终结果return ret;}
};

关于stack和queue的使用这篇博客就讲到这里,大家可以自行通过一些算法题去练习一下,也建议能够对博客里的例题能够理解后去自己实现一下。

相关文章:

stack和queue(1)

一、stack的简单介绍和使用 1.1 stack的介绍 1.stack是一种容器适配器&#xff0c;专门用在具有先进后出&#xff0c;后进先出操作的上下文环境中&#xff0c;其删除只能从容器的一端进行元素的插入和弹出操作。 2.stack是作为容器适配器被实现的&#xff0c;容器适配器即是…...

前端3剑客(第1篇)-初识HTML

100编程书屋_孔夫子旧书网 当今主流的技术中&#xff0c;可以分为前端和后端两个门类。 前端&#xff1a;简单的理解就是和用户打交道 后端&#xff1a;主要用于组织数据 而前端就Web开发方向来说&#xff0c; 分为三门语言&#xff0c; HTML、CSS、JavaScript 语言作用HT…...

植被变化趋势线性回归以及可视化

目录 植被变化线性回归ee.Reducer.linearFit().reduce()案例:天水市2004-2023年EVI线性回归趋势在该图中,使用了从红色到蓝色的渐变来表示负趋势到正趋势。红色代表在某段时间中,植被覆盖减少,绿色表示持平,蓝色表示植被覆盖增加。 植被变化线性回归 该部分参考Google…...

大话设计模式学习笔记

目录 工厂模式策略模式备忘录模式&#xff08;快照模式&#xff09;代理模式单例模式迭代器模式访问者模式观察者模式解释器模式命令模式模板方法模式桥接模式适配器模式外观模式享元模式原型模式责任链模式中介者模式装饰模式状态模式 工厂模式 策略模式 核心&#xff1a;封装…...

MiniMax公司介绍

MiniMax是一家专注于通用人工智能技术的科技公司&#xff0c;成立于2021年12月。公司致力于成为通用人工智能时代基础设施建设者和内容应用创造者&#xff0c;积极投身于中国人工智能技术高速发展的时代大潮。MiniMax的团队由多位在人工智能领域有着丰富经验的专家组成&#xf…...

lucene 9.10向量检索基本用法

Lucene 9.10 中的 KnnFloatVectorQuery 是用来执行最近邻&#xff08;k-Nearest Neighbors&#xff0c;kNN&#xff09;搜索的查询类&#xff0c;它可以在一个字段中搜索与目标向量最相似的k个向量。以下是 KnnFloatVectorQuery 的基本用法和代码示例。 1. 索引向量字段 首先…...

【2023百度之星初赛】跑步,夏日漫步,糖果促销,第五维度,公园,新材料,星际航行,蛋糕划分

目录 题目&#xff1a;跑步 思路&#xff1a; 题目&#xff1a;夏日漫步 思路&#xff1a; 题目&#xff1a;糖果促销 思路&#xff1a; 题目&#xff1a;第五维度 思路&#xff1a; 题目&#xff1a;公园 思路&#xff1a; 新材料 思路&#xff1a; 星际航行 思路…...

vs2019 QT UI 添加新成员或者控件代码不提示问题解决方法

右键点击头文件&#xff0c;添加ui的头文件 添加现有项 找到uic目录的头文件 打开ui,QtWidgetsApplication2.ui,进行测试 修改一个名字&#xff1a; 重点&#xff1a; 设置一个布局&#xff1a; 点击生成解决方案&#xff1a; 以后每次添加控件后&#xff0c;记得点击保存 这样…...

【面试八股总结】MySQL事务:事务特性、事务并行、事务的隔离级别

参考资料&#xff1a;小林coding 一、事务的特性ACID 原子性&#xff08;Atomicity&#xff09; 一个事务是一个不可分割的工作单位&#xff0c;事务中的所有操作&#xff0c;要么全部完成&#xff0c;要么全部不完成&#xff0c;不会结束在中间某个环节。原子性是通过 undo …...

STL用法总结

文章目录 vector构造常用函数遍历适用情形注意事项使用迭代器删除可能会出现的错误 Set & MultiSet&#xff08;不能用sort,会自动排序&#xff09;构造常用函数删除&#xff0c;查找遍历 unordered_set(不排序集合&#xff09;&#xff0c;unordered_multiset Map & M…...

他人项目二次开发——慎接

接了一个朋友的项目——开发及运营迭代差不多2年多了&#xff0c;整体样子移动端和PC都能正常使用&#xff0c;但后期的扩展性及新功能添加出现瓶颈。 因此给了一部分钱&#xff0c;让我接手来开发——重构架构。 背景说明 朋友公司的技术人员是我帮忙招聘的&#xff0c;相关技…...

k8s之PV、PVC

文章目录 k8s之PV、PVC一、存储卷1、存储卷定义2、存储卷的作用2.1 数据持久化2.2 数据共享2.3 解耦2.4 灵活性 3、存储卷的分类3.1 emptyDir存储卷3.1.1 定义3.1.2 特点3.1.3 用途3.1.4 示例 3.2 hostPath存储卷3.2.1 定义3.2.2 特点3.2.3 用途3.2.4 示例 3.3 NFS存储卷3.3.1 …...

新人学习笔记之(JavaScript作用域)

一、作用域 1.通常来说&#xff0c;一段程序代码中所用的名字并不总是有效和可用的&#xff0c;而限定这个名字的可用性的代码范围就是这个名字的作用域。作用域的使用提高了程序逻辑的局部性&#xff0c;增强了程序的可靠性&#xff0c;减少了名字冲突 二、变量的作用域 1.变…...

图论第一天

在单位摸鱼&#xff0c;地铁上看了个开始&#xff0c;图论开了个头&#xff0c;后面也希望能往这个方向上转&#xff0c;努努力吧。 一周没做题啦&#xff0c;后面坚持继续做题&#xff0b;二刷&#xff0c;接着记录每一天&#xff01;&#xff01;&#xff01;加油&#xff0…...

革新风暴来袭:报事报修系统小程序如何重塑报事报修体验?

随着数字化、智能化的发展&#xff0c;已经应用在我们日常生活和工作的方方面面。那么&#xff0c;你还在为物业报修而头疼吗&#xff1f;想象一下&#xff0c;家里的水管突然爆裂&#xff0c;你急忙联系物业&#xff0c;时常面临物业电话忙音、接听后才进行登记繁琐的报修单、…...

linux各个日志的含义 以及使用方法

在Linux系统上&#xff0c;系统日志文件通常存储在/var/log/目录下。可以通过查看这些日志文件来了解系统的操作记录、错误信息和其他相关信息。以下是一些常见的系统日志文件以及它们包含的信息&#xff1a; /var/log/messages&#xff1a;这是一个常见的系统日志文件&#xf…...

详解 Spark 核心编程之 RDD 持久化

一、问题引出 /** 案例&#xff1a;对同一份数据文件分别做 WordCount 聚合操作和 Word 分组操作 期望&#xff1a;针对数据文件只进行一次分词、转换操作得到 RDD 对象&#xff0c;然后再对该对象分别进行聚合和分组&#xff0c;实现数据重用 */ object TestRDDPersist {def …...

创新融合,5G+工业操作系统引领未来工厂

为加速企业完成生产制造自动化和经营管理自动化&#xff0c;从而走向未来工厂&#xff0c;蓝卓不断探索supOS工业操作系统与前沿技术的的创新融合&#xff0c;而5G技术为工业操作系统提供了更多元化的赋能手段和想象空间。目前&#xff0c;supOS围绕生产、安全、质检、监控等领…...

自监督表示学习和神经音频合成实现语音修复

关键词&#xff1a;语音修复、自监督模型、语音合成、语音增强、神经声码器 语音和/或音频修复的目标是增强局部受损的语音和/或音频信号。早期的工作基于信号处理技术&#xff0c;例如线性预测编码、正弦波建模或图模型。最近&#xff0c;语音/音频修复开始使用深度神经网络&a…...

【论文复现|智能算法改进】融合黑寡妇思想的蜣螂优化算法

目录 1.算法原理2.改进点3.结果展示4.参考文献5.代码获取 1.算法原理 【智能算法】蜣螂优化算法&#xff08;DBO&#xff09;原理及实现 2.改进点 ICMIC混沌映射 z n 1 sin ⁡ ( α z n ) , α ∈ ( 0 , ∞ ) (1) z_{n1}\sin(\frac{\alpha}{z_n}),\alpha\in(0,\infty)\ta…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...