数据结构与算法---JS与栈

前言

js里，是没有栈这种原生的数据结构。但是我们可以通过自定义创建栈类，来实现对添加/删除元素时更多的控制。

创建栈类

// 初始化一个基于数组的栈类
class Stack {constructor() {this.items = [];}
}

为什么我们要选择数组作为栈类的存储数据类型？

因为栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称为栈顶，另外一端为栈底。在栈里，新元素越靠近栈顶，旧元素越靠近栈底。

栈的用途很广。被用于编程语言的编译器和内存中保存变量、方法调用等。也用于浏览器历史记录（浏览器的前进后退）

对栈的设想

由于栈遵循LIFO原则，不像数组可以随意对数组内的元素进行操作。所以需要对元素的插入和删除等功能做限制。接下来，我们为栈类设想一些方法。

• 添加一个（或几个）新元素到栈顶

push(ele) {this.items.push(ele)
}

• 移除栈顶的元素，同时返回被移除的元素

pop() {return this.items.pop();
}

• 返回栈顶的元素，不对栈做任何修改

peek() {return this.items[this.items.length-1]
}

• 如果栈为空则返回true 否则返回false

isEmpty()  {return this.items.length === 0;
}

• 移除栈内所有元素

clear() {this.items = [];
}

• 返回栈里的元素个数

size() {return this.items.length
}

实例化Stack类：

const stack = new Stack();
stack.isEmpty(); // true
stack.push(5);
stack.push(6);
stack.peek(); // 6

创建一个基于JS对象的Stack类

作用

我们上面创建的Stack类，是使用一个数组来存储数据。那么我们现在为什么要用JS对象来替换Stack类的存储方式?

因为在使用数组时，大部分方法的时间复杂度为O(n)。n代表数组长度。即在最坏的情况下，我们需要迭代整个数组直到找到我们要找的那个元素。

另外数组是元素的一个有序集合，为了保证元素排列有序，它需要占用更多的内存空间。

在大多数编程语言里，能够直接获取元素，占用较少的内存空间的存储方式，无非是键值表了。

所以我们要使用一个JS对象来存储所有的栈元素，并保证他们的顺序并且遵循LFO原则。

声明一个Stack类

