资讯专栏INFORMATION COLUMN

JavaScript数据结构03 - 队列

Jonathan Shieber / 2592人阅读

摘要:但是,还有一种队列叫优先队列,元素的添加和移除是依赖优先级的。分类优先队列分为两类最小优先队列最大优先队列最小优先队列是把优先级的值最小的元素被放置到队列的最前面代表最高的优先级。那么最小优先队列排序应该为,,,。

一、定义

前面我们学习了栈的实现,队列和栈非常类似,但是使用了不同的原则,而非后进先出。

队列是遵循FIFO(First In First Out,先进先出)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。

在计算机科学中,一个最常见的例子就是打印队列。比如说我们要打印五份文档。我们会打开每个文档,然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文档会首先被打印,以此类推,直到打印完所有文档。

二、队列的实现 2.1 普通队列

创建普通队列类:

// Queue类
function Queue () {
  this.items = [];

  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.isEmpty = isEmpty;
  this.size = size;
  this.clear = clear;
  this.print = print;
}

队列里面有一些声明的辅助方法:

enqueue(element):向队列尾部添加新项

dequeue():移除队列的第一项(即排在队列最前面的项),并返回被移除的元素

front():返回队列中第一个元素,队列不做任何变动,和Stack的peek()方法类似

isEmpty():如果队列中不包含任何元素,返回true,否则返回false

size():返回队列包含的元素个数,与数组的length属性类似

print():打印队列中的元素

clear():清空整个队列

下面我们来一一实现这些辅助方法:

// 向队列尾部添加元素
function enqueue (element) {
  this.items.push(element);
}

// 移除队列的第一个元素,并返回被移除的元素
function dequeue () {
  return this.items.shift();
}

// 返回队列的第一个元素
function front () {
  return this.items[0];
}

// 判断是否为空队列
function isEmpty () {
  return this.items.length === 0;
}

// 获取队列的长度
function size () {
  return this.items.length;
}

// 清空队列
function clear () {
  this.items = [];
}

// 打印队列里的元素
function print () {
  console.log(this.items.toString());
}

创建普通队列实例进行测试:

// 创建Queue实例
var queue = new Queue();

console.log(queue.isEmpty());     // true
queue.enqueue("John");            // undefined
queue.enqueue("Jack");            // undefined
queue.enqueue("Camila");          // undefined
queue.print();                    // "John,Jack,Camila"
console.log(queue.size());        // 3
console.log(queue.isEmpty());     // false
queue.dequeue();                  // "John"
queue.dequeue();                  // "Jack"
queue.print();                    // "Camila"
queue.clear();                    // undefined
console.log(queue.size());        // 0
2.2 优先队列 2.2.1 定义

普通队列的添加和移除只依赖于先后顺序,先来的先添加,后来的后添加,然后按照先后顺序依次从队列移除。

但是,还有一种队列叫优先队列,元素的添加和移除是依赖优先级的。

一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。再比如火车,老年人、孕妇和带小孩的乘客是享有优先检票权的。

2.2.2 分类

优先队列分为两类:

最小优先队列

最大优先队列

最小优先队列是把优先级的值最小的元素被放置到队列的最前面(代表最高的优先级)。比如有四个元素:"John", "Jack", "Camila", "Tom",他们的优先级值分别为4,3,2,1。

那么最小优先队列排序应该为:"Tom","Camila","Jack","John"

最大优先队列正好相反,把优先级值最大的元素放置在队列的最前面,以上面的为例,最大优先队列排序应该为:"John", "Jack", "Camila", "Tom"

2.2.2 实现

实现一个优先队列,有两种选项:

设置优先级,根据优先级正确添加元素,然后和普通队列一样正常移除

设置优先级,和普通队列一样正常按顺序添加,然后根据优先级移除

这里最小优先队列和最大优先队列我都采用第一种方式实现,大家可以尝试一下第二种。

所以我只重写enqueue()方法和print()方法,其他方法和上面的普通队列完全相同。完整代码见我的github。

实现最小优先队列

// 定义最小优先队列
function MinPriorityQueue () {
  this.items = [];

  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.isEmpty = isEmpty;
  this.size = size;
  this.clear = clear;
  this.print = print;
}

实现最小优先队列enqueue()方法和print()方法

