首页 > > 网页制作 > Javascript >

前端学数据结构之队列

2018-06-24 01:10:55来源：未知阅读 ()

前面的话

　　队列和栈非常类似，但是使用了不同的原则，而非后进先出。本文将详细介绍队列的JS实现

数据结构

　　队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾

　　在现实中，最常见的队列的例子就是排队：

　　还有，在电影院、自助餐厅、杂货店收银台，我们也都会排队。排在第一位的人会先接受服务

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

创建队列

　　我们需要创建自己的类来表示一个队列。先从最基本的声明类开始：

function Queue() {
 //这里是属性和方法
}

　　首先需要一个用于存储队列中元素的数据结构。可以使用数组，就像在上一篇博文Stack类中那样使用（Queue类和Stack类非常类似，只是添加和移除元素的原则不同）：

let items = [];

　　接下来需要声明一些队列可用的方法

enqueue(element(s))：向队列尾部添加一个（或多个）新的项。
dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不 做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）。
isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。
size()：返回队列包含的元素个数，与数组的length属性类似。

【enqueue】

　　首先要实现的是enqueue方法。这个方法负责向队列添加新元素。这里有一个非常重要的细节，新的项只能添加到队列末尾：

　　既然我们使用数组来存储队列的元素，就可以用JS的array类的push方法

this.enqueue = function(element){ 
  items.push(element);
};

【dequeue】

　　接下来要实现dequeue方法。这个方法负责从队列移除项。由于队列遵循先进先出原则，最先添加的项也是最先被移除的。可以用JavaScript的array类的shift方法。shift方法会从数组中移除存储在索引0（第一个位置）的元素

this.dequeue = function(){ 
  return items.shift();
};

　　只有enqueue方法和dequeue方法可以添加和移除元素，这样就确保了Queue类遵循先进先出原则

【front】

　　现在来为我们的类实现一些额外的辅助方法。如果想知道队列最前面的项是什么，可以用front方法。这个方法会返回队列最前面的项（数组的索引为0）：

this.front = function(){ 
  return items[0];
};

【isEmpty】

　　如果队列为空，isEmpty方法返回true，否则返回false

　　对于isEmpty方法，可以简单地验证内部数组的length是否为0。

this.isEmpty = function(){ 
  return items.length == 0;
};

【size】

　　可以为Queue类实现类似于array类的length属性的方法。size方法也跟Stack类里的一样：

this.size = function(){ 
  return items.length;
};

【print】

　　增加一个print方法：

this.print = function(){ 
  console.log(items.toString());
};

　　Queue类的完整代码如下

function Queue() {

    let items = [];

    this.enqueue = function(element){
        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.print = function(){
        console.log(items.toString());
    };
}

使用Queue类

　　首先要做的是实例化我们刚刚创建的Queue类，然后就可以验证它为空（输出为true，因为我们还没有向队列添加任何元素）：

let queue = new Queue(); 
console.log(queue.isEmpty()); //输出true

　　接下来，添加一些元素（可以向队列添加任何类型的元素）：

queue.enqueue("John"); 
queue.enqueue("Jack");

　　添加另一个元素：

queue.enqueue("Camila");

　　再执行一些其他的命令：

queue.print(); 
console.log(queue.size()); //输出3 
console.log(queue.isEmpty()); //输出false
queue.dequeue(); 
queue.dequeue(); 
queue.print();

　　如果打印队列的内容，就会得到John、Jack和Camila这三个元素。因为我们向队列添加了三个元素，所以队列的大小为3（当然也就不为空了）

　　下图展示了目前为止执行的所有入列操作，以及队列当前的状态：

　　然后，出列两个元素（执行两次dequeue方法）。下图展示了dequeue方法的执行过程：

　　最后，再次打印队列内容时，就只剩Camila一个元素了。前两个入列的元素出列了，最后入列的元素也将是最后出列的。也就是说，我们遵循了先进先出原则

ES6

　　我们也可以用ECMAScript 6语法编写Queue类。在这种方法中，我们要用一个WeakMap来保存私有属性items，并用外层函数（闭包）来封装Queue类。

let Queue2 = (function () {

    const items = new WeakMap();

    class Queue2 {

        constructor () {
            items.set(this, []);
        }

        enqueue(element) {
            let q = items.get(this);
            q.push(element);
        }

        dequeue() {
            let q = items.get(this);
            let r = q.shift();
            return r;
        }

        front() {
            let q = items.get(this);
            return q[0];
        }

        isEmpty(){
            return items.get(this).length == 0;
        }

        size(){
            let q = items.get(this);
            return q.length;
        }

        clear(){
            items.set(this, []);
        }

        print(){
            console.log(this.toString());
        }

        toString(){
            return items.get(this).toString();
        }
    }
    return Queue2;
})();

优先队列

　　队列大量应用在计算机科学以及我们的生活中，实现的默认队列也有一些修改版本。其中一个修改版就是优先队列。元素的添加和移除是基于优先级的。一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。在有些国家，老年人和孕妇（或带小孩的妇女）登机时也享有高于其他乘客的优先级

　　另一个现实中的例子是医院的（急诊科）候诊室。医生会优先处理病情比较严重的患者。通常，护士会鉴别分类，根据患者病情的严重程度放号。

　　实现一个优先队列，有两种选项：设置优先级，然后在正确的位置添加元素；或者用入列操作添加元素，然后按照优先级移除它们。在这个示例中，我们将会在正确的位置添加元素，因此可以对它们使用默认的出列操作：

function PriorityQueue() {
 let items = [];
 function QueueElement (element, priority){ // {1}
  this.element = element;
  this.priority = priority;
 }
 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){ // {2}
      items.splice(i,0,queueElement); // {3}
      added = true;
      break; // {4}
    }
  }
  if (!added){
    items.push(queueElement); //{5}
  }
 };
 this.print = function(){
  for (let i=0; i<items.length; i++){
    console.log(`${items[i].element} - ${items[i].priority}`);
  }
 };
 //其他方法和默认的Queue实现相同
}

