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

算法训练day4:栈与队列

那么我这里再列出四个关于栈的问题,大家可以思考一下。以下是以C++为例,使用其他编程语言的同学也对应思考一下,自己使用的编程语言里栈和队列是什么样的。

  1. C++中stack 是容器么?
  2. 我们使用的stack是属于哪个版本的STL?
  3. 我们使用的STL中stack是如何实现的?
  4. stack 提供迭代器来遍历stack空间么?

相信这四个问题并不那么好回答, 因为一些同学使用数据结构会停留在非常表面上的应用,稍稍往深一问,就会有好像懂,好像也不懂的感觉。

有的同学可能仅仅知道有栈和队列这么个数据结构,却不知道底层实现,也不清楚所使用栈和队列和STL是什么关系。

所以这里我再给大家扫一遍基础知识,

首先大家要知道 栈和队列是STL(C++标准库)里面的两个数据结构。

C++标准库是有多个版本的,要知道我们使用的STL是哪个版本,才能知道对应的栈和队列的实现原理。

那么来介绍一下,三个最为普遍的STL版本:

  1. HP STL 其他版本的C++ STL,一般是以HP STL为蓝本实现出来的,HP STL是C++ STL的第一个实现版本,而且开放源代码。

  2. P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的,被Visual C++编译器所采用,不是开源的。

  3. 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:栈与队列

那么我这里再列出四个关于栈的问题&#xff0c;大家可以思考一下。以下是以C为例&#xff0c;使用其他编程语言的同学也对应思考一下&#xff0c;自己使用的编程语言里栈和队列是什么样的。 C中stack 是容器么&#xff1f;我们使用的stack是属于哪个版本的STL&#xff1f;我们…...

Git cherry-pick详解

文章目录 基本用法引入多个提交代码冲突解决引入分支所有提交引入另一个代码库提交常用配置常见问题 此文在阅读前需要有一定的git命令基础&#xff0c;若基础尚未掌握&#xff0c;建议先阅读这篇文章Git命令播报详版 对于多分支的代码库&#xff0c;将代码从一个分支引入到另一…...

基于JS简单甘特图(IT枫斗者)

基于JS简单甘特图 基于JS简单甘特图 先来看一下效果吧&#xff0c;这里的需求是从早上的5点为开始时间&#xff0c;到第二天到凌晨5点 前期准备 其实网上有很多甘特图的实现方式&#xff0c;但是他们都只能具象到天&#xff0c;不能具体到某个时间点&#xff0c;而且每一个…...

你真的会判断对象是否为空吗?

首先&#xff0c;这个问题就很有意思&#xff0c;相信大部分人第一反应不就是null吗&#xff1f; 比如&#xff1a; if(str ! null){}可是&#xff0c;很多时候我们判断前端送过来的值&#xff0c;有可能是空字符串&#xff0c;所以更严格的写法是&#xff1a; if(str ! nul…...

JVM系列(十) 垃圾收集器之 Parallel Scavenge/Old

上篇文章我们讲解了单线程垃圾收集器 Serial/SerialOld &#xff0c;与之相对应的多线程垃圾收集器就是 Parallel Scavenge/Old&#xff0c; 本文我们讲解下多线程垃圾收集器 Parallel Scavenge/Old 垃圾收集器 新生代收集器&#xff1a; Serial、ParNew、Parallel Scavenge&…...

华为认证实验篇-ENSP的安装(附下载地址)

ENSP&#xff08;Enterprise Network Simulation Platform&#xff09;是华为公司开发的一款网络仿真软件&#xff0c;它可以帮助网络工程师进行网络拓扑设计、网络配置、网络测试等工作。本篇文章将介绍如何在Windows操作系统上安装ENSP。后续会在专栏陆续更新ENSP的实验&…...

轻量级任务看板做任务管理

利用看板管理工作和任务&#xff0c;可以让团队更高效&#xff0c;也可以一目了然的了解任务进度及问题 1、首先创建一个任务看板 使用看板工具轻量级项目模板创建一个任务看板。 任务看板内包含&#xff1a;列表和任务卡片&#xff0c;列表一般代表任务流程及状态&#xff…...

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 题目描述 省选终于考完了&#xff0c;但是还是不出成绩&#xff0c;Fancy 非常焦急而忧伤的等待着。 闲着无聊的 Fancy 打开书包拿出了一张纸和一支笔&#xff0c;在纸上画了一行n个…...

06 【Sass语法介绍-函数】

