JavaScript队列、优先队列与循环队列

队列是一种遵从先进先出(FIFO)原则的有序集合
队列在尾部添加新元素,从顶部移除元素

队列的理解

队列在我们生活中最常见的场景就是排队了
队列这个名字也已经很通俗易懂了

和栈很像,这不过队列是先入先出的数据结构

队列的前面是队头
队列的后面是队尾
出队从队头出
入队从队尾入

队列的创建

和栈类似,这里我就不就不啰嗦了
同样需要实现一些功能
这里我类比生活中的排队上厕所

  • 向队列中添加元素(进入排队的队伍中)
  • 移除队头元素(队伍最前面的人出队进入厕所)
  • 查看队头元素(查看队伍最前面的人)
  • 判断队列是否为空(看看队伍中有没有人)
  • 移除队伍全部元素(厕所炸了,都散了吧)
  • 查看栈里元素个数(查看排队的有多少人)

于是我们可以创建一个完整队列实现,同样是利用我们的数组实现
数组头就是队列头

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.size = function () {
    return items.length;
  };//队列大小
  this.clear = function () {
    items = [];
  };//清空队列
  this.print = function () {
    console.log(items.toString());
  };//打印队列
}
var queue = new Queue(); //声明队列的实例

队列的使用

下面我们就用这个队列简单模拟排队

var queue = new Queue();
console.log("队列是否为空: " + queue.isEmpty());
queue.enqueue('Mr.A');
queue.enqueue('Mr.B');
queue.enqueue('Mr.C');
console.log("当前队列:");
queue.print();
console.log("出队的人: " + queue.dequeue());
console.log("当前队列:");
queue.print();

控制台打印:

优先队列

在我们排队上厕所的时候,来了一位拥有VIP会员卡的朋友,插到了队伍的最前面
过了一会儿又来了一位拥有SVIP会员卡的朋友,插到了VIP的前面

虽然这个比喻可能不恰当,但是生活中可能存在有优先级的队列
优先级高的人可以查到优先级低的人前面

这就是循环队列

如果优先值小的元素放到队列的前面,这叫做最小优先队列
反之优先值大的元素放到队列的前面,这叫做最大优先队列
但其实他们两个仅仅是一个判断的改变,实现方式是一样的
优先队列较普通队列的区别也就是入队要判断优先级,并且需要对我们的元素进行处理,其他方法不变
这处理也就是把元素包装为一个拥有优先级的对象
既然所有对象都有着同样的属性,那我们毫无疑问就应该使用工厂构建
我们可以稍微修改一下我们的队列类
来实现一个最小优先队列

function PriorityQueue() {
  var items = [];
  function QueEle(ele, priority){ //封装我们的元素为一个对象
    this.ele = ele; //元素
    this.priority = priority; //优先级
  }
  this.enqueue = function (ele, priority) {
    var queObj = new QueEle(ele, priority); //创建队列元素对象
    if(this.isEmpty()){ //如果队列是空的,直接插入
      this.push(queObj);
    }else{
      var bAdded = false;
      for(var i = 0, len = items.length; i < len; i++){
        if(priority < items[i].priority){
          items.splice(i, 0, queObj); // 循环队列,如果优先级小于这个位置元素的优先级,插入
          bAdded = true;
          break;
        }
      }
      if(!bAdded){
        items.push(queObj); // 如果循环一圈都没有找到能插队的位置,直接插入队列尾部
      }
    }
  };
  this.dequeue = function () {
    return items.shift();
  };
  this.front = function () {
    return items[0];
  };
  this.isEmpty = function () {
    return items.length === 0;
  };
  this.size = function () {
    return items.length;
  };
  this.clear = function () {
    items = [];
  };
  this.print = function () {
    //这个地方稍微修改一下下
    var temp = [];
    for(var i = 0, len = items.length; i < len; i++){
      temp.push(items[i].ele);
    }
    console.log(temp.toString());
  };
}

解释我已经在代码里说的很明白
下面我们就用这个优先队列同样来模拟排队上WC

var pQueue = new PriorityQueue();
pQueue.enqueue('Mr.A', 3);
pQueue.enqueue('Mr.B', 3);
pQueue.enqueue('Mr.C', 3);
console.log("原队列:");
pQueue.print();
pQueue.enqueue('VIP', 2);
pQueue.enqueue('SVIP', 1);
console.log("新队列:");
pQueue.print();

控制台打印:

循环队列

循环队列典型的例子击鼓传花
还记得在我上高中的时候我们晚自习一停电就玩这个
拿一个东西当“花”,轮着传,“鼓”一停,拿到花的同学就要站起来唱歌
可以把循环队列当作是队列的应用
下面我们来模拟实现循环队列击鼓传花

function hotPotato(pepoleList, frequency){ //参数:表示人的数组,传花的频率
  var queue = new Queue();
  for(var i = 0, len = pepoleList.length; i < len; i++){
    queue.enqueue(pepoleList[i]); //初始化,进入队列
  }
  var eliminated;//被淘汰的同学
  while(queue.size() > 1){ //只要队列至少还有两个人,就一直循环
    for(var i = 0; i < frequency; i++){//出队入队,模拟循环效果
      queue.enqueue(queue.dequeue());
    }
    eliminated = queue.dequeue();//清算
    console.log(eliminated + '被淘汰');
  }
  return queue.dequeue();//返回队列中的最后一人
}
var pepole = ['Mr.A','Mr.B','Mr.C','Mr.D','Mr.E','Mr.F'];
var gameWinner = hotPotato(pepole, 12);
console.log('全场最佳:' + gameWinner);