　　默认的Queue类和PriorityQueue类实现上的区别是，要向PriorityQueue添加元素，需要创建一个特殊的元素（行{1}）。这个元素包含了要添加元素，需要创建一个特殊的元素（行{1}）。这个元素包含了要添加到队列的元素（它可以是任意类型）及其在队列中的优先级

　　如果队列为空，可以直接将元素入列（行{2}）。否则，就需要比较该元素与其他元素的优先级。当找到一个比要添加的元素的priority值更大（优先级更低）的项时，就把新元素插入到它之前（根据这个逻辑，对于其他优先级相同，但是先添加到队列的元素，我们同样遵循先进先出的原则）。要做到这一点，我们可以用JavaScript的array类的splice方法。一旦找到priority值更大的元素，就插入新元素（行{3}）并终止队列循环（行{4}）。这样，队列也就根据优先级排序了

　　如果要添加元素的priority值大于任何已有的元素，把它添加到队列的末尾就行了（行{5}）：

var priorityQueue = new PriorityQueue(); 
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jack", 1);
priorityQueue.enqueue("Camila", 1); 
priorityQueue.print();

　　以上代码是一个使用PriorityQueue类的示例。在下图中可以看到每条命令的结果（以上代码的结果）

queue4

　　第一个被添加的元素是优先级为2的John。因为此前队列为空，所以它是队列中唯一的元素。接下来，添加了优先级为1的Jack。由于Jack的优先级高于John，它就成了队列中的第一个元素。然后，添加了优先级也为1的Camila。Camila的优先级和Jack相同，所以它会被插入到Jack之后（因为Jack先被插入队列）；Camila的优先级高于John，所以它会被插入到John之前

　　我们在这里实现的优先队列称为最小优先队列，因为优先级的值较小的元素被放置在队列最前面（1代表更高的优先级）。最大优先队列则与之相，把优先级的值较大的元素放置在队列最前面

循环队列

　　还有另一个修改版的队列实现，就是循环队列。循环队列的一个例子就是击鼓传花游戏（Hot Potato）。在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩一个孩子（胜者）

　　在下面这个示例中，我们要实现一个模拟的击鼓传花游戏：

function hotPotato (nameList, num){ 
  var queue = new Queue(); // {1}
  for (var i=0; i<nameList.length; i++){
    queue.enqueue(nameList[i]); // {2}
  }
  var eliminated = ''; 
  while (queue.size() > 1){
    for (var i=0; i<num; i++){ 
      queue.enqueue(queue.dequeue()); // {3}
    }
    eliminated = queue.dequeue();// {4} 
    console.log(eliminated + '在击鼓传花游戏中被淘汰。');
  }
  return queue.dequeue();// {5}
}

var names = ['John','Jack','Camila','Ingrid','Carl']; 
var winner = hotPotato(names, 7);
console.log('胜利者：' + winner);

　　实现一个模拟的击鼓传花游戏，要用到Queue类（行{1}）。我们会得到一份名单，把里面的名字全都加入队列（行{2}）。给定一个数字，然后迭代队列。从队列开头移除一项，再将其添加到队列末尾（行{3}），模拟击鼓传花（如果把花传给了旁边的人，被淘汰的威胁立刻就解除了）。一旦传递次数达到给定的数字，拿着花的那个人就被淘汰了（从队列中移除——行{4}）。最后只剩下一个人的时候，这个人就是胜者（行{5}）

　　以上算法的输出如下：

Camila在击鼓传花游戏中被淘汰。 
Jack在击鼓传花游戏中被淘汰。
Carl在击鼓传花游戏中被淘汰。 
Ingrid在击鼓传花游戏中被淘汰。 
胜利者：John

　　下图模拟了这个输出过程：

　　可以改变传入hotPotato函数的数字，模拟不同的场景

最后

　　JavaScript内部控制所使用的也是队列如此基础的数据结构

　　当我们在浏览器中打开新标签时，就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务，它被称为事件循环。浏览器要负责多个任务，如渲染HTML，执行JavaScript代码，处理用户交互（用户输入、鼠标点击等），执行和处理异步请求

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：git笔记

下一篇：前端MVC Vue2学习总结（四）——条件渲染、列表渲染、事件处理器

IDC资讯：主机资讯注册资讯托管资讯 vps资讯网站建设

网站运营：建站经验策划盈利搜索优化网站推广免费资源

网站联盟：联盟新闻联盟介绍联盟点评网赚技巧

行业资讯：搜索引擎网络游戏电子商务广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器安全防护

软件技巧：其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识：网络协议网络安全网络管理组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条

最新资讯

热门关注

热门标签