??隊(duì)列是遵循先進(jìn)先出服務(wù)的一組有序的項(xiàng)扒接，隊(duì)列在尾部添加新元素吹菱，并從頂部移除元素楣黍，最新添加的元素必須排在隊(duì)列的末尾附迷。
??讓我們用JS實(shí)現(xiàn)一個(gè)隊(duì)列:
function Queue() {
let items = []
this.enqueue = function (element) {
items.push(element)
}
this.dequeue = function () {
return items.shift()
}
this.front = function () {
return items[0]
}
this.isEmpty = function () {
return items.length == 0
}
this.clear = function () {
items = []
}
this.size = function () {
return items.length
}
this.print = function () {
console.log(items.toString())
}
}
??隊(duì)列大量應(yīng)用在計(jì)算機(jī)科學(xué)以及我們的生活中惧互，如我們需要排隊(duì)進(jìn)入電影院，在醫(yī)院需要排號(hào)喇伯。但有時(shí)候也需要設(shè)置優(yōu)先級(jí)喊儡，比如醫(yī)院的急診科，醫(yī)生會(huì)優(yōu)先處理病情比較嚴(yán)重的患者稻据，我們來(lái)實(shí)現(xiàn)個(gè)優(yōu)先隊(duì)列艾猜，根據(jù)元素的優(yōu)先級(jí)添加。
function PriorityQueue() {
let items = []
function QueueElement(element, priority) {
this.element = element
this.priority = priority
}
this.isEmpty = function () {
return items.length == 0
}
this.print = function () {
let str = ''
for (let i = 0; i < items.length; i++) {
str += items[i].element + ' '
}
console.log(str)
}
this.enqueue = function (element, priority) {
let queueElement = new QueueElement(element, priority)
if (this.isEmpty()) {
items.push(queueElement)
} else {
let added = false
for (let i = 0; i < items.length; i++) {
if (queueElement.priority < items[i].priority) {
items.splice(i, 0, queueElement)
added = true
break
}
}
if (!added) {
items.push(queueElement)
}
}
}
}
let priorityQueue = new PriorityQueue()
priorityQueue.enqueue('yiyou', 10)
priorityQueue.enqueue('world', 2)
priorityQueue.enqueue('hello', 1)
console.log(priorityQueue.print()) // hello world yiyou
??還有一個(gè)修改版的隊(duì)列實(shí)現(xiàn)，是循環(huán)隊(duì)列匆赃。循環(huán)隊(duì)列的一個(gè)例子就是擊鼓傳花游戲淤毛。在這個(gè)游戲中，孩子們圍成一個(gè)圓圈算柳，把花盡快地傳遞給旁邊的人低淡，某一時(shí)刻傳花停止，這個(gè)時(shí)候花在誰(shuí)手里瞬项，誰(shuí)就退出圓圈結(jié)束游戲蔗蹋，重復(fù)這個(gè)過(guò)程，直到只剩一個(gè)孩子囱淋。
function hotPotato (nameList, num) {
let queue = new Queue()
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i])
}
let eliminated = ''
while (queue.size() > 1) {
for (let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue()) // 循環(huán)隊(duì)列的核心
}
eliminated = queue.dequeue()
console.log(eliminated + '在擊鼓傳花游戲中被淘汰')
}
return queue.dequeue()
}
let names = ['snow', 'john', 'alia', 'sansa', 'blue']
let winner = hotPotato(names, 7)
console.log('勝利者' + winner)
// alia在擊鼓傳花游戲中被淘汰
// john在擊鼓傳花游戲中被淘汰
// blue在擊鼓傳花游戲中被淘汰
// sansa在擊鼓傳花游戲中被淘汰
// 勝利者snow
