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

数据结构与算法-Rust 版读书笔记-2线性数据结构-队列

数据结构与算法-Rust 版读书笔记-2线性数据结构-队列

1、队列:先进先出

队列是项的有序集合,其中,添加新项的一端称为队尾,移除项的另一端称为队首。一个元素在从队尾进入队列后,就会一直向队首移动,直到它成为下一个需要移除的元素为止。

2、Rust 预备知识

1、Some

rust为了处理情况设置的两个枚举类型,分别是enum Option 和enum Result。

Option的枚举情况有两种,分别是代表有的Some()和代表无的None。 如果是有返回值,则可以通过if let,match,unwrap,?等多种方法对应情况取出Some包裹的值,如果没有则是None。

Result的枚举情况也是有两种,表示正确的Ok()和表示错误的Err()。同样也是match,unwrap等等对应方法去提取。分别提取对应情况的内容。

3、队列的 Rust 代码实现、运行结果

queue.rs

/** @Description: * @Author: tianyw* @Date: 2023-12-10 17:43:34* @LastEditTime: 2023-12-11 21:46:30* @LastEditors: tianyw*/
// 定义队列
#[derive(Debug)] // Debug 是派生宏的名称,此语句为 Queue 结构体实现了 Debug traitpub struct Queue<T> { // pub 表示公开的cap: usize, // 容量data: Vec<T>, // 数据容器
}impl<T> Queue<T> { // impl 用于定义类型的实现,如实现 new 方法、is_empty 方法等// 初始化空栈pub fn new(size: usize) -> Self { // 指代 Queue 类型Self {cap: size,data:Vec::with_capacity(size)}}pub fn is_empty(&self) -> bool {0 == Self::len(&self)}pub fn is_full(&self) -> bool {self.len() == self.cap}pub fn len(&self) -> usize { // &self 只可读self.data.len()}// 清空pub fn clear(&mut self) { // &mut self 可读、可写self.data = Vec::with_capacity(self.cap)}// 判断是否有剩余空间,如果有的话,就将数据添加到队列中pub fn enquue(&mut self, val: T) -> Result<(), String> {if self.len() == self.cap {return  Err("No space available".to_string());}self.data.insert(0, val);Ok(())}// 数据出队pub fn dequeue(&mut self) -> Option<T> {if self.len() > 0 {self.data.pop()}else {None}}// 以下是为队列实现的迭代功能// into_iter:队列改变,成为迭代器// iter: 队列不变,得到不可变迭代器// iter_mut: 队列不变,得到可变迭代器pub fn into_iter(self) -> IntoIter<T> {IntoIter(self)}pub fn iter(&self) -> Iter<T> {let mut iterator = Iter { stack: Vec::new() };for item in self.data.iter() {iterator.stack.push(item);}iterator}pub fn iter_mut(&mut self) -> IterMut<T> {let mut iterator = IterMut { stack: Vec::new() };for item in self.data.iter_mut() {iterator.stack.push(item);}iterator}}// 实现三种迭代功能
pub struct IntoIter<T>(Queue<T>);
impl<T:Clone> Iterator for IntoIter<T> {type Item = T;fn next(&mut self) -> Option<Self::Item> {if !self.0.is_empty() {Some(self.0.data.remove(0))} else {None}}
}pub struct Iter<'a,T:'a> { stack: Vec<&'a T>, }
impl<'a,T> Iterator for Iter<'a,T> {type Item = &'a T;fn next(&mut self) -> Option<Self::Item> {if 0 != self.stack.len() {Some(self.stack.remove(0)) // 索引移除}else {None}}
}pub struct IterMut<'a,T:'a> { stack: Vec<&'a mut T> }
impl<'a,T> Iterator for IterMut<'a,T> {type Item = &'a mut T;fn next(&mut self) -> Option<Self::Item> {if 0 != self.stack.len() {Some(self.stack.remove(0))}else {None}}
}    

main.rs

/** @Description: * @Author: tianyw* @Date: 2023-12-11 21:29:04* @LastEditTime: 2023-12-11 21:54:22* @LastEditors: tianyw*/mod queue;
fn main() {basic();iter();fn basic() {let mut q = queue::Queue::new(4);let _r1 = q.enquue(1);let _r2 = q.enquue(2);let _r3 = q.enquue(3);let _r4 = q.enquue(4); // 入队if let Err(error) = q.enquue(5) {println!("Enqueue error:{error}")}if let Some(data) = q.dequeue() { // 出队println!("dequeue data: {data}");}else {println!("empty queue");}println!("empty: {}, len: {}", q.is_empty(),q.len());println!("full: {}",q.is_full());println!("q: {:?}",q);q.clear();println!("{:?}",q);}fn iter() {let mut q = queue::Queue::new(4);let _r1 = q.enquue(1);let _r2 = q.enquue(2);let _r3 = q.enquue(3);let _r4 = q.enquue(4);let sum1 = q.iter().sum::<i32>();let mut addend = 0;for item in q.iter_mut() {*item += 1;addend += 1;}let sum2 = q.iter().sum::<i32>(); // vec 的 sum 方法println!("{sum1} + {addend} = {sum2}");println!("sum = {}",q.into_iter().sum::<i32>())}
}

cargo run 运行结果

在这里插入图片描述

队列的典型应用是模拟以FIFO方式管理数据的真实场景。

应用:烫手山芋游戏

// hot_potato.rsfn hot_potato(names: Vec<&str>, num: usize) -> &str {// 初始化队列,将人名入队let mut q = Queue::new(names.len());for name in names { let _nm = q.enqueue(name); }while q.size() > 1 {// 出入栈中的人名,相当于传递山芋for _i in 0..num {let name = q.dequeue().unwrap();let _rm = q.enqueue(name);}// 出入栈达到num次,删除一个人名let _rm = q.dequeue();}q.dequeue().unwrap()
}fn main() {let name = vec!["Mon","Tom","Kew","Lisa","Marry","Bob"];let survivor = hot_potato(name, 8);println!("The survival person is {survivor}");// 输出“The survival person is Marry”
}

注意,在上面的实现中,计数值8大于队列中的人名数量6。但这不存在问题,因为队列就像一个圈,到了队尾就会重新回到队首,直至达到计数值。

相关文章:

数据结构与算法-Rust 版读书笔记-2线性数据结构-队列

数据结构与算法-Rust 版读书笔记-2线性数据结构-队列 1、队列&#xff1a;先进先出 队列是项的有序集合&#xff0c;其中&#xff0c;添加新项的一端称为队尾&#xff0c;移除项的另一端称为队首。一个元素在从队尾进入队列后&#xff0c;就会一直向队首移动&#xff0c;直到…...

Android Kotlin Viewbinding封装

目录 Viewbinding配置 Activity封装 Activity使用 Fragment封装 Fragment使用 Dialog封装 Dialog使用 Viewbinding配置 android { viewBinding { enabled true } } Activity封装 import android.os.Bundle import android.view.LayoutInflater import androidx.ap…...

Flutter:web项目跨域问题解决

前后端解决系列 文章目录 一、Flutter web客户端解决本地环境调试跨域问题二、Flutter web客户端解决线上环境跨域问题 一、Flutter web客户端解决本地环境调试跨域问题 就一句命令【--web-browser-flag "--disable-web-security"】&#xff0c;用来屏蔽浏览器域名请…...

汽车标定技术(十二)--A2L文件生成的方法

目录 1.工具生成 1.1 CANape/ASAP2 Studio 1.2 ASAP2ToolKit 1.3 Matlab/Simulink 2.手写A2L要点 3.小结 A2L文件的制作一直以来是一个很少有人关注的方向,不管是标定工程师还是Slave协议栈的开...

《PySpark大数据分析实战》-03.了解Hive

&#x1f4cb; 博主简介 &#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是wux_labs。&#x1f61c; 热衷于各种主流技术&#xff0c;热爱数据科学、机器学习、云计算、人工智能。 通过了TiDB数据库专员&#xff08;PCTA&#xff09;、TiDB数据库专家&#xff08;PCTP…...

经验分享|MySQL分区实战(RANGE)

概述 分区概述 在 MySQL 中&#xff0c; InnoDB存储引擎长期以来一直支持表空间的概念。在 MySQL 8.0 中&#xff0c;同一个分区表的所有分区必须使用相同的存储引擎。但是&#xff0c;也可以为同一 MySQL 服务器甚至同一数据库中的不同分区表使用不同的存储引擎。 通俗地讲…...

Arrays.asList() 和 Collections.singletonList()

Arrays.asList() 和 Collections.singletonList() 概述 List 是我们使用Java时常用的集合类型。众所周知&#xff0c;我们可以轻松地在一行中初始化列表。例如&#xff0c;当我们想要初始化一个只有一个元素的List时&#xff0c;我们可以使用Arrays.asList&#xff08;&#…...

Firmware Analysis Plus (Fap)固件模拟安装教程(最新)

最近在搞IoT的研究&#xff0c;但是难在设备比较难弄&#xff0c;只有固件&#xff0c;而没有设备&#xff0c;买吧&#xff0c;又太费钱&#xff0c;不划算。好在有很多项目可以在模拟环境中运行固件。但是几乎没有一个平台能够模拟所有硬件设备。IoT产品的架构也不尽相同。 …...

使用包、Crate 和模块管理项目(上)

目录 1、包和Crate 2、定义模块来控制作用域与私有性 2.1 在模块中对相关代码进行分组 3、引用模块项目的路径 3.1 使用 pub 关键字暴露路径 二进制和库 crate 包的最佳实践 3.2 super 开始的相对路径 3.3 创建公有的结构体和枚举 Rust 有许多功能可以让你管理代码的组…...

【Kotlin】

Lambda 就是一小段可以作为参数传递的代码。 因为正常情况下&#xff0c;我们向某个函数传参时只能传入变量&#xff0c;而借助Lambda 却允许传入一小段代码。 Lambda 表达式的语法结构&#xff1a; {参数名1: 参数类型, 参数名2: 参数类型 -> 函数体}首先&#xff0c;最外…...

JavaDay17

创建不可变集合 import java.util.Iterator; import java.util.List;public class Test {public static void main(String[] args) {/*创建不可变的List集合* "张三" "李四" "王五" "赵六*///一旦创建之后 是无法进行修改的 在下面的代码…...

Python爬取酷我音乐

&#x1f388; 博主&#xff1a;一只程序猿子 &#x1f388; 博客主页&#xff1a;一只程序猿子 博客主页 &#x1f388; 个人介绍&#xff1a;爱好(bushi)编程&#xff01; &#x1f388; 创作不易&#xff1a;喜欢的话麻烦您点个&#x1f44d;和⭐&#xff01; &#x1f388;…...

项目实战第四十七讲:易宝支付对接详解(保姆级教程)

易宝支付对接(保姆级教程) 为了实现项目的支付需求,公司选择了易宝支付进行对接,本文是项目实战第四十七讲,详解易宝支付对接。 文章目录 易宝支付对接(保姆级教程)1、需求背景2、流程图3、技术方案4、相关接口4.1、入驻相关(商户入网)4.2、账户相关接口(充值、提现、…...

python的websocket方法教程

WebSocket是一种网络通信协议&#xff0c;它在单个TCP连接上提供全双工的通信信道。在本篇文章中&#xff0c;我们将探讨如何在Python中使用WebSocket实现实时通信。 websockets是Python中最常用的网络库之一&#xff0c;也是websocket协议的Python实现。它不仅作为基础组件在…...

Qt处理焦点事件(获得焦点,失去焦点)

背景&#xff1a; 我只是想处理焦点动作&#xff0c;由于懒&#xff0c;上网一搜&#xff0c;排名靠前的一位朋友&#xff0c;使用重写部件的方式实现。还是因为懒&#xff0c;所以感觉复杂了。于是又花了一分钟解决了一下。 所以记录下来&#xff0c;以免以后忘了。 思路&a…...

SiteGround如何设置WordPress网站自动更新

SiteGround Autoupdate功能会自动帮我们更新在他们这里托管的所有WordPress网站&#xff0c;这样做是为了保证网站安全&#xff0c;并且让它们一直保持最新状态。他们会根据我们选择的设置自动更新不同版本的WordPress&#xff0c;包括主要版本和次要版本。在每次自动更新之前&…...

http代理和SOCK5代理谁更安全?

在这个网络化的时代&#xff0c;我们常常听到HTTP代理和SOCKS5代理这两个名词&#xff0c;不过很多人并不了解是什么意思。今天&#xff0c;我们将揭开这两种代理的神秘面纱&#xff0c;看看到底HTTP代理和SOCKS5代理哪个更安全&#xff1f; HTTP代理&#xff1a;高效通信的“枢…...

Kotlin关键字二——constructor和init

在关键字一——var和val中最后提到了构造函数&#xff0c;这里就学习下构造函数相关的关键字: constructor和init。 主要构造(primary constructor) kotlin和java一样&#xff0c;在定义类时就自动生成了无参构造 // 会生成默认的无参构造函数 class Person{ }与java不同的是…...

java的long类型超过9位报错:the literal 987654321000 of type int is out of range

java的long类型超过9位报错 1、报错提示2、报错截图3、解决办法4、参考文章 1、报错提示 the literal 987654321000 of type int is out of range 2、报错截图 3、解决办法 long类型是一种用于表示较大整数的数据类型&#xff0c;范围比int类型更广泛。然而&#xff0c;即使…...

【Java期末复习资料】(4)模拟卷

有不会的题可以后台问我的哦&#xff0c;看见了就会回。 本文章主要是模拟卷&#xff0c;知识点例题简答题已经发过了&#xff0c;可以在主页专栏Java中找一下 一、单项选择题 1. 编译 Java Application 源程序文件将产生相应的字节码文件&#xff0c;这些字节码文件的扩展名为…...

通信萌新们注意了!今天咱们玩点刺激的——用MATLAB手搓各种QAM调制的性能对比。准备好你的小本本,咱们边写代码边分析,包教包会

基于4QAM&#xff0c;16QAM&#xff0c;64QAM调制方式下经过AWGN信道的性能分析 均包含加噪声前后的星座图、误码率和误符号率性能对比&#xff0c;该程序一共10张仿真图&#xff0c;可学习性非常强先上硬货&#xff0c;看看怎么生成4QAM的星座图。掏出这段代码&#xff1a; M …...

TPAMI 2025 | 港城大团队新作:强化学习引导 ODE 轨迹,提升图像复原性能

点击上方“小白学视觉”&#xff0c;选择加"星标"或“置顶” 重磅干货&#xff0c;第一时间送达在计算机视觉领域&#xff0c;图像恢复一直是核心研究方向之一——从模糊的监控画面中还原清晰细节、让水下拍摄的照片重现真实色彩、给低光照的夜景图像提亮增晰&#x…...

Windows系统性能优化指南:使用RyTuneX提升系统响应速度

Windows系统性能优化指南&#xff1a;使用RyTuneX提升系统响应速度 【免费下载链接】RyTuneX RyTuneX is a cutting-edge optimizer built with the WinUI 3 framework, designed to amplify the performance of Windows devices. Crafted for both Windows 10 and 11. 项目地…...

ERNIE-4.5-0.3B-PT创意写作实战:用AI帮你生成有画面感的场景描述

ERNIE-4.5-0.3B-PT创意写作实战&#xff1a;用AI帮你生成有画面感的场景描述 1. 为什么需要AI辅助创意写作 在内容创作领域&#xff0c;最令人头疼的莫过于如何让文字"活起来"。传统写作往往面临三大痛点&#xff1a; 画面感不足&#xff1a;描述停留在表面&#…...

告别手动重启!用宝塔PM2管理器实现Node.js热更新(2023最新配置指南)

2023终极指南&#xff1a;用宝塔PM2打造Node.js热更新开发流水线 每次保存代码都要手动重启服务&#xff1f;还在为部署中断用户体验而头疼&#xff1f;作为经历过数百次深夜紧急部署的全栈开发者&#xff0c;我总结出一套零中断热更新方案。只需15分钟配置&#xff0c;让你的N…...

FT232串口在Ubuntu22.04上不稳定?3步搞定驱动冲突问题

FT232串口在Ubuntu 22.04上的稳定性优化实战指南 当你正在调试一个物联网设备&#xff0c;突然发现串口连接莫名其妙断开&#xff0c;那种感觉就像在高速公路上爆胎——既突然又让人抓狂。Ubuntu 22.04作为当前LTS版本&#xff0c;本应提供稳定的开发环境&#xff0c;但FTDI芯片…...

PCB开窗技术:提升电流承载能力的关键工艺

1. PCB开窗技术解析&#xff1a;从概念到应用在PCB设计领域&#xff0c;"开窗"这个术语经常被经验丰富的工程师挂在嘴边&#xff0c;但对于刚入行的新手来说&#xff0c;这个看似简单的操作背后却蕴含着不少设计门道。作为一名有十年硬件设计经验的工程师&#xff0c…...

KS-Downloader:快手无水印内容获取与管理的专业解决方案

KS-Downloader&#xff1a;快手无水印内容获取与管理的专业解决方案 【免费下载链接】KS-Downloader 快手&#xff08;KuaiShou&#xff09;视频/图片下载工具&#xff1b;数据采集工具 项目地址: https://gitcode.com/gh_mirrors/ks/KS-Downloader 在短视频内容创作与传…...

让屏幕标注像在纸上写字一样自然:gInk 三分钟上手指南

让屏幕标注像在纸上写字一样自然&#xff1a;gInk 三分钟上手指南 【免费下载链接】gInk An easy to use on-screen annotation software inspired by Epic Pen. 项目地址: https://gitcode.com/gh_mirrors/gi/gInk 你是否曾经在线上会议中&#xff0c;想快速圈出PPT的重…...

MegSpot专业视觉分析工具:从基础操作到高级应用全指南

MegSpot专业视觉分析工具&#xff1a;从基础操作到高级应用全指南 【免费下载链接】MegSpot MegSpot是一款高效、专业、跨平台的图片&视频对比应用 项目地址: https://gitcode.com/gh_mirrors/me/MegSpot 在数字媒体创作与分析领域&#xff0c;如何高效对比图片细节…...