Author | 王平安 |
---|---|
pingan8787@qq.com | |
博 客 | www.pingan8787.com |
微 信 | pingan8787 |
每日文章推荐 | https://github.com/pingan8787/Leo_Reading/issues |
微信公众号 | 前端自习课 |
这是第二周的练习题,这里补充下咯,五一节马上就要到了,自己的计划先安排上了,开发一个有趣的玩意儿。
下面是之前分享的链接:
本周练习内容:数据结构与算法 —— Queue
这些都是数据结构与算法,一部分方法是团队其他成员实现的,一部分我自己做的,有什么其他实现方法或错误,欢迎各位大佬指点,感谢。
一、队列有什么特点,生活中有什么例子?
解题:
1.概念介绍
队列,又称为伫列(queue),是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。 ——《维基百科》
队列特点:先进先出操作。
生活中的案例:常见的排队,在电影院也好,排队结账也是,排在第一位的人会先接受服务。
2.与堆栈区别
队列的操作方式和堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。
二、请实现一个队列,并实现以下方法:
enqueue(element)
:向队列尾部添加一个新的项。dequeue()
:移除队列的第一项,并返回被移除的元素。front()
:返回队列中第一个元素 —— 最先被添加,也将是最先被移除的元素。队列不做任何变动 (不移除元素,只返回元素信息 —— 与Stack
类的peek
方法类似)。tail()
:返回队列中的最后一个元素,队列不做任何变动。isEmpty()
:如果栈没有任何元素就返回true
,否则返回false
。size()
:返回队列包含的的元素个数,与数组的length
属性类似。print()
:打印队列中的元素。
提示:Web 端优先使用 ES6 以上的语法实现。
解题:
1 | /** |
三、使用队列计算斐波那契数列的第 n 项。
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:
1 | 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610... |
在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*),即前两项固定为 1,后面的项为前两项之和,依次向后。在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用。
使用示例如下:
1 | fibonacci(5); --> 5 |
解题:
解题方法1:
1 | /** |
解题方法2:
1 | function fibonacci(n) { |
四、实现优先队列 PriorityQueue。
现实中优先队列的例子很多,比如机场登机的顺序,头等舱和商务舱乘客优先级高于经济舱乘客。又如在银行中办理业务时,VIP 客户的优先级高于普通客户。要实现一个优先队列,有两种方式:
- 设置优先级,然后在正确的位置添加元素。
- 用入列操作添加元素,然后按照优先级移除它们。
本题要求使用第一种方式来实现优先队列,数值越小优先级越高,若优先级相同时,先入队的元素,排在前面。
使用示例如下:
1 | let priorityQueue = new PriorityQueue(); |
解题:
解题方法1:
1 | class PriorityQueue { |
解题方法2:
1 | /** |
五、用队列实现栈。
利用两个队列实现栈,栈的特点是后进先出,可以让元素入队 q1
,留下队尾元素让其他元素出队,暂存到 q2
中,再让 q1
中剩下的元素出队,即最后进的最先出来。
提示:入栈和出栈都在 q1 中完成,q2 只作为临时中转空间。
解题:
1 | /** |
这里也可以直接使用第二题定义的Queue来实现:
1 | class QueueStack { |
下周预告
下周将练习集合(Set) 的题目,五一要到咯,也要好好做自己一个项目了。