Rust 数据结构与算法:2线性数据结构 之 栈

这篇具有很好参考价值的文章主要介绍了Rust 数据结构与算法:2线性数据结构 之 栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二、基础数据结构

1、线性数据结构

数组、栈、队列、双端队列、链表这类数据结构都是保存数据的容器,数据项之间的顺序由添加或删除时的顺序决定,数据项一旦被添加,其相对于前后元素就会一直保持位置不变,诸如此类的数据结构被称为线性数据结构。线性数据结构有两端,称为“左”和“右”,在某些情况下也称为“前”和“后”,当然也可以称为顶部和底部,名称不重要,重要的是这种命名展现出的位置关系表明了数据的组织方式是线性的。这种线性特性和内存紧密相关,因为内存就是一种线性硬件,由此也可以看出软件和硬件是如何关联在一起的。线性数据结构说的并非数据的保存方式,而是数据的访问方式。线性数据结构不一定代表数据项在内存中相邻。以链表为例,虽然其中的数据项可能在内存的各个位置,但访问是线性的。

2、栈

栈就是一种特别有用的线性数据结构,可用于函数调用、网页数据记录等。栈是数据项的有序集合,其中,新项的添加和移除总发生在同一端,这一端称为顶部,与之相对的另一端称为底部。栈的底部很重要,因为栈中靠近底部的项是存储时间最长的,最近添加的项最先被移除。这种排序原则有时被称为后进先出(Last In First Out,LIFO)或先进后出(First In Last Out,FILO),所以较新的项靠近顶部,较旧的项靠近底部。

栈的例子很常见,工地上堆的砖,桌子上摆的书,餐厅里摞在一起的盘子,它们都是栈的物理模型。要想拿到最下面的砖、书、盘子,就必须先把上面的都拿走。

Rust 数据结构与算法:2线性数据结构 之 栈,数据结构与算法Rust版,rust,数据结构,开发语言

栈的插入(左)和删除(右)数据的过程:从栈顶插入和删除
1、栈的抽象数据类型

栈的抽象数据类型由栈的结构和操作定义。如前所述,栈被构造为项的有序集合,其中,项的添加和移除位置被称为顶部。栈的部分操作如下。

●new():创建一个空栈,不需要参数,返回一个空栈。

●push(item):将数据项item添加到栈顶,需要item作为参数,不返回任何内容。

●pop():从栈中删除顶部的数据项,不需要参数,返回数据项,栈被修改。

●peek():从栈中返回顶部的数据项但不删除,不需要参数,不修改栈。

●is_empty():测试栈是否为空,不需要参数,返回布尔值。

●size():返回栈中数据项的数量,不需要参数,返回一个usize型整数。

●iter():返回栈的不可变迭代形式,栈不变,不需要参数。

●iter_mut():返回栈的可变迭代形式,栈可变,不需要参数。

●into_iter():改变栈为可迭代形式,栈被消费,不需要参数。

Rust 数据结构与算法:2线性数据结构 之 栈,数据结构与算法Rust版,rust,数据结构,开发语言

栈操作以及栈操作后的结果
2、栈的 Rust 代码实现

这里使用集合容器Vec作为栈的底层实现,因为Rust中的Vec提供了有序集合机制和一组操作方法,只需要选定Vec的哪一端是栈顶就可以实现其他操作了。以下栈实现假定Vec的尾部保存了栈的顶部元素,随着栈不断增长,新项将被添加到Vec的末尾。因为不知道所插入数据的类型,所以采用泛型数据类型T。此外,为了实现迭代功能,这里添加了IntoIter、Iter、IterMut三个结构体,以分别完成三种迭代功能。

代码:文章来源地址https://www.toymoban.com/news/detail-831711.html

/*
 * @Description:
 * @Author: tianyw
 * @Date: 2024-02-15 14:13:35
 * @LastEditTime: 2024-02-15 14:56:07
 * @LastEditors: tianyw
 */
#[derive(Debug)]
struct Stack<T> {
   
    size: usize,  // 栈大小
    data: Vec<T>, // 栈数据
}

impl<T> Stack<T> {
   
    // 初始化空栈
    fn new() -> Self {
   
        Self {
   
            size: 0,
            data: Vec::new(), // 以 Vec 为低层
        }
    }

    fn is_empty(&self) -> bool {
   
        0 == self.size
    }

    fn len(&self) -> usize {
   
        self.size
    }

    // 清空栈
    fn clear(&mut self) {
   
        self.size = 0;
        self.data.clear();
    }

