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

发布时间:2020-06-24 05:29:26 作者:大史不说话
来源:网络 阅读:261

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

网上的相关教程非常多,基础知识自行搜索即可。

习题主要选自Orelly出版的《数据结构与算法javascript描述》一书。

参考代码可见:https://github.com/dashnowords/blogs/tree/master/Structure/Queue

队列的基本知识

基本练习

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

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

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

习题思路

  1. javascript中的数组就符合双向队列的特性,试着自己去实现几个特征方法即可。

  2. Deque类可以从队列两端出队,每次从两端各出队一个元素进行比较即可。

扩展- 循环队列

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

基本练习

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

推荐阅读:
  1. 关于基础的数据结构的一些练习
  2. 野生前端的数据结构基础练习(5)——散列

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

前端 野生前端 结构基础

上一篇:shell变量的简单说明

下一篇:密码学与身份鉴别技术--PKI原理与实战应用篇<2>

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》