前言
最近在看JavaScript数据结构与算法一书，这里就带大家复习一下数组和栈的数据结构吧~
一、数组
几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。 小tips：JavaScript的第一个版本并没有支持数组。数组存储一系列同一种数据类型的值。
虽然在JavaScript里，也可以在数组中保存不同类型的值，但我们还是要遵守最佳实践，避免这么做。
1.1 创建和初始化数组
1.1.2 使用new关键字
let arr1 = new Array();// 简单地声明并初始化一个数组 let arr2 = new Array(5);// 创建一个指定长度的数组 let arr3 = new Array(1,2,3,4,5);// 将数组元素作为参数传递给它的构造器 复制代码
然而使用new创建数组并不是最好的方式。如果你想在JavaScript中创建一个数组，只要中括号（[]）的形式就可以了。
1.1.3 使用字面量创建数组
let arr1 = []; let arr2 = [1,2,3,4,5] 复制代码
1.2 访问元素和迭代数组
访问特定位置的元素，直接在中括号里传递数值位置即可。
1.2.1 循环迭代数组，打印元素
for(let i = 0;i < arr2.length;i++){ console.log(i) } 复制代码
1.2.2 求斐波那契数列的前20个数
const fibonacci = []; fibonacci[1] = 1; fibonacci[2] = 1; // 根据前面两项即可求出第三项 for(let i = 3;i < 20;i++){ fibonacci[i] = fibonacci[i-1] + fibonacci[i-2] } // 循环数组并打印结果 for(let i = 1 ; i < fibonacci.length;i++){ console.log(fibonacci[i]) } 复制代码
小伙伴们可以直接复制以上代码，然后敲下F12键，然后粘贴代码，敲回车结果就出来啦！
1.3 数组添加元素
在数组中添加和删除元素也很容易但有时也会很棘手。
let newArr = [0,1,2,3,4,5] 复制代码
1.3.1 在数组末尾插入元素
给newArr添加一个元素（比如6）
newArr[newArr.length]=6 复制代码
在JavaScript中，数组是一个可以修改的对象！如果添加元素，它就会动态增长。在C和Java等其他语言中，我们要决定数组的大小，要添加新的元素就要创建一个新的数组！
使用push方法
可以添加任意个元素
newArr.push(6); newArr.push(6,7) 复制代码
1.3.2 在数组开头插入元素
首先腾出数组里第一个元素，把所有的元素向右移动一位。把我们想要的值赋给第一个位置上
Array.prototype.insertFirstPosition = function(value){ for(let i = this.length; i >= 0;i--){ this[i]=this[i-1]; } this[0] = value; }; 复制代码
使用unshift()方法
该方法背后的逻辑和insertFirstPosition方法的行为是一样的
newArr.unshift(-1) newArr.unshift(-2,-1) 复制代码
1.4 删除元素
1.4.1 从数组末尾删除元素
newArr.pop(5); newArr.pop(4,5); 复制代码
通过push和pop方法，能用数组来模拟栈
1.4.2 从数组开头删除元素
newArr.shift(0); 复制代码
1.5 在任意位置添加或删除元素
使用splice方法，简单地通过指定位置/索引,就可以删除相应位置上指定数量的元素 splice方法接受的第一个参数表示想要删除或插入元素的索引值。第二个参数是删除元素的个数（如果为0则是添加元素）。第三个参数往后，就是要添加到数组里的值。
1.6 二维和多维数组
JavaScript之支持一维数组，并不支持矩阵，但是我们可以数组套数组，实现矩阵或任一多维数组
let averageTemp = []; averageTemp[0]=[1,2,3]; averageTemp[1]=[4,5,6]; 复制代码
1.6.1 迭代二维数组的元素
使用一个嵌套的for循环来处理。
function printMatrix(myMatrix){ for(let i = 0;i<myMatrix.length;i++){ for(let j = 0;j<myMatrix[i].length;j++){ console.table(myMatrix[i][j]) } } } 复制代码
1.7 JavaScript的数组方法参考
1.7.1 数组合并
const zero = 0; const arr1 = [1,2,3]; const arr2 = [4,5,6]; let newArr = arr1.concat(zero,arr1,arr2); console.log(newArr) // output:[1,2,3,0,4,5,6] 复制代码
concat方法可以向一个数组传递数组、对象或是元素。数组会按照该方法传入的参数顺序连接指定数组。
1.7.2 迭代器函数
我们可以用循环语句来处理，例如for语句。 JavaScript内置了许多数组可用的迭代方法。 例：我们需要一个函数和一个数组：如果数组里的元素可以被2整除，函数就返回true,否则返回false。
function isEven(x){ console.log(x); return x % 2 === 0 ? true : false } ES6写法： const isEven = x=>x%2 === 0; let newArr = [2,4,5,6,8] 复制代码
1.用every方法迭代
every方法会迭代数组中的每一个元素，直到返回false
newArr.every(isEven) 复制代码
数组newArr第3个元素为奇数，isEven函数返回false,然后every执行结束
2.用some方法迭代
它和every的行为相反，会迭代数组的每一个元素，直到函数返回true。
newArr.some(isEven) 复制代码
3.用forEach方法迭代
如果要迭代整个数组，可以用forEach方法。它和使用for循环的结果相同。
4.使用map和filter方法
JavaScript还有两个会返回新数组的迭代方法。
第一个是map方法。
const myMap = newArr.map(isEven); 复制代码
数组myMap里的值是[true,true,false,true,true]。 它保存了传入map方法的isEven函数的运行结果。这样就很容易知道一个元素是否是偶数。
第二个是filter方法。
它返回的新数组由使函数返回true的元素组成。
const myFilter = newArr.filter(isEven) output:[2,4,6,8] 复制代码
5. 使用reduce方法
reduce方法接受一个有如下四个参数的函数：previousValue、currentValue、index、array是可选的参数。因为index和array是可选的参数，所以有时可不传。这个函数会返回一个将被叠加到累加器的值， reduce方法停止执行后会返回这个累加器。
如果要对一个数组中的所有元素求和，这就很有用。
newArr.reduce((a,b)=>a+b); 复制代码
这三个方法（map.filter,reduce）是JavaScript函数式编程的基础
1.7.3 ES6中数组新增方法
除了这些新的方法，还有一种用for...of循环来迭代数组的新做法。
1. 使用for...of循环迭代
for(const n of newArr){ console.log(n%2 === 0 ? true : false) } 复制代码
2. 使用@@iterator对象
ES6还为Array类增加一个@@iterator属性，需要通过Symbol.iterator来访问。
let iterator = newArr[Symbol.iterator](); console.log(iterator.next().value);//2 console.log(iterator.next().value);//4 复制代码
iterator = newArr[Symbol.iterator](); for（const n of iterator）{ console.log(n) } 复制代码
3. 数组的entries、keys和values方法
ES6还增加了三种从数组中得到迭代器的方法。
entries方法
entries方法返回包含键值对的@@iterator
let myEntries = newArr.entries(); console.log(myEntries.next().value)//[0,2] console.log(myEntries.next().value)//[1,4] 复制代码
使用集合、字典、散列表等数据结构时，能够取出键值对是很有用的，这个功能会在后面的内容在大显身手。
keys方法
keys方法会返回包含数组索引的@@iterator
const myKeys = newArr.keys(); console.log(myKeys.next())//{value:0,done:false} console.log(myKeys.next())//{value:1,done:false} 复制代码
一旦没有可迭代的值，myKeys.next()就会返回一个value属性为undefined、done属性为true的对象。如果done属性的值为false,就意味着还有可迭代的值。
values方法
values方法返回的@@iterator则包含数组的值。
const myValues = newArr.values(); console.log(myValues.next()); console.log(myValues.next()); 复制代码
4.使用Array.from方法
Array.from方法根据已有的数组创建一个新的数组。
// 复制newArr数组 let newArr1 = Array.from(newArr) // 还可以传入一个过滤值的函数 let newArr2 = Array.from(newArr,x=>x % 2 == 0) 复制代码
5. 使用Array.of方法
Array.of方法会根据传入的参数创建一个新的数组
let arr1 = Array.of(1); let arr2 = Array.of(1,2,3，4，5，6); 复制代码
我们也可以用该方法复制已有数组
let newArr = Array.of(...arr2) 复制代码
效果和Array.from(arr2)的效果是一样的，不过这里使用了解构的方法。
6. 使用fill方法
fill方法用静态值填充数组
let newArr1 = newArr.fill(0)// 数组的所有值都变为0 let newArr2 = newArr.fill(0,1)// [1,2,3,4,5,6]变更为[1,0,0,0,0,0] let newArr3 = newArr.fill(0,3,5)// 把0填充到数组索引为3到5的位置（不包含3和5） 复制代码
创建数组并初始化值的时候，fill方法非常好用
// 创建一个长度为5值都为0的数组 let arr = Array(5).fill(0) 复制代码
7. 使用copyWithin方法
copyWithin方法复制数组中的一系列元素到同一数组指定的起始位置
let arr = [1,2,3,4,5,6]; // 把4，5，6复制到数组的前三个位置 arr.copyWithin(0,3); // 把4、5两个值复制到位置1，2 arr.copyWithin(1,3,5) 复制代码
1.7.4 排序元素
在JavaScript里提供了一个排序方法和一组搜索方法。
reverese方法反序输出数组
let arr = [1,2,3,4,5,6] arr.reverse() 复制代码
sort方法对数组做排序
sort方法在对数组做排序时，把元素默认为字符串进行相互比较。
我们可以传入自己写的比较函数arr.sort((a,b)=>a-b),这些就实现了对arr的升序排序。
1.自定义排序
我们也可以对任何对象类型的数组排序，可以创建compareFunction来比较元素。
const friends = [{name:'橙子',age:18},{name:'柚子',age:22},{name:'西瓜',age:17},]; function compareFunction(a,b){ if(a.age<b.age){ return 1 } if(a.age>b.age){ return -1 } return 0 } friends.sort(compareFunction) 复制代码
最后输出就会按年龄降序排序
2.字符串排序
let names = ['Ana','ana','john','John'] console.log(names.sort()) // output:['Ana','John','ana','john'] 复制代码
JavaScript在做字符比较的时候，是根据字符对应的ASCII值来比较的。 如果给sort传入一个忽略大小写的函数，这个时候sort函数不会有任何作用，它会按照现在的大小写字母顺序排序。
如果希望小写字母排在前面，那么需要使用localCompare方法。
names.sort((a,b)=>a.localCompare(b)) 复制代码
此外localCompare还可以对带有重音符号的字符做排序。
1.7.5 搜索
搜索有两种方法：
indexOf方法返回与参数匹配的第一个元素的索引。
lastIndexOf返回与参数匹配的最后一个元素的索引。
若没有找到则返回-1
1.ES6--find和findIndex方法
find和findIndex方法接受一个回调函数，搜索一个满足回调函数条件的值。
find方法返回第一个满足条件的值，findIndex方法则返回这个值在数组里的索引。如果没有满足条件的值，find会返回undefined,而findIndex返回-1。
2.ES7--使用includes方法
如果数组里存在某个元素，includes方法会返回true，否则返回false。
arr.includes(15) 复制代码
如果给includes方法传入一个起始索引，搜索会从索引指定的位置开始。
1.7.6 输出数组为字符串
toString()
如果想把数组里所有的元素输出为一个字符串，可以使用toString方法。
join()
如果想用一个不同的分割符把元素隔开，可以用join方法
const numberString = arr.join('-') console.log(numberString) // output：1-2-3-4-5-6 复制代码
二、栈
2.1 栈数据结构
栈是一种遵从后进先出原则的有序集合。
2.1.1 创建一个基于数组的栈
class Stack{ constructor() { this.items=[] } } 复制代码
由于栈遵循LIFO原则，需要对元素的插入和功能进行限制，接下来，要为栈声明一些方法。
2.1.2 向栈添加元素
push(element){ this.items.push(element) } 复制代码
2.1.3 从栈移除元素
pop(){ return this.items.pop(); } 复制代码
2.1.4 查看栈顶元素
peek(){ return this.items[this.items.length-1] } 复制代码
2.1.5 检查栈是否为空
isEmpty(){ return this.items.length === 0; } 复制代码
2.1.6 获取栈的长度
size(){ return this.items.length; } 复制代码
2.1.7 清空栈元素
clear(){ this.items=[]; } 复制代码
OK!栈已完成
2.2 创建一个基于JavaScript对象的类Stack
创建一个Stack类最简单的方式是使用一个数组来存储其元素。在使用数组时，大部分方法的时间复杂度是O(n)。如果数组有很多元素的话，所需的时间会更长。另外数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。如果我们能直接获取元素，占用较少的内存空间，并且仍然保证所有元素按照我们的需要排列，那不是更好吗？
我们可以使用一个JavaScript对象来存储所有的栈元素。
class Stack{ constructor() { this.count = 0; this.items = {}; } } 复制代码
在这个版本的Stack类中，我们将使用一个count属性来帮助我们记录栈的大小（也能帮助我们从数据结构中添加和删除元素）
2.2.1 向栈中插入元素
push(element) { this.items[this.count] = element; this.count++ } 复制代码
要向栈中添加元素，我们将使用count变量作为items对象的键名，插入的元素则是它的值。在向栈插入元素后，我们递增count变量。
2.2.2 验证一个栈是否为空和它的大小
size() { return this.count } isEmpty() { return this.count === 0 } 复制代码
2.2.3 从栈中弹出元素
由于我们没有用数组来存储元素，需要手动实现移除元素的逻辑。
首先，我们需要检验栈是否为空，如果为空，就返回undefined。
如果不为空，count--,保存栈顶元素，删除栈顶元素再返回栈顶元素。由于我们使用的是JavaScript对象，可以使用JavaScript的delete运算符从对象中删除一个特定的值
pop() { if (this.isEmpty()) { return undefined } this.count--; const result = this.items[this.count]; delete this.items[this.count]; return result; } 复制代码
2.2.4 查看栈顶元素和将栈清空
peek() { return this.items[this.count - 1] } clear() { this.items = {} this.count = 0 } 复制代码
2.2.5 创建toString方法
在数组版本中，我们不需要关心toString方法的实现，因为数据结构可以直接使用数组已经提供的toString方法。
对于使用对象的版本，我们将创建一个toString方法像数组一样打印出栈的内容。
toString() { if (this.isEmpty()) { return '' } let objString = `${this.items[0]}` for (let i = 1; i < this.count;i++ ){ objString=`${objString},${this.items[i]}` } return objString } 复制代码
实现了toString方法后，我们就完成这个版本的Stack类。
除了toString方法，我们创建的其他方法的复杂度均为O(1),代表我们可以直接找到目标元素对其进行操作（push、pop或peek）。
2.3 保护数据结构内部的数据
在创建别的开发者也可以使用的数据结构或对象时，我们希望保护内部的元素，只有我们暴露出的方法才能修改内部结构。不幸的是，我们在Stack类中的声明的items和count属性并没有得到保护，我们可以直接访问它们，
Object.getOwnPropertyNames(stack) Object.keys(stack)因为JavaScript的类就是这样工作的。
ES6类是基于原型的。尽管基于原型的类能节省内存空间并在扩展方面优于基于函数的类，但这种方式不能声明私有属性（变量）或方法。
下面来看看其他使用JavaScript来实现私有属性的方法。
2.3.1 下划线命名约定
class Stack{ constructor(){ this._count = 0; this._items = {}; } } 复制代码
不过这种方式只是一种约定，并不能保护数据。
2.3.2 用ES6的限定作用域Symbol实现类
ES6新增了一种叫作Symbol的基本类型，它是不可变的，可以用作对象的属性。
const _items = Symbol(); class Stack{ constructor() { this[_items] = []; } } 复制代码
这种方法创建了一个假的私有属性，因为ES6新增的Object.getOwnProperty-Symbol方法能够取到类里面声明的所有Symbol属性。
const stack = new Stack(); stack.push(5); stack.push(8); let objectSymbols = Object.getOwnPropertySymbols(stack); console.log(objectSymbols.length); console.log(objectSymbols); console.log(objectSymbols[0]); stack[objectSymbols[0]].push(1); console.log(stack); 复制代码
output: 1 [ Symbol() ] Symbol() Stack { [Symbol()]: [ 5, 8, 1 ] } 复制代码
我们可以进行任意的数组操作，但我们操作的是栈，不应该出现这种行为。
2.3.3 用ES2015的WeakMap实现类
用一种数据类型看可以确保属性是私有的，这就是WeakMap。WeakMap可以存储键值对，其中键是对象，值可以是任意数据类型。
const items = new WeakMap(); class Stack{ constructor() { items.set(this,[]) } push(element) { const s = items.get(this); s.push(element) } pop() { const r = items.get(this); r.pop() return r } } 复制代码
现在items在Stack类里是真正的私有属性，但是采用该方法，代码的可读性不高，而且在拓展该类时无法继承私有属性。
最后
⚽本文介绍了JavaScript数据结构中的数组及栈，相信你对它们又有了更深的理解~
⚾如果这篇文章对你有帮助的话，麻烦点赞收藏哟~
