javascript队列,js数组实现队列

JavaScript如何用数组实现队列问题

1.1. 队列的数据结构

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

1.2. Java实现

QueueTest

package ch04;

public class QueueTest {

public static void main(String[] args) {

ArrayQueue queue = new ArrayQueue(10);

System.out.println(queue.isEmpty());

for (int i = 0; i 10; i++) {

queue.insert(i);

}

System.out.println(queue.isFull());

while (!queue.isEmpty()) {

System.out.println(queue.remove());

}

}

}

class ArrayQueue {

private int[] arrInt;// 内置数组

private int front;// 头指针

private int rear;// 尾指针

public ArrayQueue(int size) {

this.arrInt = new int[size];

front = 0;

rear = -1;

}

/**

* 判断队列是否为空

*

* @return

*/

public boolean isEmpty() {

return front == arrInt.length;

}

/**

* 判断队列是否已满

*

* @return

*/

public boolean isFull() {

return arrInt.length - 1 == rear;

}

/**

* 向队列的队尾插入一个元素

*/

public void insert(int item) {

if (isFull()) {

throw new RuntimeException("队列已满");

}

arrInt[++rear] = item;

}

/**

* 获得对头元素

*

* @return

*/

public int peekFront() {

return arrInt[front];

}

/**

* 获得队尾元素

*

* @return

*/

public int peekRear() {

return arrInt[rear];

}

/**

* 从队列的对头移除一个元素

*

* @return

*/

public int remove() {

if (isEmpty()) {

throw new RuntimeException("队列为空");

}

return arrInt[front++];

}

}

运行结果如下:

false

true

1

2

3

4

5

6

7

8

9

相关问答

Q1: 整理涵盖很全很广的前端知识点

HTML、CSS相关

html5新特性、语义化

浏览器渲染机制、重绘、重排

网页生成过程：

重排(也称回流): 当 DOM 的变化影响了元素的几何信息( DOM 对象的位置和尺寸大小)，浏览器需要重新计算元素的几何属性，将其安放在界面中的正确位置，这个过程叫做重排。 触发：

重绘： 当一个元素的外观发生改变，但没有改变布局,重新把元素外观绘制出来的过程，叫做重绘。 触发：

重排优化建议：

transform 不重绘，不回流 是因为 transform 属于合成属性，对合成属性进行 transition/animate 动画时，将会创建一个合成层。这使得动画元素在一个独立的层中进行渲染。当元素的内容没有发生改变，就没有必要进行重绘。浏览器会通过重新复合来创建动画帧。

css盒子模型

所有 HTML 元素可以看作盒子，在CSS中， "box model" 这一术语是用来设计和布局时使用。 CSS 盒模型本质上是一个盒子，封装周围的 HTML 元素，它包括：边距，边框，填充，和实际内容。 盒模型允许我们在其它元素和周围元素边框之间的空间放置元素。

css样式优先级

!importantstyleidclass

什么是BFC？BFC的布局规则是什么？如何创建BFC？BFC应用？

BFC 是 Block Formatting Context 的缩写，即块格式化上下文。 BFC 是CSS布局的一个概念，是一个环境，里面的元素不会影响外面的元素。 布局规则：Box是CSS布局的对象和基本单位，页面是由若干个Box组成的。元素的类型和display属性，决定了这个Box的类型。不同类型的Box会参与不同的 Formatting Context 。 创建：浮动元素 display：inline-block position:absolute 应用: 1.分属于不同的 BFC 时,可以防止 margin 重叠 2.清除内部浮动 3.自适应多栏布局

DOM、BOM对象

BOM（Browser Object Model） 是指浏览器对象模型，可以对浏览器窗口进行访问和操作。使用 BOM，开发者可以移动窗口、改变状态栏中的文本以及执行其他与页面内容不直接相关的动作。 使 JavaScript 有能力与浏览器"对话"。 DOM （Document Object Model） 是指文档对象模型，通过它，可以访问 HTML 文档的所有元素。 DOM 是 W3C （万维网联盟）的标准。 DOM 定义了访问 HTML 和 XML 文档的标准： "W3C 文档对象模型（DOM）是中立于平台和语言的接口，它允许程序和脚本动态地访问和更新文档的内容、结构和样式。" W3C DOM 标准被分为 3 个不同的部分：

