这是第二周的练习题，这里补充下咯，五一节马上就要到了，自己的计划先安排上了，开发一个有趣的玩意儿。
下面是之前分享的链接：
欢迎关注我
- 个人主页(https://github.com/pingan8787)
- 个人博客(http://www.pingan8787.com/)
- 个人知识库(http://js.pingan8787.com/)
- 微信公众号“前端自习课”
本周练习内容：数据结构与算法 —— 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. /**
2. * 2. 实现一个队列
3. */
4. class Queue {
5. constructor (){
6. this.items = []
7. }
8. // enqueue(element)：向队列尾部添加一个新的项。
9. enqueue( element ){
10. this.items.push(element)
11. }
12. // dequeue()：移除队列的第一项，并返回被移除的元素。
13. dequeue (){
14. return this.items.shift()
15. }
16. // front()：返回队列中第一个元素 —— 最先被添加，也将是最先被移除的元素。队列不做任何变动 (不移除元素，只返回元素信息 —— 与 Stack 类的 peek 方法类似)。
17. front (){
18. return this.items[0]
19. }
20. // tail()：返回队列中的最后一个元素，队列不做任何变动。
21. tail (){
22. return this.items[this.items.length-1]
23. }
24. // isEmpty()：如果栈没有任何元素就返回 true，否则返回 false。
25. isEmpty (){
26. return this.items.length === 0
27. }
28. // size()：返回队列包含的的元素个数，与数组的 length 属性类似。
29. size (){
30. return this.items.length
31. }
32. // print()：打印队列中的元素。
33. print (){
34. console.log(this.items.toString())
35. }
36. }
三、使用队列计算斐波那契数列的第 n 项。
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：
-
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
2. fibonacci(9); --> 34
3. fibonacci(14); --> 377
解题：
解题方法1：
1. /**
2. * 3. 使用队列计算斐波那契数列的第 n 项。
3. * 前两项固定为 1，后面的项为前两项之和，依次向后。
4. * @param {Number} num
5. */
6.
7. function fibonacci (num){
8. if(isNaN(num) || num < 0 || num === 0) return 0
9. // // 1. 直接
10. // let n1 = 1, n2 = 1, sum
11. // for(let i = 3; i <= num; i++){
12. // sum = n1 + n2
13. // n1 = n2
14. // n2 = sum
15. // }
16. // // 2. 队列 考虑小于等于2
17. // let arr = [], sum
18. // num === 1 && (arr = [1])
19. // num >= 2 && (arr = [1, 1])
20. // for(let i = 3; i <= num; i ++){
21. // sum = arr[i-2] + arr[i-3]
22. // arr.push(sum)
23. // }
24. // // 3.队列 进出队列
25. let queue = [], sum;
26. for(let i = 1; i <= num; i ++){
27. if(i <=2 ){
28. queue.push(1)
29. }else{
30. sum = queue[0] + queue[1]
31. queue.push(sum)
32. queue.shift()
33. }
34. }
35. return sum
36. }
解题方法2：
1. function fibonacci(n) {
2. const queue = new Queue();
3. queue.enqueue(1);
4. queue.enqueue(1);
5.
6. let index = 0;
7. while(index < n - 2) {
8. index += 1;
9. // 出队列一个元素
10. const delItem = queue.dequeue();
11. // 获取头部值
12. const headItem = queue.front();
13. const nextItem = delItem + headItem;
14. queue.enqueue(nextItem);
15. }
16. return queue.tail();
17. }
18. console.log(fibonacci(9)); // 34四、实现优先队列 PriorityQueue。
现实中优先队列的例子很多，比如机场登机的顺序，头等舱和商务舱乘客优先级高于经济舱乘客。又如在银行中办理业务时，VIP 客户的优先级高于普通客户。要实现一个优先队列，有两种方式：
- 设置优先级，然后在正确的位置添加元素。
- 用入列操作添加元素，然后按照优先级移除它们。
本题要求使用第一种方式来实现优先队列，数值越小优先级越高，若优先级相同时，先入队的元素，排在前面。
使用示例如下：
1. let priorityQueue = new PriorityQueue();
2. priorityQueue.enqueue("leo", 2);
3. priorityQueue.enqueue("pingan", 1);
4. priorityQueue.enqueue("robin", 1);
5. priorityQueue.print();
6. // pingan - 1
7. // robin - 1
8. // leo - 2
解题：
解题方法1：
1. class PriorityQueue {
2. constructor() {
3. this._items = [];
4. }
5.
6. enqueue(element, priority) {
7. let queueElement = {
8. element
9. priority
10. };
11.
12. if (this.isEmpty()) {
13. this._items.push(queueElement);
14. } else {
15. let added = false;
16. for (var i = 0; i < this.size(); i++) {
17. if (queueElement.priority < this._items[i].priority) {
18. this.items.splice(i, 0, queueElement);
19. added = true;
20. break ;
21. }
22. }
23.
24. if (!added) {
25. this._items.push(queueElement);
26. }
27. }
28. }
29.
30. print() {
31. var strArr = [];
32. strArr = this._items.map(function (item) {
33. return `${item.element}->${item.priority}`;
34. });
35.
36. console.log(strArr.toString());
37. }
38. }解题方法2：
1. /**
2. * 4. 实现优先队列
3. */
4.
5. class PriorityQueue {
6. constructor (){
7. this.items = []
8. }
9. enqueue (element, priority){
10. let ele = {element, priority}
11. let isAdded = false
12. for(let i = 0; i < this.items.length; i++){
13. if(ele.priority < this.items[i].priority){
14. this.items.splice(i, 0, ele)
15. isAdded = true
16. break
17. }
18. }
19. !isAdded && this.items.push(ele)
20. }
21. print (){
22. for(let i = 0; i < this.items.length; i++){
23. let {element, priority} = this.items[i]
24. console.log(`${element} - ${priority}`)
25. }
26. }
27. }
28. let leo = new PriorityQueue()
29. leo.enqueue("leo", 2);
30. leo.enqueue("leo1", 1);
31. leo.enqueue("leo2", 1);
32. console.log(leo)
五、用队列实现栈。
利用两个队列实现栈，栈的特点是后进先出，可以让元素入队 q1，留下队尾元素让其他元素出队，暂存到 q2 中，再让 q1 中剩下的元素出队，即最后进的最先出来。
提示：入栈和出栈都在 q1 中完成，q2 只作为临时中转空间。
解题：
1. /**
2. * 5. 队列实现栈
3. */
4. class Myqueue {
5. constructor (){
6. this.items = []
7. }
8. enqueue (element){
9. this.items.push(element)
10. }
11. dequeue (){
12. return this.items.shift()
13. }
14. }
15. class Mystack {
16. constructor (){
17. this.q1 = new myQueue()
18. this.q2 = new myQueue()
19. }
20. push (element){
21. this.q1.enqueue(element)
22. this.q2.items = []
23. let len = this.q1.items.length
24. while(len > 0){
25. this.q2.enqueue(this.q1.items[len-1])
26. len --
27. }
28. }
29. pop (){
30. let result = this.q2.dequeue()
31. let len = this.q2.items.length
32. this.q1.items = []
33. while(len > 0){
34. this.q1.enqueue(this.q2.items[len-1])
35. len --
36. }
37. return result
38. }
39. print (){
40. console.log(this.q1.items.toString())
41. }
42. }
这里也可以直接使用第二题定义的Queue来实现：
1. class QueueStack {
2. constructor() {
3. this.queue = new Queue();
4. }
5.
6. push(item) {
7. this.queue.enqueue(item);
8. }
9.
10. pop() {
11. // 向队列末尾追加 队列长度-1 次，后弹出队列头部
12. for(let i = 1; i < this.queue.size(); i += 1) {
13. this.queue.enqueue(this.queue.dequeue());
14. }
15. return this.queue.dequeue();
16. }
17.
18. peek() {
19. return this.queue.tail();
20. }
21. }下周预告
下周将练习集合（Set） 的题目，五一要到咯，也要好好做自己一个项目了。
每一个，都是对我最大的肯定！