队列结构(Queue)
队列也是一种受限的线性表,他的特点是先进先出
- 受限之处在于他只允许在表的前端(front)进行删除操作
- 而在表的后端(rear)进行插入操作
队列的常见操作:
- enqueue(element):向队列尾部添加一个新的项;
- dequeue():移除队列的第一(即排在队列最前面的)项,并返回被移除的元素;
- front():返回队列中的第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息与Stack类的peek方法非常类似);
- isEmpty():如果队列中不包含任何元素,返回true,否则返回false;
- size():返回队列包含的元素个数,与数组的length属性类似;
- toString():将队列中的内容,转成字符串形式;
代码封装实现
// 封装队列类
class Queue {
constructor() {
// 属性
this.items = []
}
// 相关操作
enqueue(el) {
// 向队列尾部添加一个新的项
this.items.push(el)
}
dequeue() {
// 移除队列的第一 并返回被移除的元素
return this.items.shift()
}
front() {
// 返回队列中最先被添加的元素,队列不做任何变动
return this.items[0]
}
isEmpty() {
// 如果队列中不包含任何元素,返回true,否则返回false
return this.items.length === 0
}
size() {
// 返回队列包含的元素个数
return this.items.length
}
toString() {
// 将队列中的内容,转成字符串形式
let res = ''
for (let i = 0; i < this.items.length; i++) {
res += this.items[i] + ''
}
return res
}
}
const queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
console.log(queue);
队列应用
击鼓传花是一个常见的面试算法题,使用队列可以非常方便的实现最终的结果
游戏规则(修改过):
- 几个朋友一起玩一个游戏,围成一圈,开始数数,数到某个数字的人自动淘汰
- 最后剩下的这个人会获得胜利,请问最后剩下的是原来在哪一个位置的人?
封装一个基于队列的函数:
- 参数:所有参与人的姓名,基于的数字
- 结果:最终剩下的那个人的姓名
代码实现
// 面试题:击鼓传花
function passGame(nameList, num) {
// 1.创建队列结构
const queue = new Queue()
// 2.将所有人依次加入到队列中
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i])
}
// 3.开始数数字
while (queue.size() > 1) {
// 不是num的时候,重新加入到队列的末尾
// 是num的时候,从队列中删除
// num数字之前的人重新放到队列末尾
for (let i = 0; i < num - 1; i++) {
queue.enqueue(queue.dequeue())
}
// num对应的人直接删除掉
queue.dequeue()
}
// 4.获取剩下的人
return queue.front()
}
console.log(passGame([1,2,3,4,5], 2)); // 3
优先级队列
优先级队列主要考虑的问题为:
- 每个元素不再只是一个数据,还包含数据的优先级
- 在添加数据过程中,根据优先级放入到正确位置
优先级队列封装:
class QueueElement {
constructor(element, priority) {
this.element = element
this.priority = priority
}
}
class PriorityQueue {
constructor() {
// 属性
this.items = []
}
enqueue(element, priority) {
// 1.创建QueueElement对象
let queueElement = new QueueElement(element, priority)
// 判断队列是否为空
if (!this.items.length) {
this.items.push(queueElement)
} else {
// 判断优先级是不是最小的,如果是最小的,那么就没必要去比较了
if (queueElement.priority >= this.items[this.items.length - 1].priority) {
this.items.push(queueElement)
return
}
// 比较优先级,插入
for (let i = 0; i < this.items.length; i++) {
if (queueElement.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElement)
break
}
}
}
}
// 删除优先级最高的并返回
dequeue() {
return this.items.shift()
}
// 返回优先级最高的
front() {
return this.items[0]
}
// 队列是否为空
isEmpty() {
return this.items.length === 0
}
// 队列长度
size() {
return this.items.length
}
// 返回队列的字符串形态
toString() {
let res = ''
for (let i = 0; i < this.items.length; i++) {
res += this.items[i].element + ' '
}
return res
}
}
const qp = new PriorityQueue()
// enqueue
qp.enqueue('star', 10)
qp.enqueue('tom', 11)
qp.enqueue('jack', 2)
qp.enqueue('gg', 22)
console.log(qp);
标签:queue,return,队列,items,Queue,enqueue,length,结构
From: https://www.cnblogs.com/codehaoran/p/16828272.html