什么是 XML DOM ？ XML DOM 定义了所有 XML 元素的对象和属性，以及访问它们的方法。 什么是 HTML DOM？ HTML DOM 定义了所有 HTML 元素的对象和属性，以及访问它们的方法。

JS相关

js数据类型、typeof、instanceof、类型转换

闭包(高频)

闭包是指有权访问另一个函数作用域中的变量的函数 ——《JavaScript高级程序设计》

当函数可以记住并访问所在的词法作用域时，就产生了闭包，

即使函数是在当前词法作用域之外执行 ——《你不知道的JavaScript》

原型、原型链(高频)

原型: 对象中固有的 __proto__ 属性，该属性指向对象的 prototype 原型属性。

原型链: 当我们访问一个对象的属性时，如果这个对象内部不存在这个属性，那么它就会去它的原型对象里找这个属性，这个原型对象又会有自己的原型，于是就这样一直找下去，也就是原型链的概念。原型链的尽头一般来说都是 Object.prototype 所以这就是我们新建的对象为什么能够使用 toString() 等方法的原因。

特点: JavaScript 对象是通过引用来传递的，我们创建的每个新对象实体中并没有一份属于自己的原型副本。当我们修改原型时，与之相关的对象也会继承这一改变。

this指向、new关键字

this 对象是是执行上下文中的一个属性，它指向最后一次调用这个方法的对象，在全局函数中， this 等于 window ，而当函数被作为某个对象调用时，this等于那个对象。 在实际开发中， this 的指向可以通过四种调用模式来判断。

new

作用域、作用域链、变量提升

继承(含es6)、多种继承方式

（1）第一种是以 原型链的方式来实现继承 ，但是这种实现方式存在的缺点是，在包含有引用类型的数据时，会被所有的实例对象所共享，容易造成修改的混乱。还有就是在创建子类型的时候不能向超类型传递参数。

（2）第二种方式是使用 借用构造函数 的方式，这种方式是通过在子类型的函数中调用超类型的构造函数来实现的，这一种方法解决了不能向超类型传递参数的缺点，但是它存在的一个问题就是无法实现函数方法的复用，并且超类型原型定义的方法子类型也没有办法访问到。

（3）第三种方式是 组合继承 ，组合继承是将原型链和借用构造函数组合起来使用的一种方式。通过借用构造函数的方式来实现类型的属性的继承，通过将子类型的原型设置为超类型的实例来实现方法的继承。这种方式解决了上面的两种模式单独使用时的问题，但是由于我们是以超类型的实例来作为子类型的原型，所以调用了两次超类的构造函数，造成了子类型的原型中多了很多不必要的属性。

（4）第四种方式是 原型式继承 ，原型式继承的主要思路就是基于已有的对象来创建新的对象，实现的原理是，向函数中传入一个对象，然后返回一个以这个对象为原型的对象。这种继承的思路主要不是为了实现创造一种新的类型，只是对某个对象实现一种简单继承，ES5 中定义的 Object.create() 方法就是原型式继承的实现。缺点与原型链方式相同。

（5）第五种方式是 寄生式继承 ，寄生式继承的思路是创建一个用于封装继承过程的函数，通过传入一个对象，然后复制一个对象的副本，然后对象进行扩展，最后返回这个对象。这个扩展的过程就可以理解是一种继承。这种继承的优点就是对一个简单对象实现继承，如果这个对象不是我们的自定义类型时。缺点是没有办法实现函数的复用。

（6）第六种方式是 寄生式组合继承 ，组合继承的缺点就是使用超类型的实例做为子类型的原型，导致添加了不必要的原型属性。寄生式组合继承的方式是使用超类型的原型的副本来作为子类型的原型，这样就避免了创建不必要的属性。

EventLoop

JS 是单线程的，为了防止一个函数执行时间过长阻塞后面的代码，所以会先将同步代码压入执行栈中，依次执行，将异步代码推入异步队列，异步队列又分为宏任务队列和微任务队列，因为宏任务队列的执行时间较长，所以微任务队列要优先于宏任务队列。微任务队列的代表就是， Promise.then ， MutationObserver ，宏任务的话就是 setImmediate setTimeout setInterval

