一、什么是队列结构
队列结构(Queue)是另一种受限的数据结构,他是一种受限的线性表,先进先出(FIFO First In First Out)
- 只允许在表的前端
(font)
进行删除操作 - 在表的后端
(rear)
进行插入操作
图解:
二、队列结构的实现
队列的实现和栈一样,有两种方案:
- 基于数组实现
- 基于链表实现
/**
* 封装一个队列类
*/
function Queue() {
// 属性
this.items = []
// 元素进入队列
Queue.prototype.enqueue = function (element) {
this.items.push(element)
}
// 移除队列第一项,并返回数据
Queue.prototype.dequeue = function () {
return this.items.shift()
}
// 返回队列第一项数据
Queue.prototype.front = function () {
return this.items[0]
}
// 判断队列是否为空
Queue.prototype.isEmpty = function () {
return this.items.length == 0
}
// 返回队列的元个数
Queue.prototype.size = function () {
return this.items.length
}
// toString方法
Queue.prototype.toString = function () {
let str = ''
for (let i = 0; i < this.items.length; i++) {
str += this.items[i] + ' '
}
return str
}
}
let queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.enqueue('d')
console.log(queue) // Queue { items: [ 'a', 'b', 'c', 'd' ] }
queue.dequeue()
queue.dequeue()
console.log(queue) // Queue { items: [ 'c', 'd' ] }
console.log(queue.front()) // c
console.log(queue.isEmpty()) // false
console.log(queue.size()) // 2
三、面试题
击鼓传花的实现
/**
* 一群人从一开始读到特定的数字淘汰,返回最后一个人
*/
function gameOut(nameList, num) {
// 创建一个队列结构
let queue = new Queue()
// 将人添加到队列中
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i])
}
while (queue.size() > 1) {
// 开始数数字,不是对应数字则添加到队列末尾,是则移出队列
for (let i = 0; i < num - 1; i++) {
queue.enqueue(queue.dequeue())
}
queue.dequeue()
}
// 获取仅剩的人
let successName = queue.front()
return successName
}
console.log(gameOut(['张三', '李四', '王五'], 2)) // 王五
console.log(gameOut(['Monkey', 'Lucy', 'Tom', 'Lilei', 'Wang'], 3)) // Lilei
四、优先级队列
普通队列插入元素,数据会被放入后端
,等待前端数据处理完毕才会处理
优先级队列插入元素会考虑数据的优先级
,进行比较后会得出正确的位置
- 每个数据不仅仅是一个数据,还有数据的优先级
- 添加方式中,根据优先级将数据放入正确的位置
优先级队列的封装:
/**
* 封装一个优先级队列,使用数字代表优先级
*/
// 规定数据越小,优先级越高
function PriorityQueue() {
// 内部类,保存数据和优先级
function QueueElement(element, priority) {
this.element = element
this.priority = priority
}
// 使用属性保存数据
this.items = []
// 实现插入方法
PriorityQueue.prototype.enqueue = function (element, priority) {
// 创建QueueElement对象
let queueElement = new QueueElement(element, priority)
// 判断队列是否为空
if (this.items.length == 0) {
this.items.push(queueElement)
} else { // 不为空,从最大优先级开始比较
let flag = false
for (let i = 0; i < this.items.length; i++) {
if (queueElement.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElement) // 前方插入
flag = true
break // 跳出循环
}
}
if (!flag) { // 比较完毕,优先级是最小的,直接放到最后
this.items.push(queueElement)
}
}
}
// 移除队列第一项,并返回数据
PriorityQueue.prototype.dequeue = function () {
return this.items.shift()
}
// 返回队列第一项数据
PriorityQueue.prototype.front = function () {
return this.items[0]
}
// 判断队列是否为空
PriorityQueue.prototype.isEmpty = function () {
return this.items.length == 0
}
// 返回队列的元个数
PriorityQueue.prototype.size = function () {
return this.items.length
}
// toString方法
PriorityQueue.prototype.toString = function () {
let str = ''
for (let i = 0; i < this.items.length; i++) {
str += this.items[i].element + ':' + this.items[i].priority + ' '
}
return str
}
}
let pq = new PriorityQueue()
pq.enqueue('吃饭', 10)
pq.enqueue('睡觉', 50)
pq.enqueue('打游戏', 100)
pq.enqueue('学习', 1)
console.log(pq.toString()) // 学习:1 吃饭:10 睡觉:50 打游戏:100
文章评论