    // 将数据保存在 Vec 的末尾
    fn push(&mut self, val: T) {
   
        self.data.push(val);
        self.size += 

到了这里,关于Rust 数据结构与算法:2线性数据结构 之 栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【零基础学Rust | 基础系列 | 数据结构】元组,数组,向量,字符串,结构体

    在Rust编程语言中,数据结构是组织和存储数据的一种方式,它们使得数据可以高效地被访问和操作。本章将详细介绍元组,数组,向量,字符串,和结构体这几种基本的数据结构。 元组是Rust编程语言中的一种复合数据类型,它可以包含多个值,这些值可以是不同类型。元组

    2024年02月11日
    浏览(58)
  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(49)
  • 【Python数据结构与算法】线性结构小结

    🌈个人主页: Aileen_0v0 🔥系列专栏:PYTHON学习系列专栏 💫\\\"没有罗马,那就自己创造罗马~\\\"   目录 线性数据结构Linear DS 1.栈Stack 栈的两种实现 1.左为栈顶,时间复杂度为O(n) 2.右为栈顶,时间复杂度O(1)   2.队列Queue 3.双端队列Deque 4.列表List 5.链表 a.无序链表的实现 b.有序链表的实

    2024年02月04日
    浏览(40)
  • 数据结构与算法 - 线性表

    编程要求 本关任务是实现 step1/Seqlist.cpp 中的SL_InsAt、SL_DelAt和SL_DelValue三个操作函数,以实现线性表中数据的插入、删除与查找等功能。具体要求如下: SL_InsAT: 在顺序表的位置i插入结点x,即插入d[i]之前,i的有效范围[0,slist-len]; SL_DelAt:删除顺序表slist的第i号结点, i的有

    2024年02月01日
    浏览(82)
  • 数据结构 - 线性表(C语言版)

    线性表分为 顺序表 和 单链表 线性表的操作主要是 查询、插入、删除 首先,定义一个顺序表的结构体 创建一个顺序表 遍历顺序表 1.1、查询 顺序查询 输出结果 1.2、插入 在position处插入元素 位置position在表中对应的序号 i = position-1 思路:将v(length-1)至vi依次后移一位,然后

    2024年02月15日
    浏览(50)
  • 【数据结构与算法_01_线性表】线性表

    定义 ● 线性表 具有相同数据类型**(同类型)**的n个数据元素有限序列 ● 三方面 ● 定义 逻辑结构 ● 相同数据类型 ● 每个数据元素所占的空间相同 ● 有限 ● 有限个元素 ● 序列 ● 是有次序的 ● 基本操作 操作— 基本操作 运算 ● 创建线性表【initList(L)】 ● 初始化线

    2024年02月11日
    浏览(35)
  • 数据结构与算法【02】—线性表

    CSDN系列专栏:数据结构与算法专栏 针对以前写的数据结构与算法系列重写(针对文字描述、图片、错误修复),改动会比较大,一直到更新完为止 通过前面数据结构与算法基础知识我们知道了数据结构的一些概念和重要性,那么本章总结下线性表相关的内容。当然,我用自己

    2024年02月05日
    浏览(48)
  • HNU数据结构与算法分析-作业2-线性结构

      1. (简答题) 4.1 假设一个线性表包含下列元素: |2,23,15,5,9 使用Shaffer编写的教材《数据结构与算法分析》的List ADT编写一些C++语句,删除值为15的元素。 (要求:采用C或C++语言描述算法) 4.6 使用Shaffer编写的教材《数据结构与算法分析》的LList类,给LList类的实现添加一个成

    2024年02月05日
    浏览(52)
  • 【数据结构】线性表的顺序存储结构及实现——C语言版

    线性表的顺序存储结构称为 顺序表 ,其基本思想是 用一段地址连续的存储单元一次存储线性表的数据元素。 设顺序表的每个元素占用 c 个存储单元,则第 i 个元素的存储地址为: 所以, 只要确定了存储顺序表的起始地址(即基地址),计算任意一个元素的存储地址的时间

    2024年03月15日
    浏览(51)
  • C语言数据结构(2)——线性表其一(顺序表)

    欢迎来到博主的新专栏——C语言数据结构 博主ID:代码小豪 再开始这篇文章之前,我们假设要对10个数据进行操作。这十个数据全都被声明成10个变量 如果我们准备为这些数据增加功能,将他们进行赋值,打印,交换等。就会发现一个特别棘手的问题,这些程序写起来太繁杂

    2024年01月19日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包