队列的JS实现及广度优先搜索(BFS)的实现

队列是先进先出(FIFO)的数据结构,插入操作叫做入队,只能添加在队列的末尾;删除操作叫做出队,只能移除第一个元素。在JS中,用数组可以很简单的实现队列。

function Queue () {
    this.queue = [];
}
// 增加
Queue.prototype.enQueue = function(x) {
    this.queue.push(x);
    return true;
}
// 删除
Queue.prototype.deQueue = function() {
    if(this.isEmpty()) {
        return false;
    }
    this.queue.shift();
    return true;    
}
// 获取队首元素
Queue.prototype.front = function() {
    if(this.isEmpty()) {
        return false;
    }
    this.queue[0];  
}
// 是否为空
Queue.prototype.isEmpty = function() {
    return !this.queue.length
}

以上就实现了队列的数据结构,那么队列这种数据结构有什么作用呢?在广度优先搜索(BFS)中,很适合队列。那什么是BFS。在树的遍历中,有两种遍历方式,其中一种就是从根节点一层一层的往下遍历,这就是广度优先;另一种是先由根节点选一条路径直接遍历到叶子节点,这就是深度优先搜索(DFS)。队列可以用在BFS中,下面我们来实现一个广度优先搜索的例子,返回目标节点深度。

let root = {
            key: 1,
            children: [
                {
                    key:2,
                },
                {
                    key:3,
                    children:[
                        {
                            key:4,
                        }
                    ]
                }
            ]
        } // 数据源

function bfs(root, target) {
    //利用上面创建的Queue,当然也可以直接用数组实现
    let queue = new Queue();
    let step = 0;  // 根节点到目标节点之间的深度
    queue.enQueue(root); //将根节点加入
    //遍历队列
    while(!queue.isEmpty()) {
        step += 1;
        let len = queue.length;
        // 分层遍历队列,没有目标元素则删除该层元素,继续遍历下一层
        for(let i =0; i<len; i++) {
            let cur = queue.front()  // 获取队首元素
            if(target === cur.key) return step; //如果是目标元素,返回
            // 如果不是,将下一层节点加入到队列
            if(cur.children && cur.children.length) {
                cur.children.map(item => {
                    queue.enQueue(item)
                })
            }
            queue.deQueue()  //然后将遍历过的节点删除,
        }
    }
}

bfs(root,4)

这样我们就完成了BFS的实现思路,大家可已参照该思路在具体的业务中灵活运用BFS。

原文链接:segmentfault.com

上一篇:浏览器拦截打开新窗口情况总结
下一篇:理解 React Hooks

相关推荐

  • 🙋Hanjst汉吉斯特改进+enSafeExpression安全表达式等

    Hanjst汉吉斯特模版语言及模版引擎,近期持续改进升级。 这次改进主要是增加了对安全输出表达式兼容,由于涉及到对软件开发过程中的效率和软件运行效率的平衡和取舍,所以多写了几句,以描述这个权衡利弊对...

    10 天前
  • 🙋Hanjst汉吉斯特升级:+showImageAsync及性能改进等

    自2019年元旦🙋Hanjst汉吉斯特 模板语言及其编译引擎发布,已经过去一年多了。 这期间随着 🙋Hanjst汉吉斯特 的推广应用,我们也陆续发布了如下一些更新内容: 🛠️Hanjst/汉吉...

    1 个月前
  • 😉我用 Nuxt.js 仿了个掘金

    前言 首先肯定是要夸夸掘金啦,最开始从 CSDN 到 博客园 再到 掘金,个人感觉掘金的技术氛围非常的nice,真是个宝藏社区👏。技术文章大多以前端为主,对前端开发者非常友好,质量也是歪瑞古的。

    21 天前
  • 😀一个原生js弹幕库

    danmujs 😀一个原生js弹幕库,基于 CSS3 Animation 地址、核心代码 本项目基于 rcbullets,项目约70%的代码基于rcbullets,首先要感谢这个项目的作者,如...

    4 个月前
  • 🕵️‍♀️由原型到JS中的“模拟类”

    讲述了有关 JavaScript 中原型相关知识,又引出了 JavaScript 中的“类“究竟是什么?,以及一系列相关问题。 一、前置知识 1、JavaScript 的面向对象(OOP) ​ 面向...

    2 个月前
  • 🔥《吊打面试官》系列 Node.js 必知必会必问!

    (/public/upload/f204a3b224d986128f1b4d9b8d06cd17) 前言 codeing 应当是一生的事业,而不仅仅是 30 岁的青春🍚 本文已收录 Git...

    2 个月前
  • 💖CSS + JS 送学妹满屏幕小爱心

    故事开始 午饭时间,暗恋已久的学妹拉着我的衣袖:“学长学长,你能不能让这些爱心变成五颜六色的吗~”。 我在旁边笑开了花~~~ image.png(/public/upload/04aaa24e...

    1 个月前
  • (vuejs学习)2、使用ElementUI(*)

    1.element安装 开发环境是win10,一到node官网下载node的.msi包(https://npm.taobao.org/mirrors/node/v10.16.0/nodev10.16....

    10 个月前
  • (vuejs学习)1、Vue初上手(*)

    参考《官方(https://cli.vuejs.org/zh/guide/installation.html)》官方: Node 版本要求: Vue CLI 需要 Node.js 8.9 或更高...

    10 个月前
  • 黄金搭档 -- JS 装饰器(Decorator)与Node.js路由

    很多面对象语言中都有装饰器(Decorator)函数的概念,Javascript语言的ES7标准中也提及了Decorator,个人认为装饰器是和一样让人兴奋的的变化。

    1 年前

官方社区

扫码加入 JavaScript 社区