JavaScript实现队列结构过程

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› JavaScript›JavaScript编程经验

原作者: [db:作者] 来自: [db:来源] 收藏邀请

一、认识队列

前面的博客已经讲了受限的数据结构—栈，现在，我们再来看看队列（Queue）。

它是受限的线性表，先进先出（FIFO）,即first in first out。
受限之处在于它只允许在表的前端（front）进行删除操作。
而在表的后端（rear）进行插入操作。

其结构图可以表示为：

生活中类似于队列的：例如：当我们在排队买东西的时候，先到先买一样。

二、封装队列

这里也采用数组的方式实现队列结构，首先，创建一个类。

 function Queue(){
            
        }

在其内部添加属性和方法，将数组通过属性的方法添加给该类。然后采用原型的方法添加常用的操作。

队列常用的操作有：

enqueue(element)：向队列尾部添加一个（或多个）新的项
dequeue() ：移除队列的第一（即排在队列最前面的）项，并且返回被移除的元素
front() ：返回队列中第一个元素----最先被添加，也将是最先被移除的元素
isEmpty() ：如果队列中不包含任何元素，返回true，否则，返回false
size() ：返回队列包含的元素个数
toString() ：将队列中的内容，转化成字符串形式

现在就来具体实现：

function Queue(){
     this.items = [];
     //向队列尾部添加一个（或多个）新的项 enqueue()
     Queue.prototype.enqueue = function(element){
         this.items.push(element);
     }
     //移除队列的第一（即排在队列最前面的）项dequeue()
     Queue.prototype.dequeue = function(){
          return this.items.shift();
      }
     //返回队列中第一个元素 front()
     Queue.prototype.front = function() {
          return this.items[0];
      }
     //判断栈是否空isEmpty()
     Queue.prototype.isEmpty = function(){
         return this.items.length == 0;
     }
     //返回队列包含的元素个数 size()
     Queue.prototype.size = function(){
         return this.items.length;
     }
     //将队列中的内容，转化成字符串形式 toString()
     Queue.prototype.toString  = function(){
         var str = '';
         for(var i =0;i<this.items.length;i++){
             str += this.items[i] + ' ';
         }
         return str;
     }
 }

以上就是队列的封装，现在进行验证：

 var queue = new Queue();
 queue.enqueue(10);
 queue.enqueue(20);
 queue.enqueue(30);
 queue.enqueue(40);
 queue.enqueue(50);
 console.log(queue);
 console.log('移除的第一项是：'+queue.dequeue());
 console.log('队列中的第一个元素是：'+queue.front());
 console.log('栈是否为空：'+queue.isEmpty());
 console.log('栈结构的内容为：');
 console.log(queue.toString());

输出的结果为：

构建成功。

来看一个击鼓传花的案例吧！

三、击鼓传花案列

原游戏规则：

班级中玩一个游戏，所有学生围成一圈，从某位同学手里开始像旁边的同学传一束花
此时一个人在击鼓，当鼓声停下的时候，花落在谁手里，谁就被惩罚。

修改游戏规则：

几个朋友一起玩游戏，围成一圈，开始数数，数到某个数字的人自动淘汰
最后剩下的这个人获得胜利，判断最后剩下的是原来在哪一个位置上的人？

封装一个基于队列的函数：

参数：所有参与人的姓名，基于的数字
结果：最终剩下的人的姓名

代码如下：

 // 封装队列
 function Queue(){
     this.items = [];
     //末尾添加元素
     Queue.prototype.enqueue = function(element){
         this.items.push(element);
     }
     //移除第一个元素
     Queue.prototype.dequeue = function(){
         return this.items.shift();
     }
     //返回第一个元素
     Queue.prototype.front = function(){
         return this.items[0];
     }
     //返回队列包含的元素个数
     Queue.prototype.size = function(){
         return this.items.length;
     }
 }
 
 function passGame(nameList,num){
     // 创建队列
     var queue = new Queue();
     //将所有的人添加到队列
     for(var i = 0;i<nameList.length;i++){
         queue.enqueue(nameList[i]);
     }
     //进行游戏
    while(queue.size() > 1){
         //num数字之前的人重新添加到队列末尾
         for(var i =1;i<num;i++){
             queue.enqueue(queue.dequeue());
         }
       //num数字的人直接移除
         queue.dequeue();
    }
    //获取获胜者信息
    var endName = queue.front();
    console.log('最终剩下的人是：'+endName);
    return nameList.indexOf(endName);
 }
 
 //进行测试
 var nameList = ['a','b','c','d','e'];
 var g = passGame(nameList,5);
 console.log('这个人的位置是：'+g);

输出结果为：

到此这篇关于JavaScript实现队列结构过程的文章就介绍到这了,更多相关JavaScript实现队列结构内容请搜索极客世界以前的文章或继续浏览下面的相关文章希望大家以后多多支持极客世界！