JavaScript 数据结构与算法1(数组与栈)

技术分享 2年前 (2022-05-05) 0 999+

学习数据结构的 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));