队列是是一种受限的线性表，特点为先进先出（FIFO：first in first out）。
受限之处在于它只允许在表的前端（front）进行删除操作；在表的后端（rear）进行插入操作；
相当于排队买票，先来的先买票，后来的后买票。
队列的应用：
打印队列：计算机打印多个文件的时候，需要排队打印；线程队列：当开启多线程时，当新开启的线程所需的资源不足时就先放入线程队列，等待CPU处理；
队列类的实现：
队列的实现和栈一样，有两种方案：
基于数组实现；基于链表实现；
队列的常见操作：
enqueue（element）：向队列尾部添加一个（或多个）新的项；
dequeue（）：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素；
front（）：返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与Stack类的peek方法非常类似）；
isEmpty（）：如果队列中不包含任何元素，返回true，否则返回false；
size（）：返回队列包含的元素个数，与数组的length属性类似；
toString（）：将队列中的内容，转成字符串形式；
二、封装队列类
2.1.代码实现
// 基于数组封装队列类 function Queue() { // 属性 this.items = [] // 方法 // 1.enqueue():将元素加入到队列中 Queue.prototype.enqueue = element => { this.items.push(element) } // 2.dequeue():从队列中删除前端元素 Queue.prototype.dequeue = () => { return this.items.shift() } // 3.front():查看前端的元素 Queue.prototype.front = () => { return this.items[0] } // 4.isEmpty:查看队列是否为空 Queue.prototype.isEmpty = () => { return this.items.length == 0; } // 5.size():查看队列中元素的个数 Queue.prototype.size = () => { return this.items.length } // 6.toString():将队列中元素以字符串形式输出 Queue.prototype.toString = () => { let resultString = '' for (let i of this.items){ resultString += i + ' ' } return resultString } }
测试代码：
// 创建队列 let queue = new Queue() // 将元素加入到队列中 queue.enqueue('a') queue.enqueue('b') queue.enqueue('c') queue.enqueue('d') console.log(queue); //58 // 从队列中删除元素 queue.dequeue() console.log(queue); //62 queue.dequeue() console.log(queue); //64 //front console.log(queue.front()); //67 // 验证其他方法 console.log(queue.isEmpty()); //70 console.log(queue.size()); //71 console.log(queue.toString()); //72
测试结果：
2.2.队列的应用
使用队列实现小游戏：击鼓传花，传入一组数据和设定的数字num，循环遍历数组内元素，遍历到的元素为指定数字num时将该元素删除，直至数组剩下一个元素。
代码实现：
// 队列应用：面试题：击鼓传花 let passGame = (nameList, num) => { //1.创建队列结构 let queue = new Queue() //2.将所有人依次加入队列 // 这是ES6的for循环写法，i相当于nameList[i] for(let i of nameList){ queue.enqueue(i) } // 3.开始数数 while(queue.size() > 1){//队列中只剩1个人就停止数数 // 不是num的时候，重新加入队列末尾 // 是num的时候，将其从队列中删除 // 3.1.num数字之前的人重新放入队列的末尾(把队列前面删除的加到队列最后) for(let i = 0; i< num-1; i++ ){ queue.enqueue(queue.dequeue()) } // 3.2.num对应这个人，直接从队列中删除 /* 思路是这样的，由于队列没有像数组一样的下标值不能直接取到某一元素，所以采用，把num前面的num-1个元素先删除后添加到队列末尾，这样第num个元素就排到了队列的最前面，可以直接使用dequeue方法进行删除 */ queue.dequeue() } //4.获取剩下的那个人 console.log(queue.size()); //104 let endName = queue.front() console.log('最终剩下的人：' + endName); //106 return nameList.indexOf(endName); } //5.测试击鼓传花 let names = ['lily', 'lucy', 'Tom', 'Lilei', 'Tony'] console.log(passGame(names, 3)); //113
测试结果：
三、优先队列
优先级队列主要考虑的问题为：
每个元素不再只是一个数据，还包含数据的优先级；在添加数据过程中，根据优先级放入到正确位置；3.1.优先级队列的实现
代码实现：