算法训练day4:栈与队列
那么我这里再列出四个关于栈的问题,大家可以思考一下。以下是以C++为例,使用其他编程语言的同学也对应思考一下,自己使用的编程语言里栈和队列是什么样的。
- C++中stack 是容器么?
- 我们使用的stack是属于哪个版本的STL?
- 我们使用的STL中stack是如何实现的?
- stack 提供迭代器来遍历stack空间么?
相信这四个问题并不那么好回答, 因为一些同学使用数据结构会停留在非常表面上的应用,稍稍往深一问,就会有好像懂,好像也不懂的感觉。
有的同学可能仅仅知道有栈和队列这么个数据结构,却不知道底层实现,也不清楚所使用栈和队列和STL是什么关系。
所以这里我再给大家扫一遍基础知识,
首先大家要知道 栈和队列是STL(C++标准库)里面的两个数据结构。
C++标准库是有多个版本的,要知道我们使用的STL是哪个版本,才能知道对应的栈和队列的实现原理。
那么来介绍一下,三个最为普遍的STL版本:
-
HP STL 其他版本的C++ STL,一般是以HP STL为蓝本实现出来的,HP STL是C++ STL的第一个实现版本,而且开放源代码。
-
P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的,被Visual C++编译器所采用,不是开源的。
-
SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现,被Linux的C++编译器GCC所采用,SGI STL是开源软件,源码可读性甚高。
接下来介绍的栈和队列也是SGI STL里面的数据结构, 知道了使用版本,才知道对应的底层实现。
来说一说栈,栈先进后出,
栈提供push 和 pop 等等接口,所有元素必须符合先进后出规则,所以栈不提供走访功能,也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
栈是以底层容器完成其所有的工作,对外提供统一的接口,底层容器是可插拔的(也就是说我们可以控制使用哪种容器来实现栈的功能)。
所以STL中栈往往不被归类为容器,而被归类为container adapter(容器适配器)。
那么问题来了,STL 中栈是用什么容器实现的?
从下图中可以看出,栈的内部结构,栈的底层实现可以是vector,deque,list 都是可以的, 主要就是数组和链表的底层实现。

