第四章，栈
有时候还需要一种能在添加或删除元素时进行更多控制的数据结构。有两种类似于数组的数据结构在添加和删除元素时更为可控，它们就是栈和队列。
4.2 栈数据结构
栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
栈也被用在编程语言的编译器和内存中保存变量、方法调用等，也被用于浏览器历史记录（浏览器的返回按钮）。
class Stack {
constructor() {
this.items = []
}
// 向栈添加元素
push(element) {
this.items.push(element)
}
// 从栈移出元素
pop() {
return this.items.pop()
}
// 查看栈顶元素
peek() {
return this.items[this.items.length - 1]
}
// 检查栈是否为空
isEmpty() {
return this.items.length === 0
}
// 栈的length
size() {
return this.items.length
}
// 清空栈元素
clear() {
this.items = []
}
}
const stack = new Stack()
console.log(stack)
stack.push(5)
stack.push(8)
console.log(stack.peek())
stack.push(11);
console.log(stack.size())
console.log(stack.isEmpty())
stack.push(15)
stack.pop()
stack.pop()
console.log(stack.size())
console.log(stack)
4.3 创建一个基于 JavaScript 对象的 Stack 类
在使用数组时，大部分方法的时间复杂度是 O(n)。
O(n) 的意思是，我们需要迭代整个数组直到找到要找的那个元素，在最坏的情况下需要迭代数组的所有位置，其中的 n 代表数组的长度。如果数组有更多元素的话，所需的时间会更长。另外，数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。
class Stack {
constructor() {
this.count = 0
this.items = {}
}
// 向栈中添加元素
push(element) {
this.items[this.count] = element
// this.count = this.count + 1
// this.count += 1
this.count++
}
// 栈的大小
size() {
return this.count
}
// 栈是否为空
isEmpty() {
return this.count === 0
}
// 从栈中弹出元素
pop() {
if (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.items = {}
this.count = 0
// 遵循 LIFO 原则
// while (!this.isEmpty()) {
// this.pop()
// }
}
// 创建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
}
}
const stack = new Stack()
stack.push(5)
stack.push(8)
stack.push(10)
console.log(stack)
console.log(stack.toString())
除了 toString 方法，我们创建的其他方法的复杂度均为 O(1)，代表我们可以直接找到目标元素并对其进行操作（push、pop 或 peek）。
4.4 保护数据结构内部元素
在创建别的开发者也可以使用的数据结构或对象时，我们希望保护内部的元素，只有我们暴露出的方法才能修改内部结构。
本章使用 ES2015（ES6）语法创建了 Stack 类。ES2015 类是基于原型的。尽管基于原型的类能节省内存空间并在扩展方面优于基于函数的类，但这种方式不能声明私有属性（变量）或方法。另外，在本例中，我们希望 Stack 类的用户只能访问我们在类中暴露的方法。
4.4.1 下划线命名约定
4.4.2 用 ES2015 的限定作用域 Symbol 实现类
4.4.3 用 ES2015 的 WeakMap 实现类
4.4.4 ECMAScript 类属性提案
ES2022 正式为 class 添加了私有属性，方法是在属性名之前使用#表示。
4.5 用栈解决问题
栈的实际应用非常广泛。在回溯问题中，它可以存储访问过的任务或路径、撤销的操作。
本节，我们将介绍如何解决十进制转二进制问题，以及任意进制转换的算法。
要把十进制转化成二进制，我们可以将该十进制数除以 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)) // 1010
进制转换算法，我们可以修改之前的算法，使之能把十进制转换成基数为 2～36 的任意进制。除了把十进制数除以 2 转成二进制数，还可以传入其他任意进制的基数为参数。
function baseConverter(decNumber, base) {
const remStack = new Stack()
const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
let number = decNumber
let rem
let baseString = ''
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()) {
baseString += digits[remStack.pop()]
}
return baseString
}
console.log(baseConverter(100345, 16))