原生ajax

ajax 是一种异步通信的方法,从服务端获取数据,达到局部刷新页面的效果。 过程：

事件冒泡、捕获(委托)

event.stopPropagation() 或者 ie下的方法 event.cancelBubble = true; //阻止事件冒泡

ES6

Vue

简述MVVM

MVVM 是 Model-View-ViewModel 缩写，也就是把 MVC 中的 Controller 演变成 ViewModel。Model 层代表数据模型， View 代表UI组件， ViewModel 是 View 和 Model 层的桥梁，数据会绑定到 viewModel 层并自动将数据渲染到页面中，视图变化的时候会通知 viewModel 层更新数据。

谈谈对vue生命周期的理解？

每个 Vue 实例在创建时都会经过一系列的初始化过程， vue 的生命周期钩子，就是说在达到某一阶段或条件时去触发的函数，目的就是为了完成一些动作或者事件

computed与watch

watch 属性监听 是一个对象，键是需要观察的属性，值是对应回调函数，主要用来监听某些特定数据的变化，从而进行某些具体的业务逻辑操作,监听属性的变化，需要在数据变化时执行异步或开销较大的操作时使用

computed 计算属性 属性的结果会被缓存，当 computed 中的函数所依赖的属性没有发生改变的时候，那么调用当前函数的时候结果会从缓存中读取。除非依赖的响应式属性变化时才会重新计算，主要当做属性来使用 computed 中的函数必须用 return 返回最终的结果 computed 更高效，优先使用

使用场景 computed ：当一个属性受多个属性影响的时候使用，例：购物车商品结算功能 watch ：当一条数据影响多条数据的时候使用，例：搜索数据

v-for中key的作用

vue组件的通信方式

父子组件通信

父-子 props ，子-父 $on、$emit` 获取父子组件实例 parent、 parent 、children Ref 获取实例的方式调用组件的属性或者方法 Provide、inject` 官方不推荐使用，但是写组件库时很常用

兄弟组件通信

Event Bus 实现跨组件通信 Vue.prototype.$bus = new Vue() Vuex

跨级组件通信

$attrs、$listeners Provide、inject

常用指令

双向绑定实现原理

当一个 Vue 实例创建时，Vue会遍历data选项的属性，用 Object.defineProperty 将它们转为 getter/setter并且在内部追踪相关依赖，在属性被访问和修改时通知变化。每个组件实例都有相应的 watcher 程序实例，它会在组件渲染的过程中把属性记录为依赖，之后当依赖项的 setter 被调用时，会通知 watcher重新计算，从而致使它关联的组件得以更新。

v-model的实现以及它的实现原理吗？

nextTick的实现

vnode的理解，compiler和patch的过程

new Vue后整个的流程

思考：为什么先注入再提供呢？？

答：1、首先来自祖辈的数据要和当前实例的data,等判重，相结合，所以注入数据的initInjections一定要在 InitState 的上面。2. 从上面注入进来的东西在当前组件中转了一下又提供给后代了，所以注入数据也一定要在上面。

