学习数据结构的 git 代码地址: https://gitee.com/zhangning187/js-data-structure-study
1、数组
几乎所有的语言都原生支持数组类型,因为数组是最简单的内存数据结构。该章节深入学习数组数据结构和它的能力。
1.1 数组添加元素
初始化一个数组
let numbers = [0, 1, 2, 3, 4, 5, 6];
数组尾部插入元素,只要把值赋给数组中最后一个空位上的元素即可
numbers[numbers.length] = 7;
在 JavaScript 中元素是一个可以修改的对象,如果添加元素他就会动态增长。在别的语言里面要决定数组的大小,如果添加新的元素就要创建一个全新的数组,不能简单地添加所需的元素。
使用 push 添加数组元素
numbers.push(8); numbers.push(9, 10);// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
1.1.1 数组开头插入元素
实现这个需求,要腾出数组里第一个元素的位置,把所有的元素向右移动一位。
Array.prototype.insertFirstIndex = function (value) { for (let i = this.length; i >= 0; i--) { this[i] = this[i - 1]; } this[0] = value; };
在 JavaScript 里操作数组有个方法 unshift ,可以直接在数值插入数组的开头,该方法逻辑和 insertFirstPosition 方法得方式是一致的。
1.2 删除元素
1.2.1 从数组末尾删除元素
numbers.pop();
通过 push 和 pop 方法,就能用数组来模拟栈。
1.2.2 从数组开头删除元素
Array.prototype.removeFirst = function () { for (let i = 0; i < numbers.length; i++) { numbers[i] = numbers[i + 1]; } // 过滤掉最后一个 undefined numbers = this.reIndex(this); return numbers; }; Array.prototype.reIndex = function (arr) { const newArr = []; for (let i = 0; i < arr.length; i++) { if (typeof arr[i] !== 'undefined') { newArr.push(arr[i]); } } return newArr; };
这里所有的元素都左移了一位,但是长度没有改变,还要主动把数组最后一个元素 undefined 删除掉。
js 操作数组有一个 shift 方法,就是用来删除数组得第一个元素。
通过 shift 和 unshift 方法,我们就能用数组模拟基本的队列数据结构。
在 js 中,还可以使用 delete 运算符删除数组中得元素,例如 delete numbers[0] 。然而位置 0 得值会变成 undefined,等同于 numbers[0] = undefined。因此在操作数组得时候始终要使用 splice、pop、shift 方法来删除数组元素。
这里了解下常用的数据结构:数组,便于后面学习别的数据结构的时候做对比。
2、栈
在了解了最常用的数据结构–数组之后,我们知道数组可以在任意位置上删除或添加元素。有时候还需要一种能在添加或删除元素时进行更多控制的数据结构。有两种类似于数组的数据结构在添加或删除时更为可控,就是栈和队列。
2.1 栈数据结构
栈是一种遵从后进先出(LIFO)原则的有序集合。新添加或待删除的元素都保存在栈的同一端,称为栈顶,另一端叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。
index.js
// 创建类表示栈 class IndexStack { constructor() { // 我们需要一种数据结构来保存栈里的元素。可以选择数组来实现。 this.item = []; } }
实现下面几个栈的方法
- push(element(s)): 添加一个或几个新元素到栈顶
- pop(): 移除栈顶元素,同时返回被移除的元素
- peek(): 返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它)
- isEmpty(): 栈里面是否有元素
- clear(): 移除栈里的所有元素
- size(): 返回栈里的元素个数
2.1.1 向栈里添加元素
使用数组的 push 方法模拟栈添加新元素
// 栈里面添加元素 push(element) { this.item.push(element); }
2.1.2 从栈移除元素
// 从栈移除元素 pop() { this.items.pop(); }
2.1.3 查看栈顶元素
// 查看栈顶元素 peek() { return this.items[this.items.length - 1]; }
2.1.4 检查栈是否为空
// 检查栈是否为空 isEmpty() { return this.items.length === 0; }
2.1.5 清空栈元素
// 清空栈元素 clear() { this.items = []; }
2.2 创建一个基于 JavaScript 对象的 Stack 类
2.1 中创建 Stack 类使用数组的方式来存储其元素,在处理大量数据的时候,我们同样需要评估如何操作数据是最高效的。在使用数组时,大部分方法的时间复杂度时O(n),意思时 我们需要迭代整个数组直到找到要找的那个元素,在最坏的情况下需要迭代数组的所有位置,其中的 n 代表数组的长度。如果数组有更多的元素则所需的时间会更长。另外,数组是元素的一个有序集合,为了保证元素排列有序,它会占用更多的内存空间。
如果可以直接获取元素,占用较少的内存空间,并且保证所有元素按照我们的需要进行排列不是更好么。下面使用 JavaScript 语言实现栈数据结构的场景,使用 JavaScript 对象来存储所有的栈元素,保证它们的顺序并且遵循 LIFO 原则。
2.2.1 使用 JavaScript 对象来存储所有的栈元素
class Stack { constructor() { // 在这个 Stack 类中,使用 count 属性来帮我们记录栈的大小 // (也能帮我们从数据结构中添加或删除元素) this.count = 0; this.items = {}; } }
2.2.2 向栈中插入元素
该 push 方法只允许我们一次插入一个元素
push(element) { // 在 JavaScript 中对象是一系键值对的集合。 // 要向栈中添加元素,使用 count 作为 items 对象的键名,插入的元素则是它的值。 this.items[this.count] = element; this.count++; } const stack = new Stack(); stack.push(111); stack.push(222); // items = {0: 111, 1: 222}; count = 2;
2.2.3 验证栈是否为空和它的大小
size() { return this.count; } isEmpty() { return this.count === 0; }
2.2.4 从栈中弹出元素
// 从栈中弹出元素 pop() { if (this.isEmpty()) { return undefined; } this.count--; const result = this.items[this.count]; delete this.items[this.count]; return result; }
2.2.5 查看栈顶的值、清空栈
// 查看栈顶的值 peek() { if (this.isEmpty()) { return undefined; } return this.items[this.count - 1]; } clear() { this.items = {}; this.count = 0; }
2.2.6 toString 方法
toString() { if (this.isEmpty()) { return ''; } let stackString = `${this.items[0]}`; for (let i = 1; i < this.count; i++) { stackString += `,${this.items[i]}`; } return stackString; }
以上除了 toString 方法,我们创建的其他方法的复杂度均为 O(1),代表我们直接找到目标元素并对其进行操作(push、pop、peek)。
2.3 保护数据结构内部元素
在创建公用的数据结构或对象时,我们希望保护内部的元素,只有我们暴露出的方法才能修改内部结构。对于 Stack 类来说,要确保元素只会被添加到栈顶,而不是其他位置。
2.2 中声明的 Stack 类的 items 和 count 属性并没有得到保护,因为 JavaScript 类就是这样工作的。
const stack = new Stack(); // getOwnPropertyNames 方法返回一个由指定对象的所有自身属性的属性名 // (包括不可枚举属性但不包括Symbol值作为名称的属性)组成的数组 console.log(Object.getOwnPropertyNames(stack));// 1 console.log(Object.keys(stack));// 2 console.log(stack.items);// 3
1 和 2 行输出结果为 [‘count’, ‘items’]。这表示 count 和 items 属性是公开的,我们可以像 3 行那样直接访问它们。根据这种行为,我们可以对这两个属性赋新的值。
这里使用 ES6 语法创建的 Stack 类。ES6 类是基于原型的,尽管基于原型的类能节省内存空间并在扩展方便优于基于函数的类,但这种方式不能声明私有属性(变量)或方法。这里我们希望 Stack 类的用户只能访问我们在类中暴露的方法。下面学习其他使用 JavaScript 来实现私有属性的方法。
2.3.1 下划线命名约定
一部分开发者喜欢在 JavaScript 中使用下划线命名约定来标记一个属性为私有属性。
// class Stack { constructor() { this._count = 0; this._items = {}; } }
下划线命名约定就是在属性名称之前加上一个下划线_。不过这种方式只是一种约定,并不能保护数据,而且只能依赖于使用我们代码的开发者所具备的常识。
2.3.2 使用 ES6 的限定作用域 Symbol 实现类
const _items = Symbol('stackItems'); class Stack2 { constructor() { this.count = 0; this[_items] = []; } push(element) { this[_items][this.count] = element; this.count++; } } // 上面这种方法创建了一个假的私有属性, // 因为 es6 新增的 Object.getOwnPropertySymbols 方法能够取到类里面声明的所有 Symbols 属性。 // 以下是 破坏 Stack2 类的示例 const stack2 = new Stack2(); stack2.push(1); stack2.push(2); let objectSymbols = Object.getOwnPropertySymbols(stack2); console.log(objectSymbols.length);// 1 console.log(objectSymbols);// [Symbol(stackItems)] console.log(objectSymbols[0]);// Symbol(stackItems) stack2[objectSymbols[0]].push(1); console.log(stack2);
上面代码说明 stack2[objectSymbols[0]] 是可以得到 _items 的。并且 _items 属性是一个数组,可以进行任意的数组操作,比如从中间删除或添加元素(使用对象进行存储也是一样的)。但是我们操作的是栈,不应该出现这种行为。所以这种方式也是不可取的。
2.3.3 使用 ES2015 的 WeakMap 实现类
有一种数据类型可以确保属性是私有的,这就是 WeakMap 。后面会在 第8章深入探讨 Map 这种数据结构,现在只需要知道 WeakMap 可以存储键值对,其中键是对象,值可以是任意数据类型。
// 声明 WeakMap 类型的变量 item3 const items3 = new WeakMap(); class Stack3 { constructor() { // 这里以 this 为键,把代表栈的数组存入 items items3.set(this, []); } push(element) { // 从 WeakMap 中取出值,以 this 为键从 items3 中取值。 const s = items3.get(this); s.push(element); } pop() { const s = items3.get(this); const r = s.pop(); return r; } }
以上 items3 在 Stack3 类里是真正的私有属性。(利用 weakMap 来实现私有化)采用这种方法,代码的可读性不强,而且在扩展该类时无法继承私有属性。鱼和熊掌不可兼得。
2.3.4 ES 类属性提案
TS 提供了一个给类属性和方法使用的 private 修饰符。然而该修饰符只在编译时有用,在代码转移之后属性同样是公开的。
事实上 JS 不能像其他语言一样声明私有属性和方法。虽然有很多方法都可以达到相同的效果,但无论是在语法还是性能层面,这些方法都有自己的优缺点。具体使用哪种方式来处理构造的数据结构,以及其他约束条件取决于我们自己的决定。
有一个关于 JavaScript 类中增加私有属性的提案。以后可以通过该提案,可以直接在类中声明 js 类属性并进行初始化。
class Stack { // 可以通过 # 作为前缀来声明私有属性,这种行为和 WeakMpa 中的私有属性很相似。应该在不久的将来就能实现 #count = 0; #items = {}; }
2.4 用栈解决问题
栈的应用非常多。在回溯问题中,可以存储访问过的任务或路径、撤销的操作等。
下面学习下如何解决十进制转二进制问题,以及任意进制转换的算法。
2.4.1 从十进制到二进制
通常我们主要使用十进制。在计算机领域二进制非常重要,因为计算机里的所有内容都是用二进制数字表示(0 和 1)。
要把十进制转化成二进制,我们可以将该十进制数除以 2 (二进制是满二进一)并对商进行取整,知道结果是 0 为止。
// 十进制转二进制 function decimalToBinary(decNumber) { const remStack = new Stack(); let number = decNumber; // 余数 let rem; let binaryString = ''; while (number > 0) { rem = Math.floor(number % 2); remStack.push(rem); number = Math.floor(number / 2); } // 依次出栈 while (!remStack.isEmpty()){ binaryString += remStack.pop().toString(); } return binaryString; } console.log(decimalToBinary(10));
2.4.2 进制转换算法
修改上面写的算法使之从十进制能转换为 2-36 的任意进制。
// 十进制转任意进制 function baseConverter(decNumber, base) { const remStack = new Stack(); // 余数为 0-9 加上 A-Z ,A 对应 10 B 对应 11 ,往后依次累加 const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'; let number = decNumber; // 余数 let rem; let binaryString = ''; if (!(base >= 2 && base <= 36)) { return ''; } while (number > 0) { rem = Math.floor(number % base); remStack.push(rem); number = Math.floor(number / base); } // 依次出栈 while (!remStack.isEmpty()) { binaryString += digits[remStack.pop()]; } return binaryString; } console.log(baseConverter(12345, 2)); console.log(baseConverter(12345, 8)); console.log(baseConverter(12345, 16));
2.5 小结
本章学习数据结构中栈相关知识点。分别使用了数组和 JavaScript 对象自己实现了栈,还讲解了如何用 push 和 pop 往栈里添加和移除元素。
后面学习队列,它和栈有很多相似之处,但有个重要区别,队列中的元素不遵循后进先出(LIFO)原则。