目录一.认识队列二.队列的应用三.队列类的创建四.队列的常见操作五.击鼓传花六.优先级队列七.优先级队列的实现一.认识队列 受限的线性结构: 我们已经学习了一种受限的线性结构:栈结构
受限的线性结构:
队列(Queue),它是一种受限的线性表,先进先出(FIFO First ln First Out)
生活中类似的队列结构
打印队列:
线程队列:
队列如何实现呢?
我们一起来研究一下队列的实现.
队列的实现和栈一样,有两种方案:
function Queue() {
//属性
this.items = []
}
队列有哪些常见的操作呢?
现在,,我们来实现这些方法.
其实很栈中方法的实现非常相似.因为我们的队列也是基于数组的
//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
优先级队列的特点:
优先级队列主要考虑的问题:
优先级队列的应用:
1.一个现实的例子就是机场登机的顺序
2.另一个现实中的例子是医院的(急诊科)候诊室。
3.计算机中,我们也可以通过优先级队列来重新排序队列中任务的顺序
比如每个线程处理的任务重要性不同,我们可以通过优先级的大小,来决定该线程在队列中被处理的次序.
现优先级队列相对队列主要有两方面需要考虑:
1)封装元素和优先级放在一起(可以封装一个新的构造函数)
2)添加元素时,将新插入元素的优先级和队列中已经存在的元素优先级进行比较,以获得自己正确的位置.
//封装优先级队列
function PriorityQueue() {
//在PriorityQueue重新创建了一个类
function QueueElemnt(element, priority) {
this.element = element
this.priority = priority
}
//封装属性
this.items = []
//1.实现插入方法
PriorityQueue.prototype.enqueue = function (element, priority) {
//创建QueueElement对象
let queueElemnt = new QueueElemnt(element, priority)
//判断队列是否为空
if (this.items.length === 0) {
this.items.push(queueElemnt)
} else {
let added = false
for (let i = 0; i < this.items.length; i++) {
if (queueElemnt.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElemnt)
added = true
break
}
}
if (!added) {
this.items.push(queueElemnt)
}
}
}
//2.从队列中删除前端元素
PriorityQueue.prototype.dequeue = function () {
return this.items.shift()
}
//3.查看前端元素
PriorityQueue.prototype.front = function () {
return this.items[0]
}
//4.查看队列是否为空
PriorityQueue.prototype.isEmpty = function () {
return this.items.length === 0
}
//5.查看队列中元素的个数
PriorityQueue.prototype.size = function () {
return this.items.length
}
//6.toString方法
PriorityQueue.prototype.toString = function () {
let resultString = ''
for (let i = 0; i < this.items.length; i++) {
resultString += this.items[i] + ''
}
return resultString
}
}
// 测试代码
let pq = new PriorityQueue()
pq.enqueue('abc', 111)
pq.enqueue('cba', 151)
pq.enqueue('nba', 66)
pq.enqueue('wba', 856)
console.log(pq);
到此这篇关于js数据结构之队列结构详解的文章就介绍到这了,更多相关JS队列结构内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: JS数据结构之队列结构详解
本文链接: https://www.lsjlt.com/news/170956.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-01-12
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0