// 优先队列添加元素,要根据优先级判断在队列中的插入顺序
function enqueue (element, priority) {
  var queueElement = {
    element: element,
    priority: priority
  };

  if (this.isEmpty()) {
    this.items.push(queueElement);
  } else {
    var added = false;

    for (var i = 0; i < this.size(); i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break ;
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }
}

// 打印队列里的元素
function print () {
  var strArr = [];

  strArr = this.items.map(function (item) {
    return `${item.element}->${item.priority}`;
  });

  console.log(strArr.toString());
}

最小优先队列测试:

// 创建最小优先队列minPriorityQueue实例
var minPriorityQueue = new MinPriorityQueue();

console.log(minPriorityQueue.isEmpty());     // true
minPriorityQueue.enqueue("John", 1);         // undefined
minPriorityQueue.enqueue("Jack", 3);         // undefined
minPriorityQueue.enqueue("Camila", 2);       // undefined
minPriorityQueue.enqueue("Tom", 3);          // undefined
minPriorityQueue.print();                    // "John->1,Camila->2,Jack->3,Tom->3"
console.log(minPriorityQueue.size());        // 4
console.log(minPriorityQueue.isEmpty());     // false
minPriorityQueue.dequeue();                  // {element: "John", priority: 1}
minPriorityQueue.dequeue();                  // {element: "Camila", priority: 2}
minPriorityQueue.print();                    // "Jack->3,Tom->3"
minPriorityQueue.clear();                    // undefined
console.log(minPriorityQueue.size());        // 0

实现最大优先队列

最大优先队列只要将优先级的判断改为大于号">"就可以了:

// 最大优先队列MaxPriorityQueue类
function MaxPriorityQueue () {
  this.items = [];

  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.isEmpty = isEmpty;
  this.size = size;
  this.clear = clear;
  this.print = print;
}

// 优先队列添加元素,要根据优先级判断在队列中的插入顺序
function enqueue (element, priority) {
  var queueElement = {
    element: element,
    priority: priority
  };

  if (this.isEmpty()) {
    this.items.push(queueElement);
  } else {
    var added = false;

    for (var i = 0; i < this.items.length; i++) {
      // 注意,只需要将这里改为大于号就可以了
      if (queueElement.priority > this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break ;
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }
}

最大优先队列测试:

// 创建最大优先队列maxPriorityQueue实例
var maxPriorityQueue = new MaxPriorityQueue();

console.log(maxPriorityQueue.isEmpty());     // true
maxPriorityQueue.enqueue("John", 1);         // undefined
maxPriorityQueue.enqueue("Jack", 3);         // undefined
maxPriorityQueue.enqueue("Camila", 2);       // undefined
maxPriorityQueue.enqueue("Tom", 3);          // undefined
maxPriorityQueue.print();                    // "Jack->3,Tom->3,Camila->2,John->1"
console.log(maxPriorityQueue.size());        // 4
console.log(maxPriorityQueue.isEmpty());     // false
maxPriorityQueue.dequeue();                  // {element: "Jack", priority: 3}
maxPriorityQueue.dequeue();                  // {element: "Tom", priority: 3}
maxPriorityQueue.print();                    // "Camila->2,John->1"
maxPriorityQueue.clear();                    // undefined
console.log(maxPriorityQueue.size());        // 0
2.3 循环队列

还有一种队列实现叫做循环队列

循环队列的一个例子就是击鼓传花游戏(Hot Potato)。在这个游戏中,孩子们围城一个圆圈,击鼓的时候把花尽快的传递给旁边的人。某一时刻击鼓停止,这时花在谁的手里,谁就退出圆圈直到游戏结束。重复这个过程,直到只剩一个孩子(胜者)。

下面我们在普通队列的基础上,实现一个模拟的击鼓传花游戏:

// 实现击鼓传花
function hotPotato (nameList, num) {
  var queue = new Queue();

  for (var i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i]);
  }

  var eliminated = "";

  while (queue.size() > 1) {
    // 循环num次,队首出来去到队尾
    for (var i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    // 循环num次过后,移除当前队首的元素
    eliminated = queue.dequeue();
    console.log(`${eliminated}在击鼓传花中被淘汰!`);
  }

  // 最后只剩一个元素
  return queue.dequeue();
}

// 测试
var nameList = ["John", "Jack", "Camila", "Ingrid", "Carl"];
var winner = hotPotato(nameList, 10);
console.log(`最后的胜利者是:${winner}`);

执行结果为:

// John在击鼓传花中被淘汰!
// Ingrid在击鼓传花中被淘汰! 
// Jack在击鼓传花中被淘汰!
// Camila在击鼓传花中被淘汰!
// 最后的胜利者是:Carl
三、结束

本文会同步到我的个人博客,完整代码可以到我的github仓库查看,如果对你有帮助的话欢迎点一个Star~~

欢迎关注我的公众号

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/96294.html

相关文章

  • 分布式代理爬虫:架构篇

    摘要:降低的结果可能有三个随着数据量的增大的性能受到了一定的影响知乎校验器在把中的代理消费完之后,由于是定时任务,所以导致某段时间内新鲜的空缺。 历时大致两个月,到现在终于完成了分布式代理抓取爬虫,目前开源在了Github上。写这个项目的原因主要有两点,一是自己平时的部分工作需要和爬虫打交道,代理IP在有的时候可以发挥非常重要的作用,调研过一些开源的代理IP采集程序,发现在抓取、解析、校验、...

    qujian 评论0 收藏0
  • 100行代码实现任务队列

    摘要:最近刚看完多线程,为了加深印象,按照分钟实现延迟消息功能的思路,实现了一个简易版的异步队列。读取任务时,计算当前和,取出需要执行的任务,使用多线程的形式执行。加锁的主要作用是防止多线程同时操作文件读写,影响数据一致性。 最近刚看完python多线程,为了加深印象,按照1分钟实现延迟消息功能的思路,实现了一个简易版的异步队列。 高效延时消息,包含两个重要的数据结构: 1.环形队列,例...

    xorpay 评论0 收藏0
  • 多线程+代理池爬取天天基金网、股票数据(无需使用爬虫框架)

    摘要:本次使用天天基金网进行爬虫,该网站具有反爬机制,同时数量足够大,多线程效果较为明显。技术路线代理池多线程爬虫与反爬编写思路首先,开始分析天天基金网的一些数据。一旦使用多线程,则需要考虑到数据的读写顺序问题。 @[TOC] 简介 提到爬虫,大部分人都会想到使用Scrapy工具,但是仅仅停留在会使用的阶段。为了增加对爬虫机制的理解,我们可以手动实现多线程的爬虫过程,同时,引入IP代理池进行...

    jaysun 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<