乐趣区

关于算法-数据结构:js算法与数据结构队列

一、队列的定义

二、队列办法

三、js 实现办法如下

// 队列 一种先进先出的数据结构
var Queue = function(){
  // 用数组来模仿 首元素为队头,尾元素为队尾
  var items = []
  // 入队
  this.enqueue = function(element){items.push(element)
  }
  // 出队
  this.dequeue = function(){return items.shift()
  }
  // 查看队列头
  this.front = function(){return items[0]
  }
  // 队列长度
  this.size = function(){return items.length}
  // 判断是否为空
  this.isEmpty= function(){return items.length == 0}
}

四、实战演练

1. 击鼓传花

有多个玩家进行击鼓传花,每位玩家顺次开始击鼓,击一次鼓传花一次,并且计数加 1(从 0 开始),当有玩家击鼓后,计数为 3 时,则淘汰该玩家,计数归 0,持续进行上述过程,直到残余一名玩家为胜利者, 游戏完结。

code

// 击鼓传花
var setFlowerParams = function(user, number){var passFlower = new Queue()
// 初始化队列
for(var i = 0 ; i < user.length ; i++){passFlower.enqueue(user[i])
}
// 循环队列
while(passFlower.size() > 1){for(var i = 0; i < number - 1; i++){passFlower.enqueue(passFlower.dequeue()) 
  }
  var taotai = passFlower.dequeue()
  console.log('淘汰' + taotai)
 }
 return console.log('最终玩家' + passFlower.front())
} 
var user = []

运行后果

2. 优先队列

在队列依据元素的优先级从大到小进行排序

code

// 优先队列
var PriorityQueue = function(){var items = []
  var add = false
  // 辅助类
  var QueueItem = function(element, priority){
    this.element = element
    this.priority = priority
  }
  this.enqueue = function(element, priority){var queueItem = new QueueItem(element, priority)
    for(var i = 0 ; i < items.length ; i++){if(queueItem.priority > items[i].priority){items.splice(i, 0, queueItem)
      add = true
      break
      }
    }
    if(!add){items.push(queueItem)
    }
  }
  // 查看队列
  this.getItems = function(){return items}
}
var priorityqueue = new PriorityQueue()
priorityqueue.enqueue('张飞', 10)
priorityqueue.enqueue('关羽', 20)
priorityqueue.enqueue('刘备', 30)

运行后果

排序后

退出移动版