您好,登录后才能下订单哦!
这篇文章主要介绍了js中如何实现队列,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
队列(Queue
)是一种遵从先进先出(First in
,first out
。简称FIFO
)原则的有序集合。 它和栈的不同点是栈是先进后出的,队列是先进先出的,栈都是在一端进与出,而队列是在一端进在另一端出。栈的删除操作在表尾进行,队列的删除操作在表头进行。顺序栈能够实现多栈空间共享,而顺序队列不能。 共同点是只允许在端点处插入和删除元素。多链栈和多链队列的管理模式可以相同。
JavaScript
是单线程语言,主线程执行同步代码。 函数调用时, 便会在内存形成了一个“调用记录”,又称“调用帧”,保存调用位置和内部变量等信息。如果函数内部还调用了其他函数,那么在调用记录上方又会形成一个调用记录, 所有的调用记录就形成一个“调用栈”。(尾调用、尾递归优化)
对象被分配在一个堆中,一个用以表示一个内存中大的未被组织的区域。
JS
是单线程, 主线程执行同步代码, 事件、I/O 操作等异步任务,将会进入任务队列执行,异步执行有结果之后,就会变为等待状态, 形成一个先进先出的执行栈,主线程的同步代码执行完之后,再从”任务队列”中读取事件, 执行事件异步任务的回调。 这就是为什么执行顺序是, 同步 > 异步 > 回调 更简单的说:只要主线程空了(同步),就会去读取”任务队列”(异步),这就是JavaScript
的运行机制。
本文将实现 基本队列、优先队列和循环队列
消息队列与事件循环Event Loop
一个JavaScript
运行时包含了一个待处理的消息队列(异步任务),(内部是不进入主线程,而进入”任务队列”(task queue
)的任务。比如UI
事件、ajax
网络请求、定时器setTimeout
和setInterval
等。 每一个消息都与一个函数(回调函数callback
)相关联。当栈为空时,从队列中取出一个消息进行处理。这个处理过程包含了调用与这个消息相关联的函数(以及因而创建了一个初始堆栈帧)。当栈再次为空的时候,也就意味着消息处理结束。
这个过程是循环不断的,所以整个的这种运行机制又称为Event Loop(事件循环)。
基本队列
基本队列的方法中,包含了一下6个方法
① 向队列(尾部)中添加元素(enqueue)
②(从队列头部)删除元素(dequeue)
③ 查看队列头部的元素(front)
④ 查看队列是否为空(isEmpty)
⑤ 查看队列的长度(size)
⑥ 查看队列(print)
function Queue() { //初始化队列(使用数组实现) var items = []; //入队 this.enqueue = function (ele) { items.push(ele); }; //出队 this.dequeue = function () { return items.shift(); }; //返回首元素 this.front = function () { return items[0]; }; //队列是否为空 this.isEmpty = function () { return items.length == 0; }; //清空队列 this.clear = function () { items = []; }; //返回队列长度 this.size = function () { return items.length; }; //查看列队 this.show = function () { return items; }; } var queue = new Queue(); queue.enqueue("hello"); queue.enqueue("world"); queue.enqueue("css"); queue.enqueue("javascript"); queue.enqueue("node.js"); console.log(queue.isEmpty()); // false console.log(queue.show()); //hello,world,css3,javascript,node.js console.log(queue.size()); //5 console.log(queue.front()); //hello console.log(queue.dequeue()); //hello console.log(queue.show()); //'world', 'css', 'javascript', 'node.js' console.log(queue.clear()); console.log(queue.size()); //0
优先队列的实现
在优先队列中,元素的添加或者删除是基于优先级的。实现优先队列有两种方式:① 优先添加,正常出列;② 正常添加,优先出列
优先添加,正常出列的(最小优先队列)例子(这个例子在实现队列的基础上,把添加进队列的元素从普通数据改为对象(数组)类型,该对象包含需要添加进队列的元素的值和优先级):
function PriorityQueue() { //初始化队列(使用数组实现) var items = [] //因为存在优先级,所以插入的列队应该有一个优先级属性 function queueEle(ele, priority) { this.ele = ele this.priority = priority } //入队 this.enqueue = function (ele, priority) { let element = new queueEle(ele, priority) //为空直接入队 if (this.isEmpty()) { items.push(element) } else { var qeueued = false; //是否满足优先级要求,并且已经入队 for (let i = 0; i < this.size(); i++) { if (element.priority < items[i].priority) { items.splice(i, 0, element) qeueued = true break; } } //如果不满足要求,没有按要求入队,那么就直接从尾部入队 if (!qeueued) items.push(element) } } //出队 this.dequeue = function () { return items.shift() } //返回首元素 this.front = function () { return items[0] } //队列是否为空 this.isEmpty = function () { return items.length == 0 } //清空队列 this.clear = function () { items = [] } //返回队列长度 this.size = function () { return items.length } //查看列队 this.show = function () { return items } } var priorityQueue = new PriorityQueue(); priorityQueue.enqueue('优先级2-1', 2); priorityQueue.enqueue('优先级1-1', 1); priorityQueue.enqueue('优先级1-2', 1); priorityQueue.enqueue('优先级3-1', 3); priorityQueue.enqueue('优先级2-2', 2); priorityQueue.enqueue('优先级1-3', 1); priorityQueue.show(); // 按优先级顺序输出 //输出 [ 0:queueEle {ele: "优先级1-1", priority: 1}, 1:queueEle {ele: "优先级1-2", priority: 1}, 2:queueEle {ele: "优先级1-3", priority: 1}, 3:queueEle {ele: "优先级2-1", priority: 2}, 4:queueEle {ele: "优先级2-2", priority: 2}, 5:queueEle {ele: "优先级3-1", priority: 3} ]
循环队列
可以使用循环队列来模拟击鼓传花的游戏(约瑟夫环问题):一群孩子围成一圈,每次传递 n 个数,停下来时手里拿花的孩子被淘汰,直到队伍中只剩下一个孩子,即胜利者。
循环队列,每次循环的时候(从队列头部)弹出一个孩子,再把这个孩子加入到队列的尾部,循环 n 次,循环停止时弹出队列头部的孩子(被淘汰),直到队列中只剩下一个孩子。
function Queue() { //初始化队列(使用数组实现) var items = []; //入队 this.enqueue = function (ele) { items.push(ele); }; //出队 this.dequeue = function () { return items.shift(); }; //返回首元素 this.front = function () { return items[0]; }; //队列是否为空 this.isEmpty = function () { return items.length == 0; }; //清空队列 this.clear = function () { items = []; }; //返回队列长度 this.size = function () { return items.length; }; //查看列队 this.show = function () { return items; }; } /** * * @param {名单} names * @param {指定传递次数} num */ function onlyOne(names, num) { var queue = new Queue(); //所有名单入队 names.forEach((name) => { queue.enqueue(name); }); //淘汰的人名 var loser = ""; //只要还有一个以上的人在,就一直持续 while (queue.size() > 1) { for (let i = 0; i < num; i++) { //把每次出队的人,再次入队 ,这样一共循环了num 次(击鼓传花一共传了num次) queue.enqueue(queue.dequeue()); } //到这就次数就用完了,下一个就要出队了 loser = queue.dequeue(); console.log(loser + "被淘汰了"); } //到这就剩下一个人了 return queue.dequeue(); } var names = ["文科", "张凡", "覃军", "邱秋", "黄景"]; var winner = onlyOne(names, 99); console.log("金马奖影帝最终获得者是:" + winner);
感谢你能够认真阅读完这篇文章,希望小编分享的“js中如何实现队列”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。