野生前端的数据结构基础练习(2)——队列

网上的相关教程非常多,基础知识自行搜索即可。即可。 习题主要选自Orelly出版的《数据结构与算法javascript描述》一书。 参考代码可见:https://github.com/dashnowords/blogs/tree/master/Structure/Queue

队列的基本知识

  • 特点: 先进先出。
  • 用途: 模拟流程或其他带有抽象排队属性的事物或逻辑,例如时间循环队列,发布订阅模式的回调队列等等。
  • 基本方法
    • enqueue()在队尾插入一个元素
    • dequeue()从队头删除一个元素
    • getHeader()获取队头的元素
    • getTail()获取队尾的元素
    • getLength()获取队列的长度
    • isEmpty()判断队列是否为空队列
  • 需要留意的问题 使用javascript语言来理解数据结构只能够帮助我们理解结构的基本特性,由于不涉及底层的原理,所以无法深入到算法细节的时间复杂度的话题上,对此感兴趣的同学建议在学习完数据结构入门后再去学习C语言描述版的数据结构资料。

基本练习

  1. 根据栈的特性实现一个Queue类,并在后续题目中需要用队列时使用它。
  2. 编写一个函数dancingQueue(str),str中记录着前来参加舞会的人的性别,以空格分割,函数中需要实现将前来跳舞的人按性别分成两队,每当舞池中有空位时,男队和女队的排在最前面的人组成舞伴进入,如果某一队为空时,需要返回对应的消息。
  3. 实现一个PriorityQueue类,实现优先队列的功能,优先队列的元素带有权重,权重越高(一般认为数字越小权重越高)的越早出队。

课后习题(书中第五节习题)

  1. 修改Queue类,生成一个Deque类,允许从队列两端添加和删除元素,因此也叫双向队列。
  2. 使用Deque类判断一个单词是否是回文。
  3. 题目3和题目4比较简单,不再赘述。

习题思路

  1. javascript中的数组就符合双向队列的特性,试着自己去实现几个特征方法即可。
  2. Deque类可以从队列两端出队,每次从两端各出队一个元素进行比较即可。

扩展- 循环队列

循环队列书中并没有提及,它是一种特殊的队列。简单理解就是将基本队列只当做存储结构,而使用frontrear两个指针分别代表队列的头和尾,实际对外表现的队列是frontrear所指向的元素构成的。为了复用存储空间,循环队列在存储结构的实现上是首位相连的。

  • 基本要素
    • front指针指向队头
    • rear指针指向队尾
    • size队列的长度
    • length存储空间的大小
  • 基本方法
    • enqueue()元素入队
    • dequeue()元素出队
    • isEmpty()判断队空
    • isFull()判断队满
    • getSize()获取队列长度
    • getLength()获取存储空间长度
    • clear()清空队列

基本练习

实现一个CircularQueue类,并添加一个扩展方法resize(),当存储空间已满且有元素入队时,自动将存储空间扩充一倍,当元素出队造成队列长度不足存储空间的1/4时,将存储空间减半以释放空间。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏iOS技术杂谈

iOS runtime探究(五): 从runtime开始深入weak实现机理你要知道的runtime都在这里

你要知道的runtime都在这里 转载请注明出处 https://cloud.tencent.com/developer/user/1605429 本文主要讲解...

36860
来自专栏mySoul

设计模式-原型模式

关于Cloneable 接口,用途和Serializable一样为标记型接口,内部没有方法和属性,implements Cloneable 表示对象能被克隆,即...

10410
来自专栏calmound

散列表

http://blog.csdn.net/yyxaf/article/details/7527878 搜索关键词:散列函数、散列表、哈希函数、哈希表、Hash函...

387120
来自专栏java一日一条

10个惊艳的Swift单行代码

几年前,一篇表述“10个Scala函数式单行代码”的文章非常受欢迎,并且随后立马出现了其他的语言版本,例如Haskell版本,Ruby版本,Groovy版本,C...

10220
来自专栏JAVA高级架构

java面试需要掌握知识点

重点知识 由于我面试的JAVA开发工程师,针对于JAVA,需要理解的重点内容有: JVM内存管理机制和垃圾回收机制(基本每次面试都会问,一定要搞得透彻) JVM...

38650
来自专栏李海辰的专栏

Unity引擎资源管理代码分析 ( 2 )

上一篇《Unity 引擎资源管理代码分析 ( 1 ) 》讲解了 Unity 引擎资源管理代码的类型设计架构和 Resources.Load 接口的实现,本文将...

1K40
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day5 Java中的运算符

  运算符,顾名思义就是用于运算的符号,比如最简单的+-*/,这些运算符可以用来进行数学运算,举个最简单的栗子:   已知长方形的长为3cm,高为4cm,求长方...

21470
来自专栏余林丰

Effective Java通俗理解(下)

第31条:用实例域代替序数   枚举类型有一个ordinal方法,它范围该常量的序数从0开始,不建议使用这个方法,因为这不能很好地对枚举进行维护,正确应该是利用...

29290
来自专栏java一日一条

最全面的 Android 编码规范指南

这份文档参考了 Google Java 编程风格规范和 Google 官方 Android 编码风格规范。该文档仅供参考,只要形成一个统一的风格,见量知其意就可...

18240
来自专栏Crossin的编程教室

【编程课堂】有序字典 OrderedDict

编程课堂将和每周一坑一样,成为本教室公众号的一个长期固定栏目。每期讲解一个编程知识点,包括但不限于 Python 语法、模块介绍、编程小技巧等。用简短的篇幅,让...

38980

扫码关注云+社区

领取腾讯云代金券