数据结构 – 队列-一一网

什么是队列？

队例是一种先进先出（FIFO）的数据结构。也是计算机的基础数据结构。

形象比喻：就像是很多人在排队，先来的就先上。

实现的方法

var Queue = function () {
    var items = [];
    
    // 入队
    this.enqueue = function (element) {
        items.push(element);
    }
    
    // 出队
    this.dequeue = function () {
       return items.shift();
    }
    
    // 查看队列头
    this.front = function () {
        return item[0];
    }
    
    // 是否为空
    this.isEmpty = function () {
        return item.length === 0;
    }
    
    // 获取队列长度
    this.size = function () {
        return item.length;
    }
}
复制代码

实战：击鼓传花

简介: 多人围成一圈，传递花，每传3次，花在谁手上，就把他踢出去。

// 玩家列表
var persons= ['a', 'b', 'c', 'd','e', 'f'];
// 游戏规则
var number = 3;
// 击鼓传花游戏
var passGame = function (persons, number) {
    // 创建队列
    var q = new Queue();
    // 把所有玩家加入队列
    for (let i = 0; i < persons.length - 1; i++) {
        q.enqueue(persons[i])
    }
    
    // 定义被淘汰玩家
    var fail;
    // 当队列长度大于1，说明游戏正在进行中
    while(q.size() > 1) {
        // i不为3的玩家，放到队列尾
        for(let i = 0; i < number - 1; i++) {
            q.enqueue(q.dequeue());
        }
        // i为3则淘汰
        fail = q.dequeue();
        console.log(‘被淘汰的玩家是：’, fail);
    }
    // 剩下的最后一位玩家就是赢家
    return q.dequeue();  
}
复制代码

实战：优先队列

var PriorityQueue = function () {
    var items = [];
    
    // 辅助类: 这里相当于一个工厂，创建队列里的元素
    var QueueItem = function(element, priority) {
        this.element = element;
        this.priority = priority;
    }
    
    this.enqueue = function(element, priority) {
      var queueItem = new QueueItem(element, priority);
      var added = false
      for(var i = 0; i < items.length; i++) {
        if(queueItem.priority > items[i].priority) {
          items.splice(i, 0, queueItem);
          added = true;
          break;
        }
      }
      
      // 当插入的元素，优先级最低，则直接放到最后面。
      if(!added) {
        items.push(queueItem);
      }

    }
    
    // 查看当前的队列
    this.getItems = function() {
       return items;
    }
}

var pq = new ProrityQueue();
pq.enqueue('小黑', 10);
pq.enqueue('小明', 12);

复制代码