队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
- 用数组实现队列
function Queue () {
let items = []
//向队列尾部添加一个元素
this.enquene = function (item) {
items.push(item)
}
//删除队列第一个元素
this.dequeue = function () {
return items.shift()
}
//获取队列头部元素
this.head = function () {
return items[0]
}
//获取队列尾部元素
this.tail = function () {
return items[items.length - 1]
}
//获取队列长度
this.size = function () {
return items.length
}
//判断队列是否为空
this.isEmpty = function () {
return items.length === 0
}
//清空队列
this.clear = function () {
items = []
}
this.get = function () {
return items
}
}
- 用队列实现约瑟夫环
let queue = new Queue()
for (let i = 0; i < 100; i++) {
queue.enquene(i)
}
function josephRing () {
let index = 0
while (queue.size() !== 1) {
index++
const popItem = queue.dequeue()
if (index % 3 !== 0) {
queue.enquene(popItem)
}
}
return queue.head()
}
console.log(josephRing()) //90
- 斐波那契序列
//斐波那契序列 fn = f(n-1) + f(n-2) n>=2
function fibonacci (n) {
if (n === 0) return 0
let queue = new Queue()
let index = 0
//先把起始值加入队列
queue.enquene(1)
queue.enquene(1)
while (index < n - 2) {
//弹出队列第一个元素
const deleteItem = queue.dequeue()
//获取队列第一个元素
const headItem = queue.head()
const nextItem = deleteItem + headItem
queue.enquene(nextItem)
index++
}
//最后剩两个数，第二个就是最终的结果
return queue.tail()
}
console.log(fibonacci(0)) // 0
console.log(fibonacci(1)) // 1
console.log(fibonacci(2)) // 1
console.log(fibonacci(3)) //2
console.log(fibonacci(4)) //3
console.log(fibonacci(5)) //5
console.log(fibonacci(6)) //8
- 用队列实现栈
function Stack() {
let queue1 = new Queue()
let queue2 = new Queue()
let data_queue = null
let empty_queue = null
//始终让有数据的队列指向data_queue
const init_queue = function() {
if (!queue1.isEmpty() && queue2.isEmpty()) {
data_queue = queue1
empty_queue = queue2
} else if (queue1.isEmpty() && !queue2.isEmpty()) {
data_queue = queue2
empty_queue = queue1
} else {
data_queue = queue1
empty_queue = queue2
}
}
this.push = function(item) {
init_queue()
data_queue.enqueue(item)
}
this.pop = function() {
init_queue()
//因为队列是先进先出 利用这点 将data_queue队列的数据依次删除并添加到empty_queue中，直到data_queue剩下一个时，就可以直接删除并返回了
while (data_queue.size() > 1) {
empty_queue.enqueue(data_queue.dequeue())
}
return data_queue.dequeue()
}
this.top = function() {
init_queue()
return data_queue.tail()
}
this.size = function() {
init_queue()
return data_queue.size()
}
this.get = function() {
init_queue()
return data_queue.get()
}
}
let stack = new Stack()
stack.push(3)
stack.push(2)
stack.push(5)
console.log(stack.get()) // [3, 2, 5]
stack.pop()
console.log(stack.get()) //[3, 2]
- 杨辉三角
function yanghui(n) {
let line = ''
let queue = new Queue()
queue.enqueue(1)
queue.enqueue(0) //用0来分割每一层的数据
for (let i = 1; i < n; i++) {
let prev = 0
while (true) {
const currnet = queue.dequeue()
if (currnet === 0) {
queue.enqueue(1)
queue.enqueue(0)
line += '\r\n'
break
} else {
let newCount = prev + currnet
prev = currnet
queue.enqueue(newCount)
line += ' ' + currnet
}
}
}
//因为是计算下一行的数据并将其放入队列中 所以n行的数据还在队列
const items = queue.get()
while (queue.size() !== 1) {
const currnet = queue.dequeue()
line += ' ' + currnet
}
//清空队列
queue.clear()
return line
}
console.log(yanghui(12))
/*
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
*/