class Stack {constructor() {// count是预先索引，可以代表长度，但是不存在索引为count的元素this.count = 0;this.items = {};}
}

为什么要定义count属性？为了记录栈的大小，并帮助我们添加或删除元素。

向栈中插入元素

要向栈中添加元素，我们将使用count变量作为items对象的键名，插入的元素则是它的值。在往栈插入元素后，我们递增count变量。

push(ele) {this.items[this.count] = ele;this.count ++;
}

实例化栈

const stack = new Stack();
stack.push(5)
stack.push(8)
stack; // {count: 2,items:{0:5,1:8} }

判断是否空栈和它的大小

size() {return this.count}
isEmpty() {return this.count === 0}

从栈中弹出元素（从弹夹弹出最顶上的一颗子弹）

pop() {// 空栈，弹出undefinedif (this.isEmpty()) {return undefined;}this.count --;const result = this.items[this.count]delete this.items[this.count]return result
}

查看栈顶的值

peek(){if (this.isEmpty()) {return undefined}return this.items[this.count - 1]
}

清空栈

方法①一键还原

clear() {this.count = 0;this.items = {};
}

方法②LIFO原则，循环出栈

clear() {while (!this.isEmpty()) {this.pop();}
}

toString

当我们使用数组作为数据结构的时候，不需要关心toString的实现、而对象需要我们自己去定义。

var a =['a','b',5]
a.toString() // 'a,b,5'

toString() {if (this.isEmpty()) {return ''};let objString = '';for (let i =0;i<this.count;i++) {objString+=(`[键名:${i}键值:${this.items[i]}]`)}return objString
}

时间复杂度

除了toString方法，我们创建的其他方法的复杂度均为O(1);代表我们可以直接找到目标元素并对其操作.

保护JS栈类内部的数据结构

在栈设计中，我们希望保护内部的元素。只有我们暴露出的方法才能修改内部结构。

比如在栈中，我们要确保元素只能被添加到栈顶。而不是任意位置。

也就是说，我们需要保护Stack类中声明的items和count属性。

上面的例子中，无论是以数组或者对象作为存储的数据类型。items和count都是Stack类暴露出来的公开属性。

破坏Stack类

为了方便理解，我们以数组作为Stack类的存储数据类型。

const stack = new Stack();
stack.push(5);
console.log(Object.getOwnPropertyNames(stack)); // ['items']
// 或者
console.log(Object.keys(stack)) // ['items']
// 直接破坏数据属性
stack['items'] = [1,2,3];

我们上面创建栈类是使用了ES6语法，是基于原型的类创建。这样做的好处在于能够节省内存空间并在扩展方面优于基于函数的类。但是这种方式不能声明私有属性的方法（直到ES11!）

保护内部属性-下划线命名约定

一部分开发者喜欢在js中使用下划线命名来约定这个属性为私有属性

class Stack {constructor() {this._items = {};this._count = 0;}   
}

但这只是为了规范开发时对类属性的保护，实际上并没有用处。

保护内部属性 - ES6的限定作用域Symbol

出发的思路点就是为了躲避Object.getOwnPropertyNames和Object.keys对stack实例的属性扫描。

Symbol是ES6新增的一种基本数据类型。它是不可变的。可以用作对象属性。

const _ItemKey = Symbol('dataStack')
class Stack {constructor() {this[_ItemKey] = []}
}
var stack1 = new Stack()
Object.keys(stack1) // []
Object.getOwnPropertyNames(stack1) // []

是不是找不到内部的_ItemKey属性了？

当你以为这样就可以成功躲避对象的属性扫描，那你就too young to simple啦

ES6新增的Object.getOwnProperty-Symbols方法能够拿到类里面声明的所有Symbols属性

Object.getOwnPropertySymbols(stack1) // [Symbol(stack01_item)]
stack1[Object.getOwnPropertySymbols(stack1)[0]] = [1,2,3]

保护内部属性 - ES6的WeakMap

有一种数据类型可以确保属性是私有的，这就是WeakMap。WeakMap以键值对存储数据。

const db = new WeakMap()
class Stack {constructor() {db.set(this,[])}push(t) {const items = db.get(this);items.push(t)}pop() {const items = db.get(this);return items.pop()}
}
const stack2 = new Stack()
stack2.push(5)
stack2.push(10)
stack2 // {}
stack2.pop() // 10
Object.keys(stack2) // []
Object.getOwnPropertyNames(stack2) // []

this是吧Stack类自己的引用作为键，存入WeakMap数据表里。

这样子确实是无懈可击了，Stack类里终于有了自己的私有属性。但是采用这种方法，会让代码变得难以理解，并且在继承扩展类时无法继承私有属性！

所以不推荐！

保护内部属性 - ES11的#变量

ES11（ES2020）在类中新增私有变量控制符#，在内部变量或者函数前添加一个hash符号#，可以将它们设置为私有属性，只能在类的内部可以使用。

class Stack {#items = {};#count = 0push(t) {this.#items[this.#count] = tthis.#count ++;}
}
const stack3 = new Stack()
stack3.push('ddd')
stack3.items; // undefined
stack3.#items // Uncaught SyntaxError: Private field '#items' must be declared in an enclosing class
Object.keys(stack3) // []

用栈解决问题

栈可以解决很多计算机科学问题。

从十进制到二进制

在日常生活中，我们主要使用十进制，在计算机科学中，二进制非常重要。因为计算机的所有内容都是用二进制数字表示的（0和1）

我们要利用栈来强化JS把十进制转换成二进制的能力。

规则：

要把十进制转成二进制。我们可以用十进制数除以2（二进制是满二进一）并对商取整。直到结果是0为止。

我们现在把10转成二进制数字：

const decimalToBinary = (decNumber) => {const remStack = new Stack();let binaryString = '';// 避免方法改变传入的十进制值let cloneDecNumber = decNumber;while (cloneDecNumber > 0) {// 把余数存进去remStack.push(cloneDecNumber % 2);cloneDecNumber= Math.floor(cloneDecNumber /2);}// 取值while (!remStack.isEmpty()) {binaryString += remStack.pop().toString();}return binaryString
}

decimalToBinary(233) // '11101001'
decimalToBinary(10) // '1010'
decimalToBinary(1000) // '1111101000'
decimalToBinary(100) // '1100100'

进制转换算法

我们修改之前的算法。使它能够把十进制转换成基数为2-6的任意进制。

const baseConverter = (decNumber,base) => {const remStack = new Stack();let number = decNumber;let rem;let baseString = '';if (base <2 || base>36) {return ''}while (number > 0) {remStack.push(Math.floor(number % base))number = Math.floor(number / base)}// digits是参照表const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'while (!remStack.isEmpty()) {baseString += digits[remStack.pop()];}return baseString
}

十进制转二进制，余数是0或1

十进制转为八进制，余数是0-7

十进制转十六进制时，余数是0-15（16-1），但是计算机语言里没有所谓的15，而是用A、B、C、D、E、F分别对应10、11、12、13、14、15

因此我们需要对栈中的数字做转化

从十一进制起，字母表中的每个字母代表对应的基数。

baseConverter (100345,2)
//'11000011111111001'
baseConverter (100345,8)
//'303771'
baseConverter (100345,35)
//'2BW0'
baseConverter (100345,16)
//'187F9'