《javascript数据结构和算法》读书笔记（2）：队列
第二讲 队列
队列和栈非常相似。但是使用的是FIFO（First In First Out，先进先出）原则。在尾部添加元素，在顶部移除元素。
计算机科学中，最常见的就是打印机的打印队列。
创建一个队列
原生队列
'现在用js创建一个队列吧。要求实现以下方法：
- enqueue：进队，向队列尾部添加一个选项。
- dequeue：出队，移除队列头部的选项。并返回被移除的元素
- front：返回队列第一个元素
- bottom：返回队列最后一个元素
- isEmpty：若队列为空，返回true否则返回false
- size：返回队列的元素个数。
实现队列的封装过程也是相当简单：
class Queue {
constructor(arr = []) {
this.arr = arr;
}
// 从尾部进队
enqueue(item) {
this.arr.push(item)
}
// 从头部出队，返回第一个元素
dequeue() {
return this.arr.shift()
}
// 返回第一个元素
front() {
return this.arr[0]
}
// 返回队列尾部的元素
bottom(){
return this.arr[this.arr.length-1]
}
// 是否为空
isEmpty() {
return this.arr.length == 0;
}
// 返回元素个数
size() {
return this.arr.length
}
// 打印队列
print() {
console.log(this.arr)
}
}优先队列
在优先队列中，元素添加和移除是基于优先级的。比如说登机时：头等舱的乘客优先级要更高。又比如说，医院里急诊要优先于门诊。
实现优先队列 PriorityQueue的原则：
- 设置优先级，然后在正确的位置添加元素
- 移除时，也根据优先级，但正常来说肯定是优先度最小的在最底层。
// 优先队列
class PriorityQueue{
constructor(){
this.arr=[];
// 创建一个特殊队列,用来储存元素（包括优先级）
this.QueueElement=function(item, priority){
this.item=item;
this.priority=priority;
}
}
// 移入元素，接收元素和优先级
enqueue(item, priority){
let QueueElement=this.QueueElement;
let queueElement=new QueueElement(item, priority)
let isAdded=false;
for(let i=0;i<this.arr.length;i++){
// 若有较高优先级，插入进去。
if(queueElement.priority<this.arr[i].priority){
this.arr.splice(i,0,queueElement);
isAdded=true;
break;
}
}
// 如果优先级最小，push上去吧
if(!isAdded){
this.arr.push(queueElement)
}
}
// 出队，按正常出队即可
dequeue(item,priority){
return this.arr.shift()
}
// 是否空
isEmpty(){
return this.arr.length==0;
}
// 打印
print(){
for(let i=0;i<this.arr.length;i++){
console.log(`${this.arr[i].item}-${this.arr[i].priority}`)
}
}
}
//测试用例
var aaa=new PriorityQueue();
aaa.enqueue('djtao',2)
aaa.enqueue('dangjingtao',1)
aaa.enqueue('djt',1)
aaa.print();和原生队列相比，优先队列在实现上的区别在于：
- 添加元素时，需要创建一个新类，用以储存值。
- 最大的先进先出，这个实现成为
最小优先队列
队列的应用
击鼓传花：循环队列
击鼓传花游戏（Hot Protato）是一个典型的循环队列：一群人绕圈排排坐。花尽快传给下一个人，如此往复。当某时刻停止，花在手上的人就出列。到最后还留在圈子里的人，就是胜者。
// 击鼓传花
const hotProtato = (nameList, num) => {
const queue = new Queue();
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i]);
}
let eliminated = '';
while (queue.size() > 1) {
for (let i = 0; i < num; i++) {
// 典型的蛇咬自己尾巴
queue.enqueue(queue.dequeue())
}
// 每次减1
eliminated = queue.dequeue()
console.log(eliminated + `在击鼓传花中被淘汰`);
}
return queue.dequeue();
}
//测试用例
let names = ['djtao', 'dangjingtao', 'djt', 'dangjt', 'taotao'];
let winner = hotProtato(names, 9);
console.log(`胜者是${winner}`)
约瑟夫环
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 [1] 结果+1即为原问题的解。
现有一个数组 a=newArray(100)，存放了0-99的所有数，要求每隔两个数删掉一个数，到末尾时从头继续。求最后一个被删掉的数。
分析：
- 解环：这个环中，无论循环到第几次，每个元素拥有一个唯一的索引值，每个两个数删掉一个，认为是2,5,8..，对应的index值是3,6,9......每次遍历也就是索引值index模3为0的队列元素。
- 其实就是在循环队列的基础上做出条件判断，核心在于计数。index在每次循环中都加1.
// 约瑟夫环
const cycle = () => {
// 创建队列
const queue = new Queue();
for (let i = 0; i < 100; i++) {
queue.enqueue(i);
}
let index = 0;
while (queue.size() > 1) {
let dequeue = queue.dequeue()
index += 1;
if (index % 3 != 0) {
queue.enqueue(dequeue)
}
}
return queue.dequeue();
}
let a = cycle()
console.log(a)答案为90。
斐波拉契列
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子队列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
问题背景：斐波拉契计算用递归做相当无脑：
// F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
const fib=(n)=>{
if(n==1||n==2){
return 1;
}
return fib(n-2)+fib(n-1);
}
//测试用例
for(let i=1;i<11;i++){
console.log(fib(i))
}// 1,1,2,3,5,8,13,21,34,55
console.log(fib(20)/fib(21))//约0.618却也是及其耗内存。比如说以下测试用例就通过不了：
console.log(fib(100)/fib(101))//计算量太大算不出来了！需求：不使用递归，而使用队列的方法求斐波拉契数列的第N项。
思考：其实用栈来做是可以的。但是这里用队列更省内存。我们能获取的的就是队列的底部和队列的头部。那么可以这样构造：
- 在n为1和2时。需人为设定了n=1和n=2时，返回1。
-
n>2时，初始既有队列为
[1,1]。每次计算时只考虑头部和底部，也就是说队列保留2个元素即可！ - 循环次数：循环。因此只考虑n-2次循环即可。
const fib=(n)=>{
if(n==1||n==2){
return 1
}
const queue=new Queue([1,1]);
for(let i=0;i<n-2;i++){
// 从头部获取较小的a
let a=queue.front();
// 从尾部获取较大的b，它将作为下次循环的头部
let b=queue.bottom();
// 弹出a
queue.dequeue();
// 加入a+b
queue.enqueue(a+b);
}
return queue.bottom()
}
// 测试用例
for(let i=1;i<11;i++){
console.log(fib(i))
}// 1,1,2,3,5,8,13,21,34,55
console.log(fib(100)/fib(101))//0.6180339887498949用两个队列实现一个栈（包括push，pop，和top）
如题。二者的数据管理模式是相反的。
- push ，队列1（queue）执行enqueue。
- pop，事实上是从队列尾部删除元素。
- top：取队列1的尾部即可
class Stack{
constructor(arr=[]){
this.queue=new Queue(arr);
}
push(item){
this.queue.enqueue(item);
// if(this._queue.isEmpty){
// this._queue.enqueue(item);
// }
}
// 从头部删除
pop(){
const _queue=new Queue();
for(let i=0;i<this.queue.size();i++){
let item=this.queue.dequeue();
_queue.enqueue(item);
}
let result=this.queue.dequeue();
this.queue=_queue;
return result
}
// 取栈顶，实际上取的是队列的bottom
top(){
return this.queue.bottom()
}
}
//测试用例
var a=new Stack();
a.push(1);
a.push(2);
a.push(3);
console.log(a.pop())//3
a.push(4)
console.log(a.pop())//4
console.log(a.top())//2那么栈的基本方法都实现了。
打印杨辉三角
通过console打印如图的三角排列。
- 每一层的项数都+1
- 每层除了两边的1以外，都是上边两个数之和。
const yangHui = (n) => {
let queue = new Queue([1, 1]);
// 打印第n行数据
const print = (_n) => {
const _queue = new Queue();
for (let i = 0; i < _n; i++) {
// 判断边界
if (i == 0 || i == _n - 1) {
_queue.enqueue(1);
} else {
let a = queue.dequeue();
let b = queue.front();
_queue.enqueue(a + b);
}
}
//存放新的队列
queue = _queue;
queue.print()
}
// 调用
for (let i = 1; i < n + 1; i++) {
print(i);
}
}
yangHui(10)
方法也是比较简单。注意判断边界为1的情况。
JavaScript的任务队列
当打开浏览器新的标签页,就会创建一个新的任务队列。每个标签都是单线程处理任务，这被称为事件循环。
逐层打印一棵树的节点，socket的实现。用的也是队列。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录