本文主要是介绍JS数据结构与算法-队列结构,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
队列结构
一.认识队列
- 受限的线性结构:
- 我们已经学习了一种受限的线性结构:栈结构.
- 并且已经知道这种受限的数据结构对于解决某些特定问题,会有特别的
效果.
- 下面,我们再来学习另外一个受限的数据结构:队列.
- 队列(Queue),它是一种受限的线性表,先进先出(FIFO First ln First Out)
- 受限之处在于它只允许在表的前端( front )进行删除操作
- 而在表的后端(rear)进行插入操作
- 生活中类似的队列结构
- 生活中类似队列的场景就是非常多了
- 比如在电影院,商场,甚至是厕所排队.
- 优先排队的人,优先处理.(买票,结账, WC)
二.队列的应用
- 打印队列:
- 有五份文档需要打印,这些文档会按照次序放入到打印队列中.
- 打印机会依次从队列中取出文档,优先放入的文档,优先被取出,并且对该文档进行打印.
- 以此类推,直到队列中不再有新的文档.
- 线程队列:
- 在开发中,为了让任务可以并行处理,通常会开启多个线程.
- 但是,我们不能让大量的线程同时运行处理任务.(占用过多的资源)
- 这个时候,如果有需要开启线程处理任务的情况,我们就会使用线程队列.
- 线程队列会依照次序来启动线程,并且处理对应的任务.
- 队列如何实现呢?
三.队列类的创建
function Queue() {
//属性
this.items = []
}
四.队列的常见操作
- 队列有哪些常见的操作呢?
- enqueue(element):向队列尾部添加一个(或多个)新的项。
- dequeue()∶移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。
- front():返回队列中第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息——与Stack类的peek方法非常类似)。
- isEmpty):如果队列中不包含任何元素,返回true,否则返回false。
- size():返回队列包含的元素个数,与数组的length属性类似。
- toString():将队列中的内容,转成字符串形式
- 现在,,我们来实现这些方法.
- 其实很栈中方法的实现非常相似.因为我们的队列也是基于数组的
//1.将元素加入到队列中
Queue.prototype.enqueue = function (element) {
this.items.push(element)
}
//2.从队列中删除前端元素
Queue.prototype.dequeue = function () {
return this.items.shift()
}
//3.查看前端元素
Queue.prototype.front = function () {
return this.items[0]
}
//4.查看队列是否为空
Queue.prototype.isEmpty = function () {
return this.items.length === 0
}
//5.查看队列中元素的个数
Queue.prototype.size = function () {
return this.items.length
}
//6.toString方法
Queue.prototype.toString = function () {
let resultString = ''
for (let i = 0; i < this.items.length; i++) {
resultString += this.items[i] + ''
}
return resultString
}
五.击鼓传花
//击鼓传花
function paseGame(nameList, num) {
//创建一个队列
let queue = new Queue()
//将所有人依次加入队列
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i])
}
//开始数数字
while (queue.size() > 1) {
//不是num的时候吗,重新加入到队列的末尾
//num数字之前的人重新放入到队列的末尾
for (let i = 0; i < num - 1; i++) {
queue.enqueue(queue.dequeue())
}
//num对应的这个人直接从队列中删除
queue.dequeue()
}
//获取剩下的结果
let endName = queue.front()
console.log(endName);
return nameList.indexOf(endName)
}
paseGame(['lisi', 'zhangsan', 'fgbfd', 'tom', 'jack', 'lisa', 'ez', 'laoshu', 'jikdf', 'dsada', 'poru', 'fjds'], 6)//fgbfd
六.优先级队列
优先级队列的特点:
- 我们知道,普通的队列插入一个元素,数据会被放在后端.并且需要前面所有的元素都处理完成后才会处理前面的数据.
- 但是优先级队列,在插入一个元素的时候会考虑该数
据的优先级.
- 和其他数据优先级进行比较.
- 比较完成后,可以得出这个元素在队列中正确的位置
- 其他处理方式,和基本队列的处理方式一样.
优先级队列主要考虑的问题:
- 每个元素不再只是一个数据,而且包含数据的优先级
- 在添加方式中,根据优先级放入正确的位置.
优先级队列的应用:
- 一个现实的例子就是机场登机的顺序
- 头等舱和商务舱乘客的优先级要高于经济舱乘客。
- 在有些国家,老年人和孕妇(或带小孩的妇女)登机时也享有高于其他乘客的优先级。
- 另一个现实中的例子是医院的(急诊科)候诊室。
- 医生会优先处理病情比较严重的患者。
- 当然,一般情况下是按照排号的顺序。
- 计算机中,我们也可以通过优先级队列来重新排序队列中任务的顺序
- 比如每个线程处理的任务重要性不同,我们可以通过优先级的大小,来决定该线程在队列中被处理的次序.
这篇关于JS数据结构与算法-队列结构的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!