使用JavaScript创建队列结构

OECOM

发布于 2020-07-02 11:46:58

8320

发布于 2020-07-02 11:46:58

文章被收录于专栏：OECOMOECOM

队列和栈是两种相似的结构，区别主要在于栈是先进后出，队列是先进先出（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);

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-01-19，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度