野生前端的数据结构基础练习(2)——队列
网上的相关教程非常多,基础知识自行搜索即可。
习题主要选自Orelly出版的《数据结构与算法javascript描述》一书。
参考代码可见:https://github.com/dashnowords/blogs/tree/master/Structure/Queue
队列的基本知识
-
特点:
先进先出。
-
用途:
模拟流程或其他带有抽象排队属性的事物或逻辑,例如时间循环队列,发布订阅模式的回调队列等等。
-
基本方法
-
enqueue()
在队尾插入一个元素 -
dequeue()
从队头删除一个元素 -
getHeader()
获取队头的元素 -
getTail()
获取队尾的元素 -
getLength()
获取队列的长度 -
isEmpty()
判断队列是否为空队列
-
-
需要留意的问题
使用
javascript
语言来理解数据结构只能够帮助我们理解结构的基本特性,由于不涉及底层的原理,所以无法深入到算法细节的时间复杂度的话题上,对此感兴趣的同学建议在学习完数据结构入门后再去学习C语言描述版的数据结构资料。
基本练习
-
根据栈的特性实现一个
Queue
类,并在后续题目中需要用队列时使用它。 -
编写一个函数
dancingQueue(str)
,str
中记录着前来参加舞会的人的性别,以空格分割,函数中需要实现将前来跳舞的人按性别分成两队,每当舞池中有空位时,男队和女队的排在最前面的人组成舞伴进入,如果某一队为空时,需要返回对应的消息。 -
实现一个
PriorityQueue
类,实现优先队列的功能,优先队列的元素带有权重,权重越高(一般认为数字越小权重越高)的越早出队。
课后习题(书中第五节习题)
-
修改
Queue
类,生成一个Deque
类,允许从队列两端添加和删除元素,因此也叫双向队列。 -
使用
Deque
类判断一个单词是否是回文。 -
题目3和题目4比较简单,不再赘述。
习题思路
-
javascript中的数组就符合双向队列的特性,试着自己去实现几个特征方法即可。
-
Deque
类可以从队列两端出队,每次从两端各出队一个元素进行比较即可。
扩展- 循环队列
循环队列
书中并没有提及,它是一种特殊的队列。简单理解就是将基本队列只当做存储结构,而使用front
和rear
两个指针分别代表队列的头和尾,实际对外表现的队列是front
和rear
所指向的元素构成的。为了复用存储空间,循环队列
在存储结构的实现上是首位相连的。
-
基本要素
-
front指针
指向队头 -
rear指针
指向队尾 -
size
队列的长度 -
length
存储空间的大小
-
-
基本方法
-
enqueue()
元素入队 -
dequeue()
元素出队 -
isEmpty()
判断队空 -
isFull()
判断队满 -
getSize()
获取队列长度 -
getLength()
获取存储空间长度 -
clear()
清空队列
-
基本练习
实现一个CircularQueue
类,并添加一个扩展方法resize()
,当存储空间已满且有元素入队时,自动将存储空间扩充一倍,当元素出队造成队列长度不足存储空间的1/4时,将存储空间减半以释放空间。
来源:华为云社区 作者:大史不说话
相关文章
- Java基础_死锁、线程组、定时器Timer
- java学习笔记15--多线程编程基础2
- Java实现 基础算法 求100以内的质数
- Java实现基础练习十进制转十六进制
- C/C++基础讲解(四十一)之数值计算与趣味数学篇(复矩阵乘法与求定积分)
- C/C++基础讲解(三十)之数据结构篇(配对新郎和新娘、约瑟夫问题、邮票组合、分糖果)
- 【原创】开源Math.NET基础数学类库使用(01)综合介绍
- JavaSE基础篇 | 对象的创建和使用
- 【Python 八股文】- 消息队列基础
- java===java基础学习(16)---final
- python基础===输入必须为数字的检验的另一种方法
- GIT基础篇,配置账号及命令查看以及帮助命令
- 【RabbitMQ笔记01】Windows搭建RabbitMQ消息队列基础运行环境
- WLAN通信基础——WLAN物理层通信技术
- Linux基础笔记1 | VMware Workstation 的使用
- python-flask框架基础:传入字符、整形、浮点型、文件路径参数以及图片