这篇文章只更新了颜色函数&#xff0c;由于Sass使用时间过短&#xff0c;其它函数参考官网 1.前言 Sass 中的函数&#xff0c;这在 Sass 中是比较强大的一个功能&#xff0c;同时使用场景和语法也比较多&#xff0c;所以本节内容篇幅较长&#xff0c;但你一定要好好学习&#…...

入参校验产品化 schema

与规则引擎不同,规则面向技术, 传入data, 返回 所有异常字段和原因. 面向技术, 先有对象,再有规则, 如何通过交互来编写schema是个难题? 和json-schema区别: 思路上就是反过来的, 面相产品, schema可视化编辑器, 是面向结构设计. 现有模型,才有数据, 才可以编程. 基于配置…...

【Linux】7、一篇文章学习 Linux 中一些硬核的常用知识

目录 一、systemctl二、软链接三、日期&#xff08;date 命令&#xff09;四、Linux 的时区(1) 修改时区(2) ntp 五、IP 地址六、主机名七、域名解析八、配置 Linux 的固定 IP 地址(1) 在 VMwareWorkstation 中配置 IP 地址网关和网段&#xff08;IP 地址的范围&#xff09;(2)…...

gpt4-如何使用

gpt-4怎么用 目前&#xff0c;GPT-4尚未发布或公开释放。因此&#xff0c;我们目前无法使用GPT-4。GPT-4是由OpenAI公司开发的人工智能语言模型&#xff0c;其预计能够比先前的版本GPT-3更加强大和智能化&#xff0c;但我们需要等待OpenAI官方发布有关GPT-4的更多信息。 如果您…...

定时每天凌晨一点在linux系统上执行一个autobuild.sh脚本如何实现?

定时每天凌晨一点在linux系统上执行一个autobuild.sh脚本如何实现&#xff1f; 可以使用linux的计划任务功能crontab来实现定时执行脚本。 具体步骤如下: 编辑crontab计划任务列表: bash crontab -e 这会打开一个文本编辑器,你可以在里面添加计划任务。添加一行计划任务,内容如…...

C++ 设计模式23:访问者模式

C++ 23种设计模式系列文章目录 创建型模式 第1式 工厂方法模式 第2式 抽象工厂模式 第3式 单例模式 第4式 建造者模式 第5式 原型模式 结构型模式 第6式 适配器模式 第7式 桥接模式 第8式 组合模式 第9式 装饰器模式...

使用python实现葡萄酒威士忌风味特征分类

聚类威士忌 目的和描述:苏格兰威士忌因其复杂性和多样化的风味而备受推崇。据信,生产它的苏格兰地区具有独特的风味特征。在本案例研究中,我们将根据苏格兰威士忌的风味特征对其进行分类。我们将使用的数据集包含来自几个酿酒厂的精选苏格兰威士忌,我们将尝试将威士忌聚类…...

代理IP(代理服务器)的作用和注意事项

代理IP&#xff08;也称代理服务器&#xff09;是一种网络技术&#xff0c;可以用来隐藏用户的真实IP地址并代替其发起网络请求。这种技术在许多场景下都有广泛的应用&#xff0c;如加速网络访问、保护个人隐私、绕过地理限制等。下面将详细介绍代理IP的原理和应用。 原理 代理…...

问题解决 | Failed to initialize NVML: Driver/library version mismatch

问题描述&#xff1a; Ubuntu20.04服务器上&#xff0c;一个docker容器正在训练模型&#xff0c;打开另外一个docker容器时&#xff0c;出现以下错误 Error response from daemon: failed to create shim task: OCI runtime create failed: runc create failed: unable to st…...

ThinkPHP模型操作上

ThinkPHP模型操作上 前言模型一、创建模型二、模型操作 总结 前言 在mvc架构中&#xff0c;模型的解释是写逻辑代码的地方&#xff0c;其实还可以这样理解&#xff0c;就是一串操作写在一个模型类中&#xff0c;就是你要完成某一项功能&#xff0c;将这个功能的代码写在一个mod…...

053:cesium显示网格切片标识,展示X、Y、Level 坐标

第053个 点击查看专栏目录 本示例的目的是介绍如何在vue+cesium中加载瓦片网格切分标识地图。,它在切片方案中的每个渲染图块周围绘制一个框,并在其中绘制一个标签,指示图块的 X、Y、Level 坐标。 这主要用于调试地形和图像渲染问题。 直接复制下面的 vue+cesium源代码,操…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...