### 队列

``````function Queue() {
this.items = []
}

Queue.prototype.push = function(item) {
this.items.push(item)
}

Queue.prototype.shift = function() {
return this.items.shift()
}

Queue.prototype.isEmpty = function() {
return this.items.length === 0
}

Queue.prototype.size = function() {
return this.items.length
}

Queue.prototype.clear = function() {
this.items = []
}``````

### 两种特殊队列

#### 最小优先队列

``````// 继承 Queue 类
const PriorityQueue = function () {
Queue.apply(this)
}

PriorityQueue.prototype = Object.create(Queue.prototype)

PriorityQueue.prototype.constructor = PriorityQueue

// 修改 push 方法
PriorityQueue.prototype.push = function(item, level) {
if (this.isEmpty()) {
this.items.push({ item, level })
} else {
for (let i = 0; i < this.size(); i++) {
if (level < this.items[i].level) {
this.items.splice(i, 0, { item, level })
return
}
}
add && this.items.push({ item, level })
}
}

PriorityQueue.prototype.print = function() {
for (let obj of this.items) {
console.log(obj.item)
}
}``````
``````// 调用
const queue = new PriorityQueue()
queue.push('张三', 2)
queue.push('李四', 1)
queue.push('赵五', 1)
queue.print() // 李四 赵五 张三``````

#### 循环队列

``````const drumGame = function(names, number) {
const queue = new Queue()
for (let i = 0; i < names.length; i++) {
queue.push(names[i])
}

while (queue.size() > 1) {
for (let i = 0; i < number; i++) {
queue.push(queue.shift())  // 这句是循环队列的核心
}
const loser = queue.shift()
console.log(loser + ' 出局')
}
return queue.shift()           // 留下的最后一个就是胜利者
}

const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl']
const winner = drumGame(names, 7) // 假设每轮传花 7 次
console.log('胜利者是: ' + winner)

// Camila 出局
// Jack 出局
// Carl 出局
// Ingrid 出局
// 胜利者是: John``````