通过JS实现队列的数据结构,首先是最普通的队列,先入先出
![在这里插入图片描述](https://img-blog.csdnimg.cn/191a582a3f3c46109ccf0732ba4c2368.jpeg)
// 队列
function createQueue() {
// 队列
let queue = []
// 入队
const enQueue = (data) => {
if(data == null) return
queue.push(data)
}
// 出队
const deQueue = () => {
if(queue.length === 0) return
const data = queue.shift()
return data
}
// 获取列表
const getQueue = () => {
// 返回一个克隆的数组,避免外界直接操作
return Array.from(queue)
}
return {
enQueue,
deQueue,
getQueue
}
}
还有就是循环队列
![在这里插入图片描述](https://img-blog.csdnimg.cn/533dffbfcd8041b4a7cdcaca7edf8d18.jpeg)
// 循环队列
function cirQueue (n) {
// 设置队列大小
if(!n) return console.error('创建失败,请按照cirQueue(n: number)格式传入')
// 队尾
let tial = 0
// 队头
let head = 0
// 队列
let queue = []
// 入队
function enQueue(data) {
try {
// 判断队列是否已满
if((tial + 1) % n === head) return console.error('队列已满')
tial = (tial + 1) % n
queue.push(data)
} catch(error) {
console.log('error----', error)
}
}
// 出队
function deQueue() {
try {
// 判断空队列
if(head === tial) return console.log('队列为空')
head = (head + 1) % n
let item = queue.shift()
return item
} catch(error) {
console.log('error------', error)
}
}
// 获取队列
function getQueue() {
try {
return Array.from(queue)
} catch(error) {
console.log('error-----', error)
}
}
// 获取队头、尾
function getQueueHeadAndTial() {
return {
tial,
head
}
}
return {
enQueue,
deQueue,
getQueue,
getQueueHeadAndTial
}
}
正常队列可能存在存满的情况,因此需要一定容错机制,当队列满了,可以先把任务存储下来
![在这里插入图片描述](https://img-blog.csdnimg.cn/517f77290e2f43ec9f4ec89acdd69987.jpeg)
// 循环阻塞队列
function cirBlockQueue (n) {
// 设置队列大小
if(!n) return console.error('创建失败,请按照cirQueue(n: number)格式传入')
// 队尾
let tial = 0
// 队头
let head = 0
// 队列
let queue = []
// 阻塞队列
let waitQueue = cirQueue(n)
// 入队
function enQueue(data) {
try {
// 判断队列是否已满
// 阻塞后不直接返回错误 把操作存储下来
// if((tial + 1) % n === head) return console.error('队列已满')
if((tial + 1) % n === head) {
// 阻塞队列未满
const { head: waitQueueHead, tial: waitQueueTial } = waitQueue.getQueueHeadAndTial()
if((waitQueueTial + 1) % n !== waitQueueHead) {
waitQueue.enQueue(data)
return
} else {
return console.error('队列已满')
}
}
tial = (tial + 1) % n
queue.push(data)
} catch(error) {
console.log('error----', error)
}
}
// 出队
function deQueue() {
try {
// 判断空队列
if(head === tial) return console.log('队列为空')
head = (head + 1) % n
let item = queue.shift()
// 阻塞队列不为空
const { head: waitQueueHead, tial: waitQueueTial } = waitQueue.getQueueHeadAndTial()
if(waitQueueHead !== waitQueueTial) {
enQueue(waitQueue.deQueue())
}
return item
} catch(error) {
console.log('error------', error)
}
}
// 获取队列
function getQueue() {
try {
return Array.from(queue)
} catch(error) {
console.log('error-----', error)
}
}
return {
enQueue,
deQueue,
getQueue,
tial,
head
}
}