队列是先进先出（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。
原文地址：
队列是先进先出（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。
原文地址：https://segmentfault.com/a/1190000016900956
队列的JS实现及广度优先搜索（BFS）的实现
原文地址：https://www.cnblogs.com/lalalagq/p/9907658.html