控制台输出:

以上就是JavaScript下的队列实现。
我们还简单理解了两个特殊的队列:优先队列与循环队列。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • JavaScript数据结构和算法之二叉树详解

    二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成. 二叉树的特点 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母.左孩子和右孩子的指针.每一个节点都是通过指针相互连接的.相连指针的关系都是父子关系. 二叉树节点的定义 二叉树节点定义如下: 复制代码 代码如下: struct

  • JS实现队列与堆栈的方法

    本文实例讲述了JS实现队列与堆栈的方法.分享给大家供大家参考,具体如下: 在面向对象的程序设计里,一般都提供了实现队列(queue)和堆栈(stack)的方法,而对于JS来说,我们可以实现数组的相关操作,来实现队列和堆栈的功能,看下面的相关介绍. 一.看一下它们的性质,这种性质决定了它们的使用场合 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 二.看一下实现的代码(JS代码) var a=new

  • JavaScript数据结构与算法之栈与队列

    学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己

  • JavaScript数组的栈方法与队列方法详解

    数组(Array)和对象(Object)应该是JavaScript中使用最多也是最频繁的两种类型了,Array提供了很多常用的方法:栈方法.队列方法.重排序方法.操作方法.位置方法.迭代方法等等. 1.Array的栈方法 栈是一种LIFO(Last-In-First-Out,后进先出)的数据结构,也就是最新添加的项最早被移除.栈中项的插入(push)和移除,只发生在一个位置--栈的顶部.ECMAScript为数组提供了push()和pop()方法,可以实现类似栈的行为.下面两图分别演示了入栈与出

  • javascript中利用数组实现的循环队列代码

    //循环队列 function CircleQueue(size){ this.initQueue(size); } CircleQueue.prototype = { //初始化队列 initQueue : function(size){ this.size = size; this.list = new Array(); this.capacity = size + 1; this.head = 0; this.tail = 0; }, //压入队列 enterQueue : functio

  • Javascript数据结构与算法之列表详解

    前言:在日常生活中,人们经常要使用列表,比如我们有时候要去购物时,为了购物时东西要买全,我们可以在去之前,列下要买的东西,这就要用的列表了,或者我们小时候上学那段时间,每次考完试后,学校都会列出这次考试成绩前十名的同学的排名及成绩单,等等这些都是列表的列子.我们计算机内也在使用列表,那么列表适合使用在什么地方呢?不适合使用在什么地方呢? 适合使用在:当列表的元素不是很多的情况下,可以使用列表,因为对列表中的元素查找或者排序时,效率还算非常高,反之:如果列表元素非常多的情况下,就不适合使用列表了.

  • JavaScript数据结构之链表的实现

    前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素.如果你在使用数组的时候发现很慢,就可以考虑使用链表. 链表的概念 链表是一种常见的数据结构.它是动态地进行存储分配的一种结构.链表有一个"头指针"变量,以head表示,它存放一个地址,指向一个元素.每个结点都使用一个对象的引用指标它的后继,指向另一

  • JavaScript数据结构之优先队列与循环队列实例详解

    本文实例讲述了JavaScript数据结构之优先队列与循环队列.分享给大家供大家参考,具体如下: 优先队列 实现一个优先队列:设置优先级,然后在正确的位置添加元素. 我们这里实现的是最小优先队列,优先级的值小(优先级高)的元素被放置在队列前面. //创建一个类来表示优先队列 function Priorityqueue(){ var items=[];//保存队列里的元素 function QueueEle(e,p){//元素节点,有两个属性 this.element=e;//值 this.pr

  • JavaScript队列的应用实例详解【经典数据结构】

    本文实例讲述了JavaScript队列的应用.分享给大家供大家参考,具体如下: 和前面介绍的栈相反,队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端进行删除.JavaScript自己提供了两个队列方法shift和push方法,分别是出队和入队,其原理就是将元素插入数组最后一个和删除第一个元素. 这里需要注意一点,就是unshift方法的效率比push的效率要低很多.因为它要将入队之前的数组全部往前移动一位.这里我们就不用代码再次演示了. 和线性表类似,队列也分为顺序队列和链队列

  • JS实现队列的先进先出功能示例

    本文实例讲述了JS实现队列的先进先出功能.分享给大家供大家参考,具体如下: /** * [Queue] * @param {[Int]} size [队列大小] */ function Queue(size) { var list = []; //向队列中添加数据 this.push = function(data) { if (data==null) { return false; } //如果传递了size参数就设置了队列的大小 if (size != null && !isNaN(s

  • JavaScript数据结构学习之数组、栈与队列

    前言 数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合. 常用的数据结构有: 数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表(hash) 本文主要介绍的是数组.栈与队列,下面来一起看看详细的介绍吧. 一.数组 数组是平时使用最常用的数据结构,在JavaScript中数组是动态的分配大小,在这里我不会介绍JavaScript里面数组的所有的方法,而是针对数据结构这个方向谈谈所用到的方法

随机推荐