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);

实现的过程我们可以看下面这张模拟图
使用JavaScript创建队列结构

参与评论