数据结构 - 队列结构详解

xy 2022-02-19 数据结构

哈喽,大家好，我是xy👨🏻‍💻. 这篇文章：数据结构之队列结构详解 将是我 《javaScript数据结构》系列的第三篇文章；2022 年的 Flag：学习数据结构、算法、设计模式，如果你也想和我一起学习，欢迎加我为好友，拉你进数据结构算法设计模式学习群一起学习交流 ❤️

# 什么是队列结构

在上一篇文章中我们了解了栈结构的特点的先入后出，而队列却是与之相反：先入先出

队列是一种受限的线性结构
受限之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作

生活中类似队列的场景有很多，比如：

食堂排队打饭（喜欢插队的小伙伴除外）
排队上厕所蹲坑（坑位只有一个）
超市排队结账
......

# 队列的实现

队列常见有哪些操作呢?

enqueue(element)：向队列尾部添加一个（或多个）新的项。
dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与 Stack 类的 peek 方法非常类似）。
isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false。
size()：返回队列包含的元素个数，与数组的 length 属性类似。
toString(): 返回当前队列，字符串形式。

创建一个构造函数用来封装队列,在构造函数中定义一个变量 list, 用于保存当前对象中的所有元素;这个变量是一个数组类型. 我们之后在队列中添加元素或者删除元素, 都是在这个数组中完成的.:

function Queue() {
    this.list = []
}

添加操作方法:

function Queue() {
    this.list = []

    //入队列
    Queue.prototype.enqueue = function (e) {
        this.list.push(e)
    }
    //出队列
    Queue.prototype.dequeue = function () {
        return this.list.shift()
    }
    //返回队列中的第一个元素
    Queue.prototype.front = function () {
        return this.list[0]
    }
    //判断队列是否为空
    Queue.prototype.isEmpty = function () {
        if (this.list.length === 0) {
            return true
        } else {
            return false
        }
    }
    //返回队列中元素个数
    Queue.prototype.size = function () {
        return this.list.length
    }
    //返回当前队列
    Queue.prototype.toString = function () {
        let string = ''
        for(let i in this.list) {
            string += `${this.list[i]} `
        }
        return string
    }
}

export default Queue

# 队列方法的使用

简单的来使用下以上封装的类：Queue

// 创建队列对象
var queue = new Queue()

// 在队列中添加元素
queue.enqueue("Vue")
queue.enqueue("React")
queue.enqueue("Angular")

// 查看一下队列前端元素
console.log(queue.front())

// 查看队列是否为空和元素个数
console.log(queue.isEmpty())
console.log(queue.size())

// 从队列中删除元素
console.log(queue.dequeue())
console.log(queue.dequeue())
console.log(queue.dequeue())

# 队列的应用

# 击鼓传花队列实现

这里我们的游戏规则可能和现实中的规则有一些不一样,具体游戏规则如下:

几个人围成一圈,开始数数,数到某个数字的人自然被淘汰
最后剩下的那个人获得胜利,求出最后那个人的位置

//传入人员个数以及每次数数的个数
function passFlower(member, num) {
    let queue = new Queue()

    for(let i=0; i < member.length; i++) {
        queue.enqueue(member[i])
    }

    while (queue.list.length !== 1) {
        for(let i=0; i < num - 1; i++) {
            queue.enqueue(queue.dequeue())
        }
        queue.dequeue()
    }
    return queue.list[0]
}

console.log(passFlower(['V', 'W', 'X', 'Y', 'Z'], 3))

# 优先级队列的实现

实现优先级队列主要有四个方面需要考虑:

封装元素和优先级放在一起(可以封装一个新的构造函数)
添加元素时, 将当前的优先级和队列中已经存在的元素优先级进行比较
一旦优先级, 大于某个元素, 就将该元素插入到元素这个元素的位置. 其他元素会依次向后移动.
如果遍历了所有的元素, 没有找到某个元素被这个新元素的优先级低, 直接放在最后即可.

代码实现:

function PriorityQueue() {
    this.list = []

    function EachElement(e, num) {
        // 元素
        this.element = e
        // 优先级
        this.priority = num
    }
    //入列
    PriorityQueue.prototype.enqueue = function (e, priority) {
        let element = new EachElement(e, priority)

        if(this.list.length === 0) {
            this.list.push(element)
            return;
        }

        for(let i in this.list) {
            if(element.priority < this.list[i].priority) {
                this.list.splice(i, 0, element)
                return;
            }
        }

        this.list.push(element)
    }
    //出列
    PriorityQueue.prototype.dequeue = function () {
        return this.list.shift()
    }
    //返回当前队列的元素个数
    PriorityQueue.prototype.size = function () {
        return this.list.length
    }
    //返回当前队列第一个元素
    PriorityQueue.prototype.front = function () {
        return this.list[0]
    }

    //判断优先级队列是否为空
    PriorityQueue.prototype.isEmpty = function() {
        if(this.list.length === 0) {
            return true
        }
        else {
            return false
        }
    }

    //返回当前队列
    PriorityQueue.prototype.toString = function () {
        let string = ''
        for(let i in this.list) {
            string += `${this.list[i].element}:${this.list[i].priority} `
        }
        return string
    }
}

export default PriorityQueue

# 优先级队列的使用

// 创建优先级队列对象
var pQueue = new PriorityQueue()

// 添加元素
pQueue.enqueue("Vue", 10)
pQueue.enqueue("React", 5)
pQueue.enqueue("Angular", 12)
pQueue.enqueue("Svelte", 3)

// 遍历所有的元素
var size = pQueue.size()
for (var i = 0; i < size; i++) {
    var item = pQueue.dequeue()
    console.log(item.element + "-" + item.priority)
}

# 写在最后

公众号：前端开发爱好者 专注分享 web 前端相关技术文章、视频教程资源、热点资讯等，如果喜欢我的分享，给 🐟🐟 点一个赞 👍 或者 ➕关注 都是对我最大的支持。

欢迎长按图片加好友，我会第一时间和你分享前端行业趋势，面试资源，学习途径等等。

user

关注公众号后，在首页：

回复面试题，获取最新大厂面试资料。
回复简历，获取 3200 套简历模板。
回复React实战，获取 React 最新实战教程。
回复Vue实战，获取 Vue 最新实战教程。
回复ts，获取 TypeScript 精讲课程。
回复vite，获取精讲课程。
回复uniapp，获取 uniapp 精讲课程。
回复js书籍，获取 js 进阶必看书籍。
回复Node，获取 Nodejs+koa2 实战教程。
回复数据结构算法，获取数据结构算法教程。
回复架构师，获取架构师学习资源教程。
更多教程资源应用尽有，欢迎关注获取

栈结构详解