RustPrimer
  • Introduction
  • 初识Rust
  • 安装Rust
    • Linux
    • Mac
    • Windows
    • 版本管理工具: rustup
  • 编辑器
    • 前期准备
    • vim
    • emacs
    • vscode
    • atom
    • sublime
    • visual studio
    • spacemacs
  • Rust快速入门
    • Rust旅程
    • 变量绑定与原生类型
    • 数组、动态数组和字符串
    • 结构体与枚举
    • 控制流
    • 函数与方法
    • 特性
    • 注释与文档
    • 输入输出流
  • Cargo项目管理器
  • 基本程序结构
    • 注释
    • 条件
    • 循环
  • 类型、运算符和字符串
    • 基础类型
    • 复合类型
    • 字符串类
    • 基础运算符和字符串格式化
  • 函数
    • 函数参数
    • 函数返回值
    • 语句和表达式
    • 高阶函数
  • 模式匹配
    • match关键字
    • 模式 pattern
  • 特征 Trait
    • trait关键字
    • trait对象
  • 泛型
  • 可变性、所有权、租借和生命期
    • 所有权
    • 引用和借用
    • 生命周期
  • 闭包
    • 闭包的语法
    • 闭包的实现
    • 闭包作为参数和返回值
  • 集合类型 Collections
    • 动态数组 Vec
    • 哈希表 HashMap
  • 迭代器
    • 迭代器、适配器、消费者
  • 模块和包系统、Prelude
    • 模块 module 和包 crate
    • Prelude
  • Option、Result与错误处理
  • 输入与输出
  • 宏系统
  • 堆、栈与Box
  • 几种智能指针
    • Rc, Arc
    • Mutex, RwLock
    • Cell, RefCell
  • 类型系统中的几个常见 Trait
    • Into/From 及其在 String 和 &str 互转上的应用
    • AsRef, AsMut
    • Borrow, BorrowMut, ToOwned
    • Deref 与 Deref coercions
    • Cow 及其在 String 和 &str 上的应用
  • Send 和 Sync
  • 并发,并行,多线程编程
    • 线程
    • 消息传递
    • 共享内存
    • 同步
    • 并行
  • Unsafe、原始指针
    • Unsafe
    • 原始指针
  • FFI
    • rust调用ffi函数
    • 将rust编译成库
  • 运算符重载
  • 属性和编译器参数
    • 属性
    • 编译器参数
  • Cargo参数配置
  • 测试与评测
    • 测试 (testing)
    • 评测 (benchmark)
  • 代码风格
  • Any与反射
  • 安全(safe)
  • 常用数据结构实现
    • 栈结构
    • 队列
    • 二叉树
    • 优先队列
    • 链表
    • 图结构
  • 标准库介绍
    • 系统命令:调用grep
    • 目录操作:简单grep
    • 网络模块:W回音
  • 实战篇
    • 实战:Json处理
    • 实战:Web 应用开发入门
    • 实战:使用Postgresql数据库
  • 附录-术语表
Powered by GitBook
On this page
  • 队列简介
  • 队列实现
  • 练习

Was this helpful?

  1. 常用数据结构实现

队列

队列简介

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

在队列的形成过程中,可以利用线性链表的原理,来生成一个队列。基于链表的队列,要动态创建和删除节点,效率较低,但是可以动态增长。队列采用的 FIFO(first in first out),新元素(等待进入队列的元素)总是被插入到链表的尾部,而读取的时候总是从链表的头部开始读取。每次读取一个元素,释放一个元素。所谓的动态创建,动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成,遍历也方便。

队列实现

下面看一下我们使用 Vec 来实现的简单 Queue:

主要实现的new( ), push( ), pop( )三个方法

#[derive(Debug)]
struct Queue<T> {
    qdata: Vec<T>,
}

impl <T> Queue<T> {
    fn new() -> Self {
        Queue{qdata: Vec::new()}
    }

    fn push(&mut self, item:T) {
        self.qdata.push(item);
    }

    fn pop(&mut self) -> T{
        self.qdata.remove(0)
    }
}

fn main() {
    let mut q = Queue::new();
    q.push(1);
    q.push(2);
    println!("{:?}", q);
    q.pop();
    println!("{:?}", q);
    q.pop();
}

练习

看起来比我们在上一节实现的Stack简单多了。不过这个Queue实现是有Bug的。

练习:在这个代码的上找到 Bug,并修改。

提示:pop( )方法有 Bug,请参考 Stack 小节的实现,利用 Option 来处理。

Previous栈结构Next二叉树

Last updated 5 years ago

Was this helpful?