[数据结构与算法]用JS实现队列-队列的简单理解和基本操作

一、队列的定义

队列： 是先进先出，只允许在一端进行插入操作，而在另一端进行删除操作的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q = (a1,a2,…,an)，那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后，这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍的最后。如图所示：

例如：入队：1,2,3,4,5；出队：1,2,3,4,5；

二、队列的基本操作

/**
 * 队列构造函数
 */
 function Queue() {

    /**
     * 用数组来模拟队列
     * @type {Array}
     */
    var items = [];
  
    /**
     * 将元素推入队列
     * @param  {Any} ele 要推入队列的元素
     */
    this.enqueue = function(ele) {
      items.push(ele);
    };
  
    /**
     * 将队列中第一个元素弹出
     * @return {Any} 返回被弹出的元素
     */
    this.dequeue = function() {
      return items.shift()
    };
  
    /**
     * 查看队列的第一个元素
     * @return {Any} 返回队列中第一个元素
     */
    this.front = function() {
      return items[0];
    };
  
    /**
     * 确定队列是否为空
     * @return {Boolean} 若队列为空则返回true,不为空则返回false
     */
    this.isAmpty = function() {
      return items.length === 0
    };
  
    /**
     * 返回队列的长度
     * @return {Number} 队列的长度
     */
    this.size = function() {
      return items.length;
    };
  
    /**
     * 清空队列中所有内容
     */
    this.clear = function() {
      items = [];
    };
  
    /**
     * 以字符串显示队列中所有内容
     */
    this.print = function() {
      console.log(items.toString());
    };
  }
  

三、常用应用

/**
   * 击鼓传花的小游戏
   * @param  {Array} nameList 参与人员列表
   * @param  {Number} num      在循环中要被弹出的位置
   * @return {String}          返回赢家(也就是最后活下来的那个)
   */
  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 + " Get out!")
    }
  
    return "胜利者："+queue.dequeue();
  }
  
  var nameList = ['小明', '小红', '小王', '小强']
  
  console.log(hotPotato(nameList,3))

结果：