阅读 1555

数据结构 - 队列

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 初阶:模拟实现队列
四 初阶:优先队列
五 初阶击鼓传花
六 进阶:浏览器 Event Loop 机制
七 总结

二 前言

返回目录

队列,和栈有点类似,但是又不太一样,队列遵循 先进先出 的原则。

假如将前面学过的栈用堆叠的书来比喻,需要一本一本拿,才能拿到最底部的书来说的话。

那么队列就是排队,假如你去银行排队,那么,在前面的人先享受服务,完后前面的人先走。

形象点:

入栈:(底部)A<-B<-C<-D(顶部)
出栈:(底部)A->B->C->D(顶部)

出队列(头部)A<-B<-C<-D 入队列(尾部)
复制代码

三 模拟实现队列

返回目录

在了解了队列后,我们模拟实现一个队列,加深我们对队列的印象。

首先,为队列声明一些方法:

  • enqueue(element):向队列尾部添加一个或者多个新的项。
  • dequeue():移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。
  • front():返回队列中第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何改动。
  • isEmpty():如果队列中不包含任何元素,返回 true,否则返回 false
  • size():返回队列中的元素个数,和数组的 length 属性类似。

然后,我们尝试实现这些方法:

实现代码:

function Queue() {
  const items = [];
  // 1. 元素入队列
  this.enqueue = function(element) {
    items.push(element);
  };
  // 2. 元素出队列
  this.dequeue = function() {
    return items.shift();
  };
  // 3. 查看队列顶部元素
  this.front = function() {
    return items[0];
  };
  // 4. 判断队列是否为空
  this.isEmpty = function() {
    return items.length === 0;
  };
  // 5. 查看整个队列长度
  this.size = function() {
    return items.length;
  };
  // 6. 查看整个队列
  this.print = function() {
    console.log(items);
  }
};

let queue = new Queue();
queue.enqueue('1'); // [ '1' ]
queue.enqueue('2'); // [ '1', '2' ]
queue.dequeue(); // [ '2' ]
queue.dequeue(); // [ ]
queue.print(); // []
复制代码

最后,如果纯粹看 jsliang 写的,没图没视频,小伙伴们很容易懵逼,这里 jsliang 建议看各个大佬的文章或者通过下面章节的几个案例进一步了解:

四 优先队列

返回目录

说到队列,小伙伴们应该对一个词非常有印象:

  • 插队

这时候进行词语联想,就有了 黄牛党强行插队 等一系列 “恶” 词。

但是,有时候 插队 却是非常有必要的,例如:

  1. 急诊科候诊室。先处理较急的病情,再处理次要点的。
  2. 登机顺序。头等舱和商务舱优于经济舱,有些国家老人和孕妇(或者带小孩的母亲)优于其他人。

那么,优先队列 如何实现呢?

function PriorityQueue() {
  // 1. 定义空数组
  const items = [];
  // 2. 定义队列
  function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority;
  }
  // 3. 实现入队列方式
  this.enqueue = function(element, priority) {
    let queueElement = new QueueElement(element, priority);
    let added = false;
    for (let i = 0; i < items.length; i++) {
      // 如果可以插队,那么就插入到队列,且终止本次循环(减少时间浪费以及重复添加)
      if (queueElement.priority < items[i].priority) {
        items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }
    if (!added) {
      items.push(queueElement);
    }
  };
  // 4. 实现队列打印
  this.print = function() {
    items.forEach((ele) => {
      console.log(`${ele.element} ${ele.priority}`);
    })
  };
  // 5. 其他方法和默认的Queue实现相同
}

const priorityQueue = new PriorityQueue();
priorityQueue.enqueue('jsliang', 1);
priorityQueue.enqueue('JavaScriptLiang', 2);
priorityQueue.enqueue('梁峻荣', 1)
priorityQueue.print();
// jsliang 1
// 梁峻荣 1
// JavaScriptLiang 2
复制代码

看完上面代码,可以感受到 优先队列 给人的感觉是高大上的,它可以帮助我们进行 “更为合理” 地排序,就好比假如你需要写个程序,给急诊用户排队,那么我们就可以利用 优先队列 的特点,让患者得到最快最准时的治疗。

当然,更多的后续我们在算法中进行讲解。

五 击鼓传花

返回目录

击鼓传花是一个游戏。

在这个游戏中,孩子们围成一圈。

给某个孩子一朵花,然后他要尽快把这花传递给下一个孩子(顺序传递)。

某一时刻传花停止,手里拿着花的孩子就被淘汰。

重复这个过程,直到剩下一个孩子。

实现方式如下:

/**
 * @name 队列模拟
 */
function Queue() {
  const items = [];
  // 1. 元素入队列
  this.enqueue = function(element) {
    items.push(element);
  };
  // 2. 元素出队列
  this.dequeue = function() {
    return items.shift();
  };
  // 3. 查看队列顶部元素
  this.front = function() {
    return items[0];
  };
  // 4. 判断队列是否为空
  this.isEmpty = function() {
    return items.length === 0;
  };
  // 5. 查看整个队列长度
  this.size = function() {
    return items.length;
  };
  // 6. 查看整个队列
  this.print = function() {
    console.log(items);
  }
};