vm.[Math Processing Error]mount(vm.mount(vm.options.el) ：挂载实例。

keep-alive的实现

作用：实现组件缓存

钩子函数：

原理： Vue.js 内部将 DOM 节点抽象成了一个个的 VNode 节点， keep-alive 组件的缓存也是基于 VNode 节点的而不是直接存储 DOM 结构。它将满足条件 （pruneCache与pruneCache） 的组件在 cache 对象中缓存起来，在需要重新渲染的时候再将 vnode 节点从 cache 对象中取出并渲染。

配置属性：

include 字符串或正则表达式。只有名称匹配的组件会被缓存

exclude 字符串或正则表达式。任何名称匹配的组件都不会被缓存

max 数字、最多可以缓存多少组件实例

vuex、vue-router实现原理

vuex 是一个专门为vue.js应用程序开发的状态管理库。 核心概念：

你怎么理解Vue中的diff算法?

在js中,渲染真实 DOM 的开销是非常大的, 比如我们修改了某个数据,如果直接渲染到真实 DOM , 会引起整个 dom 树的重绘和重排。那么有没有可能实现只更新我们修改的那一小块dom而不要更新整个 dom 呢？此时我们就需要先根据真实 dom 生成虚拟 dom ， 当虚拟 dom 某个节点的数据改变后会生成有一个新的 Vnode , 然后新的 Vnode 和旧的 Vnode 作比较，发现有不一样的地方就直接修改在真实DOM上，然后使旧的 Vnode 的值为新的 Vnode 。

diff 的过程就是调用 patch 函数，比较新旧节点，一边比较一边给真实的 DOM 打补丁。在采取 diff 算法比较新旧节点的时候，比较只会在同层级进行。 在 patch 方法中，首先进行树级别的比较 new Vnode 不存在就删除 old Vnode old Vnode 不存在就增加新的 Vnode 都存在就执行diff更新 当确定需要执行diff算法时，比较两个 Vnode ，包括三种类型操作：属性更新，文本更新，子节点更新 新老节点均有子节点，则对子节点进行 diff 操作，调用 updatechidren 如果老节点没有子节点而新节点有子节点，先清空老节点的文本内容，然后为其新增子节点 如果新节点没有子节点，而老节点有子节点的时候，则移除该节点的所有子节点 老新老节点都没有子节点的时候，进行文本的替换

updateChildren 将 Vnode 的子节点Vch和oldVnode的子节点oldCh提取出来。 oldCh和vCh 各有两个头尾的变量 StartIdx和EndIdx ，它们的2个变量相互比较，一共有4种比较方式。如果4种比较都没匹配，如果设置了 key ，就会用 key 进行比较，在比较的过程中，变量会往中间靠，一旦 StartIdxEndIdx 表明 oldCh和vCh 至少有一个已经遍历完了，就会结束比较。

你都做过哪些Vue的性能优化？

你知道Vue3有哪些新特性吗？它们会带来什么影响？

更小巧、更快速 支持自定义渲染器 支持摇树优化：一种在打包时去除无用代码的优化手段 支持Fragments和跨组件渲染

模板语法99%保持不变 原生支持基于class的组件，并且无需借助任何编译及各种stage阶段的特性 在设计时也考虑TypeScript的类型推断特性 重写虚拟DOM 可以期待更多的编译时提示来减少运行时的开销 优化插槽生成 可以单独渲染父组件和子组件 静态树提升 降低渲染成本 基于Proxy的观察者机制 节省内存开销

检测机制 更加全面、精准、高效,更具可调试式的响应跟踪

实现双向绑定 Proxy 与 Object.defineProperty 相比优劣如何?

React

1、react中key的作用，有key没key有什么区别，比较同一层级节点什么意思？

2、你对虚拟dom和diff算法的理解，实现render函数

虚拟DOM 本质上是 JavaScript 对象,是对 真实DOM 的抽象表现。 状态变更时，记录新树和旧树的差异 最后把差异更新到真正的 dom 中 render函数:

3、React组件之间通信方式？

Context 提供了一个无需为每层组件手动添加 props ，就能在组件树间进行数据传递的方法.如果你只是想避免层层传递一些属性，组件组合（ component composition ）有时候是一个比 context 更好的解决方案。 5. 组件组合缺点：会使高层组件变得复杂

4、如何解析jsx

5、生命周期都有哪几种，分别是在什么阶段做哪些事情？为什么要废弃一些生命周期？

componentWillMount、componentWillReceiveProps、componentWillUpdate在16版本被废弃，在17版本将被删除，需要使用UNSAVE_前缀使用，目的是向下兼容。

6、关于react的优化方法

使用return null而不是CSS的display:none来控制节点的显示隐藏。保证同一时间页面的DOM节点尽可能的少。

不要使用数组下标作为key 利用 shouldComponentUpdate 和 PureComponent 避免过多 render function ; render 里面尽量减少新建变量和bind函数，传递参数是尽量减少传递参数的数量。 尽量将 props 和 state 扁平化，只传递 component 需要的 props （传得太多，或者层次传得太深，都会加重 shouldComponentUpdate 里面的数据比较负担），慎将 component 当作 props 传入

使用 babel-plugin-import 优化业务组件的引入，实现按需加载 使用 SplitChunksPlugin 拆分公共代码 使用动态 import ，懒加载 React 组件

7、绑定this的几种方式

8、对fiber的理解

9、setState是同步还是异步的

10、Redux、React-Redux

Redux的实现流程

用户页面行为触发一个 Action ，然后 Store 调用 Reducer ，并且传入两个参数：当前 State 和收到的 Action 。 Reducer 会返回新的 State 。每当 state 更新之后， view 会根据 state 触发重新渲染。

React-Redux:

Provider ：从最外部封装了整个应用，并向 connect 模块传递 store 。 Connect ：

11、对高阶组件的理解

高阶组件是参数为组件，返回值为新组件的函数。 HOC 是纯函数，没有副作用。 HOC 在 React 的第三方库中很常见，例如 Redux 的 connect 组件。

高阶组件的作用：

12、可以用哪些方式创建 React 组件？

React.createClass()、ES6 class 和无状态函数

13、 React 元素与组件的区别？

组件是由元素构成的。元素数据结构是普通对象，而组件数据结构是类或纯函数。

Vue与React对比？

数据流：

react 主张函数式编程，所以推崇纯组件，数据不可变，单向数据流，

vue 的思想是响应式的，也就是基于是数据可变的，通过对每一个属性建立Watcher来监听，当属性变化的时候，响应式的更新对应的虚拟dom。

监听数据变化实现原理 ：

组件通信的区别：jsx和.vue模板。

性能优化

vuex 和 redux 之间的区别？

从实现原理上来说，最大的区别是两点：

Redux 使用的是不可变数据，而 Vuex 的数据是可变的。 Redux 每次都是用新的 state 替换旧的 state ，而 Vuex 是直接修改

Redux 在检测数据变化的时候，是通过 diff 的方式比较差异的，而 Vuex 其实和Vue的原理一样，是通过 getter/setter 来比较的(如果看 Vuex 源码会知道，其实他内部直接创建一个 Vue 实例用来跟踪数据变化)

浏览器从输入url到渲染页面，发生了什么？

网络安全、HTTP协议

TCP UDP 区别

Http和Https区别（高频）

GET和POST区别（高频）

理解xss，csrf，ddos攻击原理以及避免方式

XSS ( Cross-Site Scripting ， 跨站脚本攻击 )是一种代码注入攻击。攻击者在目标网站上注入恶意代码，当被攻击者登陆网站时就会执行这些恶意代码，这些脚本可以读取 cookie，session tokens ，或者其它敏感的网站信息，对用户进行钓鱼欺诈，甚至发起蠕虫攻击等。

CSRF （ Cross-site request forgery ） 跨站请求伪造 ：攻击者诱导受害者进入第三方网站，在第三方网站中，向被攻击网站发送跨站请求。利用受害者在被攻击网站已经获取的注册凭证，绕过后台的用户验证，达到冒充用户对被攻击的网站执行某项操作的目的。

XSS避免方式：

CSRF 避免方式：

DDoS 又叫分布式拒绝服务，全称 Distributed Denial of Service ，其原理就是利用大量的请求造成资源过载，导致服务不可用。

Q2: Node.js适合做主流大型系统吗

这是来自richardrodger一篇博文，主要阐述微服务和模式匹配(消息)，通过Node.js建立一个Http服务器作为微服务，微服务之间通过消息传递，以微服务构建模块，进而模块化构建一个大型系统。原文大意如下：

Node.js能做大型系统吗？回答是肯定的，沃尔玛（Walmart）和Paypal的案例已经证明，那么大型的Node.JS适合主流的开发者吗？如果你认为Node.js这样的大型系统类似Java和.Net，那么你肯定认为不行：javascript在支持复杂系统扩展性方面是一个弱性的语言。它不是强类型语言，而且有一半的语言是无法使用的。

尽管如此，我们已经建立一些大型的NodeJS系统，下面是我们的总结：

传统的主流的最大型的系统是庞大的铁板一块的monolithic，一个特别大的代码库，有很多文件，几千个类无数个配置文件。如果在javascript中建立这样的体制，可能会发疯。那些将Node.js看成类似蜘蛛侠的人只会推崇使用Java和.NET建立庞大的系统。

铁板一块式monolithic系统是坏的

什么是铁板一块monolithic系统，最简单定义就是，你如果拿出来一部分，整体就会运行失败，每个部分连接到其他部门，相互依存。这个词也用来指一块整石头。

这个词语来自古希腊，建筑直接在洛矶山的悬崖上凿成，由于直接雕刻整个山，他们是无法修复的，城市最终陷入下降。软件系统的复杂性随着时间推移，难以修复和延伸，成本不断提高。

铁板一块式的软件产生的开发流程和方法危害更大，因为系统有这么多依赖，你必须关注如何让开发者在改变它们时非常小心，大量精力用于防止代码失败。从瀑布到敏捷，都是为了铁板一块式的软件服务，都是为了让软件变得越来越大。远标之前也讲过这个问题

模块化系统是好的

作为软件开发者，应该努力避免建立铁板式系统，那就是建立模块化系统，当一个部分丢失时，整个系统还是可以运行。虽然像集装箱那样建立软件的模块化是一个很艰难的过程，但是我们知道这是处理复杂性的唯一方法。

对象是地狱

为实现模块化系统，面向对象范式受到推崇，其实对象比你想象中的要相差很多，他们来自天真的数学观点，是一种纯柏拉图的东西，以相同的属性和特征划分对象，表面上看合理，实际你在打破了现实世界的真实面貌，现实世界是混乱，甚至都打破了数学世界。请问集合是包含自身还是不包含自身呢(banq注：罗素的逻辑悖论)。

对象的最终弱点是，他们只是促成了向铁板式庞大系统发展，对象只是一个系统需要的袋袋，什么都可以往里面装，你有属性，私有和公有，你有方法，也许覆盖了其父类，你也可以有状态。

有太多的东西可以装入对象，结果一个巨大的类包含了最纠结最痛苦的大量逻辑。

NodeJs的模式是简单的

有一个例子认为计算斐波纳契数是CPU密集型，而Node.js只有一个线程，那么计算斐波纳契数的性能是可怕的。你可以使用异步委派到到操作系统，使用processes 过程而不是线程处理，为了避免CPU密集型的计算，你需要将计算任务放入队列，然后异步处理它们。

线程是出了名的难，Node.js的胜利就是避免了它们，你的代码变得易懂。

有一个问题是在javascript中如何实现单例，实际上在现实中很少会碰到这种问题，因为模块已经帮你照看一切，最好的方式是你使用Node.js建立一个Server，通过网络和其他部分通信。

NodeJS确实需要你学习一些新模式，主要是回调模式，回调函数的签名有一个规律：如果有错误发生，第一个对象是错误对象，否则，第一个参数是空的，第二个总是返回的结果。

回调函数自然地来自Node.js的事件处理循环， JavaScript最初用来处理浏览器中用户界面事件，现在非常适合处理服务器端事件果。

当你开始使用Node.js的第一件事就是创建回调(像意大利面条)。你结束了大量的缩进代码，使用回调内嵌回调。经过一些练习，你很快学会使用命名良好的函数结构化你的代码，包括异步模块库。

Node.js的另一个重大的模式是流，已经被编写成API，让你轻松 简洁操作和转换数据，你使用管道将数据从一个流接至另外一个恶瘤，你可以读写全双工的数据流。

Q3: JS树结构数据的遍历

title: JS树结构数据的遍历

date: 2022-04-14

description: 针对项目中出现树形结构数据的时候，我们怎样去操作他

项目中我们会经常出现对树形结构的遍历、查找和转换的场景，比如说DOM树、族谱、社会机构、组织架构、权限、菜单、省市区、路由、标签等等。那针对这些场景和数据，我们又如何去遍历和操作，有什么方式或者技巧可以简化我们的实现思路。下面我们将针对常规出现的场景去总结一下我们的遍历方式

树的特点

1、每个节点都只有有限个子节点或无子节点；

2、没有父节点的节点称为根节点；

3、每一个非根节点有且只有一个父节点；

4、除了根节点外，每个子节点可以分为多个不相交的子树；

5、树里面没有环路

下面的图片表示一颗树

在下面的JS中我们由多棵树组成我们的数据

在这数据中我们如何评判数据是否为叶节点（也就是最后一级），我们每个节点都会存在children属性，如果不存在children属性或者children不是一个数组或者children为数组且长度为0我们则认为他是一个叶节点

我们针对树结构的操作离不开遍历，遍历的话又分为广度优先遍历、深度优先遍历。其中深度优先遍历可以通过递归和循环的方式实现，而广度优先遍历的话是非递归的

从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。即访问树结构的第n+1层前必须先访问完第n层。

简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。

所以我们的实现思路是，维护一个队列，队列的初始值为树结构根节点组成的列表，重复执行以下步骤直到队列为空：

取出队列中的第一个元素，进行访问相关操作，然后将其后代元素（如果有）全部追加到队列最后。

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止

1、先序遍历

访问子树的时候，先访问根再访问根的子树

2、后序遍历

访问子树的时候，先访问子树再访问根

1、先序遍历

先序遍历与广度优先循环实现类似，要维护一个队列，不同的是子节点不追加到队列最后，而是加到队列最前面

2、后序遍历

后序遍历就略微复杂一点，我们需要不断将子树扩展到根节点前面去，执行列表遍历，并且通过一个临时对象维护一个id列表，当遍历到某个节点如果它没有子节点或者它本身已经存在于我们的临时id列表，则执行访问操作，否则继续扩展子节点到当前节点前面

对于树结构的遍历操作，其实递归是最基础，也是最容易理解的。递归本身就是循环的思想，所以可以用循环来改写递归,以上的方式在项目中已经廊括了大部分的场景了，我们在日常开发中可以根据场景或者需要去选择我们的遍历方式，或者基于此对他进行调整和优化，至于每种方式的空间复杂度和时间复杂度我们在这个地方就不去尝试了，各位感兴趣可以自己去验证。

广度优先搜索

树的遍历

深度优先搜索

图文详解两种算法：深度优先遍历（DFS）和广度优先遍历（BFS）

二叉树遍历（前序，后序，中序，层次）递归与迭代实现JavaScript

JS树结构操作:查找、遍历、筛选、树和列表相互转换

Q4: JS实现数组排序的方法有哪些

从给定的数据中，随机抽出一项，这项的左边放所有比它小的，右边放比它大的，然后再分别这两边执行上述操作，采用的是递归的思想，总结出来就是　实现一层，分别给两边递归，设置好出口

function fastSort(array,head,tail){

    //考虑到给每个分区操作的时候都是在原有的数组中进行操作的，所以这里head,tail来确定分片的位置

    /*生成随机项*/

    var randomnum = Math.floor(ranDom(head,tail));

    var random = array[randomnum];

    /*将小于random的项放置在其左边  策略就是通过一个临时的数组来储存分好区的结果，再到原数组中替换*/

    var arrayTemp = [];

    var unshiftHead = 0;

    for(var i = head;i = tail;i++){

      if(array[i]random){

        arrayTemp.unshift(array[i]);

        unshiftHead++;

      }else if(array[i]random){

        arrayTemp.push(array[i]);

      }

      /*当它等于的时候放哪，这里我想选择放到队列的前面，也就是从unshift后的第一个位置放置*/

      if(array[i]===random){

        arrayTemp.splice(unshiftHead,0,array[i]);

      }

    }

    /*将对应项覆盖原来的记录*/

    for(var j = head , u=0;j = tail;j++,u++){

      array.splice(j,1,arrayTemp[u]);

    }

    /*寻找中间项所在的index*/

    var nowIndex = array.indexOf(random);

    /*设置出口，当要放进去的片段只有2项的时候就可以收工了*/

    if(arrayTemp.length = 2){

      return;

    }

    /*递归，同时应用其左右两个区域*/

    fastSort(array,head,nowIndex);

    fastSort(array,nowIndex+1,tail);

  }

JavaScript实现多维数组、对象数组排序，其实用的就是原生的sort()方法，用于对数组的元素进行排序。

sort() 方法用于对数组的元素进行排序。语法如下：

arrayObject.sort(sortby)

例如：

function NumAscSort(a,b)

{

 return a - b;

}

function NumDescSort(a,b)

{

 return b - a;

}

var arr = new Array( 3600, 5010, 10100, 801); 

arr.sort(NumDescSort);

alert(arr);

arr.sort(NumAscSort);

alert(arr);