我们常用的SGI STL,如果没有指定底层实现的话,默认是以deque为缺省情况下栈的底层结构。
deque是一个双向队列,只要封住一段,只开通另一端就可以实现栈的逻辑了。
SGI STL中 队列底层实现缺省情况下一样使用deque实现的。
我们也可以指定vector为栈的底层实现,初始化语句如下:
std::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈
刚刚讲过栈的特性,对应的队列的情况是一样的。
队列中先进先出的数据结构,同样不允许有遍历行为,不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。
也可以指定list 为起底层实现,初始化queue的语句如下:
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列
所以STL 队列也不被归类为容器,而被归类为container adapter( 容器适配器)。
队列
是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)
c++队列queue模板类的定义在<queue>头文件中,queue 模板类需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque 类型。
C++队列Queue类成员函数有:
back() 返回最后一个元素
empty() 如果队列空则返回真
front() 返回第一个元素
pop() 删除第一个元素
push() 在末尾加入一个元素
size() 返回队列中元素的个数
优先队列:C++优先队列类似队列,但是在这个数据结构中的元素按照一定顺序排列。
成员函数有:
1.empty() 如果优先队列为空,则返回真
2.pop() 删除第一个元素
3.push() 加入一个元素
4.size() 返回优先队列中拥有的元素的个数
5.top() 返回优先队列中有最高优先级的元素
232:用栈实现队列
class MyQueue {
public:stack<int> stIn;stack<int> stOut;MyQueue() {}void push(int x) {stIn.push(x);}int pop() {if(stOut.empty()){while(!stIn.empty()){stOut.push(stIn.top());stIn.pop();}}int result = stOut.top();stOut.pop();return result;}int peek() {int res = this->pop(); // 直接使用已有的pop函数stOut.push(res); // 因为pop函数弹出了元素res,所以再添加回去return res;}bool empty() {return stIn.empty() && stOut.empty();}
};
225:用队列实现栈
class MyStack {
public:queue<int>que1;queue<int>que2;MyStack() {}void push(int x) {que1.push(x);}int pop() {int size = que1.size();size--;while(size--){que2.push(que1.front());que1.pop();}int result = que1.front();que1.pop();que1 = que2; // 再将que2赋值给que1while (!que2.empty()) { // 清空que2que2.pop();}return result;}int top() {return que1.back();}bool empty() {return que1.empty();}
};
20:有效的括号
class Solution {
public:bool isValid(string s) {if(s.size()%2 != 0){return false;}stack<char>st;for(int i = 0;i < s.size();i++){if (s[i] == '(') st.push(')');else if (s[i] == '{') st.push('}');else if (s[i] == '[') st.push(']');else if(st.empty() || s[i] != st.top()){return false;}else st.pop();}return st.empty();}
};
1047:删除字符串中的所有相邻重复项
class Solution {
public:string removeDuplicates(string s) {stack<char>st;for (char s : s) {if (st.empty() || s != st.top()) {st.push(s);} else {st.pop(); // s 与 st.top()相等的情况}}string s2 = "";while(!st.empty()){s2 += st.top();st.pop();}reverse (s2.begin(), s2.end());return s2;}
};
150:逆波兰表达式求值
stoll():
此函数将在函数调用中作为参数提供的字符串转换为long long int。它解析str并将其内容解释为指定基数的整数,并将其作为long long int类型的值返回。
347:前k个高频元素
class Solution {
public:// 小顶堆class mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {// 要统计元素出现频率unordered_map<int, int> map; // map<nums[i],对应出现的次数>for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}// 对频率排序// 定义一个小顶堆,大小为kpriority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// 用固定大小为k的小顶堆,扫面所有频率的数值for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { // 如果堆的大小大于了K,则队列弹出,保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒序来输出到数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};
相关文章:
算法训练day4:栈与队列
那么我这里再列出四个关于栈的问题,大家可以思考一下。以下是以C为例,使用其他编程语言的同学也对应思考一下,自己使用的编程语言里栈和队列是什么样的。 C中stack 是容器么?我们使用的stack是属于哪个版本的STL?我们…...
Git cherry-pick详解
文章目录 基本用法引入多个提交代码冲突解决引入分支所有提交引入另一个代码库提交常用配置常见问题 此文在阅读前需要有一定的git命令基础,若基础尚未掌握,建议先阅读这篇文章Git命令播报详版 对于多分支的代码库,将代码从一个分支引入到另一…...
基于JS简单甘特图(IT枫斗者)
基于JS简单甘特图 基于JS简单甘特图 先来看一下效果吧,这里的需求是从早上的5点为开始时间,到第二天到凌晨5点 前期准备 其实网上有很多甘特图的实现方式,但是他们都只能具象到天,不能具体到某个时间点,而且每一个…...
你真的会判断对象是否为空吗?
首先,这个问题就很有意思,相信大部分人第一反应不就是null吗? 比如: if(str ! null){}可是,很多时候我们判断前端送过来的值,有可能是空字符串,所以更严格的写法是: if(str ! nul…...
JVM系列(十) 垃圾收集器之 Parallel Scavenge/Old
上篇文章我们讲解了单线程垃圾收集器 Serial/SerialOld ,与之相对应的多线程垃圾收集器就是 Parallel Scavenge/Old, 本文我们讲解下多线程垃圾收集器 Parallel Scavenge/Old 垃圾收集器 新生代收集器: Serial、ParNew、Parallel Scavenge&…...
华为认证实验篇-ENSP的安装(附下载地址)
ENSP(Enterprise Network Simulation Platform)是华为公司开发的一款网络仿真软件,它可以帮助网络工程师进行网络拓扑设计、网络配置、网络测试等工作。本篇文章将介绍如何在Windows操作系统上安装ENSP。后续会在专栏陆续更新ENSP的实验&…...
轻量级任务看板做任务管理
利用看板管理工作和任务,可以让团队更高效,也可以一目了然的了解任务进度及问题 1、首先创建一个任务看板 使用看板工具轻量级项目模板创建一个任务看板。 任务看板内包含:列表和任务卡片,列表一般代表任务流程及状态ÿ…...
ARM buildroot 的引入
一、X210 的 bsp 介绍 1、嵌入式 linux 产品的 bsp 介绍 (1) 大部分的 ARM 架构的 linux 平台的 bsp 的内容和结构都是相似的。 (2) bsp 一般是芯片厂家/板卡厂家提供的。 2、X210 的 linuxQT bsp 整体介绍 (1) tslib_x210_qtopia.tgz 是用来支持 QT 的触摸屏操作的应用层库。…...
Fancy 的区间(C++)(前缀和差分)
目录 1.题目描述 2.AC 1.题目描述 Fancy 的区间 时间限制: 1.000 Sec 内存限制: 128 MB 题目描述 省选终于考完了,但是还是不出成绩,Fancy 非常焦急而忧伤的等待着。 闲着无聊的 Fancy 打开书包拿出了一张纸和一支笔,在纸上画了一行n个…...
06 【Sass语法介绍-函数】
这篇文章只更新了颜色函数,由于Sass使用时间过短,其它函数参考官网 1.前言 Sass 中的函数,这在 Sass 中是比较强大的一个功能,同时使用场景和语法也比较多,所以本节内容篇幅较长,但你一定要好好学习&#…...
入参校验产品化 schema
与规则引擎不同,规则面向技术, 传入data, 返回 所有异常字段和原因. 面向技术, 先有对象,再有规则, 如何通过交互来编写schema是个难题? 和json-schema区别: 思路上就是反过来的, 面相产品, schema可视化编辑器, 是面向结构设计. 现有模型,才有数据, 才可以编程. 基于配置…...
【Linux】7、一篇文章学习 Linux 中一些硬核的常用知识
目录 一、systemctl二、软链接三、日期(date 命令)四、Linux 的时区(1) 修改时区(2) ntp 五、IP 地址六、主机名七、域名解析八、配置 Linux 的固定 IP 地址(1) 在 VMwareWorkstation 中配置 IP 地址网关和网段(IP 地址的范围)(2)…...
gpt4-如何使用
gpt-4怎么用 目前,GPT-4尚未发布或公开释放。因此,我们目前无法使用GPT-4。GPT-4是由OpenAI公司开发的人工智能语言模型,其预计能够比先前的版本GPT-3更加强大和智能化,但我们需要等待OpenAI官方发布有关GPT-4的更多信息。 如果您…...
定时每天凌晨一点在linux系统上执行一个autobuild.sh脚本如何实现?
定时每天凌晨一点在linux系统上执行一个autobuild.sh脚本如何实现? 可以使用linux的计划任务功能crontab来实现定时执行脚本。 具体步骤如下: 编辑crontab计划任务列表: bash crontab -e 这会打开一个文本编辑器,你可以在里面添加计划任务。添加一行计划任务,内容如…...
C++ 设计模式23:访问者模式
C++ 23种设计模式系列文章目录 创建型模式 第1式 工厂方法模式 第2式 抽象工厂模式 第3式 单例模式 第4式 建造者模式 第5式 原型模式 结构型模式 第6式 适配器模式 第7式 桥接模式 第8式 组合模式 第9式 装饰器模式...
使用python实现葡萄酒威士忌风味特征分类
聚类威士忌 目的和描述:苏格兰威士忌因其复杂性和多样化的风味而备受推崇。据信,生产它的苏格兰地区具有独特的风味特征。在本案例研究中,我们将根据苏格兰威士忌的风味特征对其进行分类。我们将使用的数据集包含来自几个酿酒厂的精选苏格兰威士忌,我们将尝试将威士忌聚类…...
代理IP(代理服务器)的作用和注意事项
代理IP(也称代理服务器)是一种网络技术,可以用来隐藏用户的真实IP地址并代替其发起网络请求。这种技术在许多场景下都有广泛的应用,如加速网络访问、保护个人隐私、绕过地理限制等。下面将详细介绍代理IP的原理和应用。 原理 代理…...
问题解决 | Failed to initialize NVML: Driver/library version mismatch
问题描述: Ubuntu20.04服务器上,一个docker容器正在训练模型,打开另外一个docker容器时,出现以下错误 Error response from daemon: failed to create shim task: OCI runtime create failed: runc create failed: unable to st…...
ThinkPHP模型操作上
ThinkPHP模型操作上 前言模型一、创建模型二、模型操作 总结 前言 在mvc架构中,模型的解释是写逻辑代码的地方,其实还可以这样理解,就是一串操作写在一个模型类中,就是你要完成某一项功能,将这个功能的代码写在一个mod…...
053:cesium显示网格切片标识,展示X、Y、Level 坐标
第053个 点击查看专栏目录 本示例的目的是介绍如何在vue+cesium中加载瓦片网格切分标识地图。,它在切片方案中的每个渲染图块周围绘制一个框,并在其中绘制一个标签,指示图块的 X、Y、Level 坐标。 这主要用于调试地形和图像渲染问题。 直接复制下面的 vue+cesium源代码,操…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
