当前位置: 首页 > 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源代码,操…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

【版本控制】GitHub Desktop 入门教程与开源协作全流程解析

目录 0 引言1 GitHub Desktop 入门教程1.1 安装与基础配置1.2 核心功能使用指南仓库管理日常开发流程分支管理 2 GitHub 开源协作流程详解2.1 Fork & Pull Request 模型2.2 完整协作流程步骤步骤 1: Fork&#xff08;创建个人副本&#xff09;步骤 2: Clone&#xff08;克隆…...

ZYNQ学习记录FPGA(二)Verilog语言

一、Verilog简介 1.1 HDL&#xff08;Hardware Description language&#xff09; 在解释HDL之前&#xff0c;先来了解一下数字系统设计的流程&#xff1a;逻辑设计 -> 电路实现 -> 系统验证。 逻辑设计又称前端&#xff0c;在这个过程中就需要用到HDL&#xff0c;正文…...

WinUI3开发_使用mica效果

简介 Mica(云母)是Windows10/11上的一种现代化效果&#xff0c;是Windows10/11上所使用的Fluent Design(设计语言)里的一个效果&#xff0c;Windows10/11上所使用的Fluent Design皆旨在于打造一个人类、通用和真正感觉与 Windows 一样的设计。 WinUI3就是Windows10/11上的一个…...