专栏首页OECOM使用JavaScript创建队列结构

使用JavaScript创建队列结构

队列和栈是两种相似的结构,区别主要在于栈是先进后出,队列是先进先出(FIFO)。队列插入元素是在队尾插入,在队列头弹出,形象的描述为排队,先到的先办事,后到的后办事。在算法应用上可以应用在消息队列、的打印机队列等。

创建队列

和创建栈一样,我们先来创建一个基本的队列结构:

function Queue(){
    var items = [];
}

有了一个基本结构,我们来开始构建队列的功能结构:

  • enqueue(element):向队列尾部添加一个或多个新的元素
  • dequeue():从队列顶部移除元素并返回
  • front():返回队列顶部元素,不对队列做任何操作
  • isEmpty():判断队列是否是空队列,是返回true,否则返回false
  • size():返回队列长度
  • print():打印输出队列内容

我们先来实现一下enqueue方法,这个方法是想队列的尾部添加一个或多个新的元素。这里我们仍然采用数组作为该数据结构的一个基本存储结构,数组的最左侧为队列头,右侧为队尾,于是实现结果如下所示:

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

然后要实现的就是dequeue方法,这个方法是将队列头部的元素移除并返回,这我们就应用到了数组的shift方法,如下所示:

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

如此,添加和移除这两个方法就限定了队列的先进先出的结构特点。

按顺序我们再要实现的就是front方法,该方法用来返回队列头部元素,但是不对队列进行任何操作:

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

然后是判断队列是否为空,这个方法和栈的实现方法相同:

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

size方法就更好说了,直接返回数组长度即可:

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

print方法就是直接将数组内容字符串化输出:

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

至此,我们整个队列的结构和功能就实现了。

简单应用

这个算法应用我们实现的是一个银行排队功能

var bankQueue = new Queue();
bankQueue.nowNumber = 0;
function getCode(){
//点击按钮取号,返回当前的号码
    bankQueue.enqueue(bankQueue.nowNumber+1);
    return bankQueue.front();
}

function callCode(){
//叫号,叫号后号码从队列中移除,并返回所叫号码
    if(!bankQueue.isEmpty()){
        return bankQueue.dequeue();
    }else{
        return -1;//-1代表没有正在等待的号码了
    }
}
function getWaitCount(){
//获取当前等待的所有人数
    return bankQueue.size();
}

以上应用就是队列的一个简单应用,上述例子中队列是一个线性的,在一些算法中可以使用到循环队列,比如说击鼓传花算法的实现。

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

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){
        for (var i=0; i<num; i++){
            queue.enqueue(queue.dequeue()); //将从头部移除并获取到的元素重新压入队列,存储在了队列的尾部
        }
        eliminated = queue.dequeue();//从头部移除并获取,此人是被淘汰的人
        console.log(eliminated + '在击鼓传花游戏中被淘汰。');
    }
    return queue.dequeue();//最后一个人移除并获取出来,此人为胜利者
}
var names = ['John','Jack','Camila','Ingrid','Carl']; var winner = hotPotato(names, 7); console.log('胜利者:' + winner);

实现的过程我们可以看下面这张模拟图

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • promise的使用方法

    异步操作作为JavaScript中的一大特色,解决了JavaScript单线程运行的一个难题,但是很多时候有问题也在于这上面。最大的问题之一,就是异步操作过多的...

    无邪Z
  • flutter dart日期类型操作

    dart的日期类型和js有相通的地方,但也有很大的不同,个人感觉比js的api要好用一些。dart的日期对象是DateTime,下面来逐步介绍一下其api的使用...

    无邪Z
  • Promise实现原理

    我们工作中免不了运用promise用来解决异步回调问题。平时用的很多库或者插件都运用了promise 例如axios、fetch等等。但是你知道promise是...

    无邪Z
  • Golang 的 协程调度机制 与 GOMAXPROCS 性能调优

    正确地认识 G , M , P 三者的关系,能够对协程的调度机制有更深入的理解! 本文将会完整介绍完 go 协程的调度机制,包含:

    _simple
  • Golang 的 协程调度机制 与 GOMAXPROCS 性能调优

    Golang 简称 Go,Go 的协程(goroutine) 和我们常见的线程(Thread)一样,拥有其调度器。

    林冠宏-指尖下的幽灵
  • Java中的5大队列,你知道几个?

    通过前面文章的学习《一文详解「队列」,手撸队列的3种方法!》我们知道了队列(Queue)是先进先出(FIFO)的,并且我们可以用数组、链表还有 List 的方式...

    Java中文社群_老王
  • 图解 Java 中的 5 大队列,再也不用担心排队的问题了

    我们知道,队列(Queue)是先进先出(FIFO)的,并且我们可以用数组、链表还有 List 的方式来实现自定义队列,那么本文我们来系统的学习一下官方是如何实现...

    沉默王二
  • [PhalApi实战篇(1)]Redis队列处理异步任务

    [PhalApi实战篇(1)]Redis队列处理异步任务 ? 前言 先在这里感谢phalapi框架创始人@dogstar,为我们提供了这样一个优秀的开源框架. ...

    喵了个咪233
  • 分布式架构实记——消息队列(一)

    消息队列中间件是分布式系统中重要的组件,主要解决应用耦合,异步消息,流量削锋等问题。实现高性能,高可用,可伸缩和最终一致性架构。是大型分布式系统不可缺少的中间件...

    慕容千语
  • RabbitMQ消息通信

    ---- 概述 RabbitMQ是一个开源的消息代理和队列服务器,用来通过普通协议在完全不同的应用之间共享数据或者将作业排队以便让分布式服务器进行处理。应用程序...

    BrianLv

扫码关注云+社区

领取腾讯云代金券