/**
 * @name 击鼓传花
 * @param {*} nameList 人名
 * @param {*} num 淘汰的位置
 */
function hotPotato(nameList, num) {
  let 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());
    }
    eliminated = queue.dequeue();
    console.log('淘汰了:' + eliminated);
  }
  return queue.dequeue();
}

const names = ['name1', 'name2', 'name3', 'name4', 'name5'];
const winner = hotPotato(names, 7);
console.log('赢家是:' + winner);
// 淘汰了:name3
// 淘汰了:name2
// 淘汰了:name5
// 淘汰了:name4
// 赢家是:name1
复制代码

在这次游戏中,淘汰顺序是:

  1. name3
  2. name2
  3. name5
  4. name4

最后剩下 name1,退出循环,我们将其推出栈(此时栈为空)。

当然,这里我们固定了传递进来的数字为 7,如果我们通过随机来指定一个,那么应该会更加有趣点:

随机式击鼓传花

// ...主体代码如上

const names = ['name1', 'name2', 'name3', 'name4', 'name5'];
const winner = hotPotato(names, Math.floor(Math.random() * 10 + 1));
console.log('赢家是:' + winner);
// 淘汰了:name1
// 淘汰了:name4
// 淘汰了:name2
// 淘汰了:name3
// 赢家是:name5
复制代码

现在淘汰的位置不固定了,是不是觉得比起原版的有点味道了~

六 进阶:浏览器 Event Loop

返回目录

说到队列,如果单纯讲基础点,相信很多小伙伴都不会买单,所以咱们可以进一步探索:

  • 浏览器 Event Loop 机制

注:这也是面试常备的一道题

首先,为什么需要 Event Loop?

因为 JavaScript 是单线程的。

单线程意味着,所有任务都需要排队,前一个任务结束,才会执行后一个任务。

如果前一个任务耗时很长,那么后一个任务就不得不一直等着。

为了协调事件(event),用户交互(user interaction),脚本(script),渲染(rendering),网络(networking)等,用户代理(user agent)必须使用事件循环(event loops)。

然后,了解完 Event Loop 的基础内容,咱们通过文章进一步探索 Event Loop。

为此 jsliang 特地翻阅了十几篇文章,从 Event Loop 的机制讲起,通过尝试描述浏览器的 Event Loop,再进一步讲解 Node.js 的 Event Loop,来帮助自己和小伙伴们深入探索,仔细了解这一块内容:

最后,看到这里,相信小伙伴们对此有个简单了解,对队列这个词也有了进一步的深入了解。

参考文献:

  1. 《Tasks, microtasks, queues and schedules》 - Jake
  2. 《彻底搞懂浏览器 Event-loop》 - 刘小夕
  3. 《彻底理解 JS Event Loop(浏览器环境)》 - 93
  4. 《彻底弄懂浏览器端的 Event-Loop》 - 长可
  5. 《什么是浏览器的事件循环(Event Loop)?》 - 鱼子酱
  6. 《理解event loop(浏览器环境与nodejs环境)》 - sugerpocket
  7. 《从 event loop 规范探究 JavaScript 异步及浏览器更新渲染时机》 - 杨敬卓
  8. 《跟着 Event loop 规范理解浏览器中的异步机制》 - fi3ework
  9. 《不要混淆 nodejs 和浏览器中的 event loop》 - youth7
  10. 《浏览器的 event loop 和 node 的 event loop》 - 金大光
  11. 《浏览器与 Node 的事件循环(Event Loop)有何区别?》 - 浪里行舟
  12. 《浏览器和 Node 不同的事件循环(Event Loop)》 - toBeTheLight
  13. 《let 和 const 命令》 - 阮一峰
  14. 《Node.js Event Loop》 - Node.js 官网

七 总结

返回目录

这样,我们就 暂时 完成了队列的基础了解学习,因为你站在甲板上,你是看不到整艘邮轮是怎么运行的,所以咱们会慢慢探索,通过各种 LeetCode 题专门训练,逐步丰富我们的视野。

在探索这些内容的过程中,jsliang 也对某些内容感到困惑,基本上,碰到一些新内容,会先抄一遍(照着敲一份),细细理解它的意思,然后根据自身理解,想想有没有其他实现方式(例如通过定时器来实现击鼓传花)。

个人觉得,人的一生都在学习,关键是你能不能持续探索下去,以及你的探索方式对你的启发。

仅此而已。


不折腾的前端,和咸鱼有什么区别!

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

浪子神剑 会每天更新面试题,以面试题为驱动来带动大家学习,坚持每天学习与思考,每天进步一点!

扫描上方二维码,关注 jsliang 的公众号(左)和 浪子神剑 的公众号(右),让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于github.com/LiangJunron…上的作品创作。
本许可协议授权之外的使用权限可以从 creativecommons.org/licenses/by… 处获得。