栈
何为栈？栈是一种遵从后进先出（LIFO）原则的有序集合。
新添加或待删除的元素都保存在栈的同一端，称作栈顶；另一端就叫栈底。
在栈里，新元素都靠近栈顶，旧元素都接近栈底。
基于数组的栈
我们将创建一个基于数组的栈，了解栈的结构、运行规则
/** * 基于数组array的栈Stack * @author huxiaoshuai */ class Stack { // 初始化 constructor () { this.items = [] } }
使用数组保存栈里的元素
数组允许我们在任何位置添加和删除元素，那基于栈遵循LIFO原则，我们对元素的插入和删除功能进行封装
| 方法 | 描述 |
| push(element(s)) | 添加一个（或多个）新元素到栈顶 |
| pop() | 移除栈顶元素，同时返回被移除的元素 |
| peek() | 返回栈顶的元素，不对栈做任何修改 |
| isEmpty() | 判断栈是否为空，为空则返回true，否则返回false |
| clear() | 移除栈的所有元素 |
| size() | 返回栈的元素个数 |
代码实现
class Stack { // 初始化 constructor () { this.items = [] } /** * push() 添加元素到栈顶 */ push (element) { this.items.push(element) } /** * pop() 移除栈顶元素并返回 */ pop () { return this.items.pop() } /** * peek() 返回栈顶部元素 */ peek () { return this.items[this.items.length - 1] } /*** * isEmpty() 检测栈是否为空 */ isEmpty () { return this.items.length === 0 } /** * size() 返回栈的长度 */ size () { return this.items.length } /** * clear() 清空栈元素 */ clear () { this.items = [] } }
使用Stack类
const stack = new Stack() console.log(stack.isEmpty()) // true // 添加元素 stack.push(5) stack.push(8) // 输出元素 console.log(stack.peek()) // 8 stack.push(11) console.log(stack.size()) // 3 console.log(stack.isEmpty()) // false stack.push(15)
基于以上栈操作的示意图
stack.pop() stack.pop() console.log(stack.size()) // 2
基于以上栈操作的示意图
基于对象的栈
创建一个Stack类最简单的方式是使用一个数组来存储元素。在处理大量数据的时候，我们同样需要评估如何操作数据是最高效的。
使用数组时，大部分方法的时间复杂度是O(n)。简单理解：O(n)的意思为我们需要迭代整个数组直到找到要找的那个元素，在最坏的情况下需要迭代数组的所有位置，其中的n代表数组的长度。数组越长，所需时间会更长。另外，数组是元素的一个有序集合，为保证元素的有序排列，会占用更多的内存空间。
使用JavaScript对象来存储所有的栈元素，以实现可以直接获取元素，同时占用较少的内存空间，同时保证所有的元素按照我们的需要进行排列，遵循后进先出（LIFO）原则。
代码实现
/** * 基于对象的Stack类 * @author huxiaoshai */ class Stack { // 初始化 constructor () { this.items = {} this.count = 0 } /** * push() 向栈中添加元素 */ push (element) { this.items[this.count] = element this.count++ } /** * isEmpty() 判断是否为空 */ isEmpty () { return this.count === 0 } /** * size() 返回栈的长度 */ size () { return this.count } /** * pop() 栈顶移除元素并返回 */ pop () { if (this.isEmpty()) { return undefined } this.count-- let result = this.items[this.count] delete this.items[this.count] return result } /** * peek() 返回栈顶元素，如果为空则返回undefined */ peek () { if (this.isEmpty()) { return undefined } return this.items[this.count - 1] } /** * clear() 清空栈数据 */ clear () { this.items = {} this.count = 0 } /** * toString() 实现类似于数组结构打印栈内容 */ toString () { if (this.isEmpty()) { return '' } let objStr = `${this.items[0]}` for (let i = 1; i < this.count; i++) { objStr = `${objStr},${this.items[i]}` } return objStr } }
保护数据结构内部元素
私有属性
有时候我们需要创建供其他开发者使用的数据结构和对象时，我们希望保存内部元素，只有使用允许的方法才能修改内部结构。很不幸，目前JS是没有办法直接声明私有属性的，目前业内主要使用一下几种方式实现私有属性。
- 下划线命名约定
class Stack { constructor () { this._items = {} this._count = 0 } }
这只是约定，一种规范，并不能实际保护数据
- 基于ES6的限定作用域Symbol实现类
const _items = Symbol('stackItems') class Stack { constructor () { this[_items] = [] } }
假的私有属性，ES6新增的Object.getOwnPropertySymbols方法能够获取类里面声明的所有Symbols属性
- 基于ES6的WeakMap实现类
/** * 使用WeekMap实现类的私有属性 */ const items = new WeakMap() console.log(items) // WeakMap { [items unknown] } class Stack { constructor () { items.set(this, []) } push (element) { const s = items.get(this) s.push(element) } pop () { const s = items.get(this) const r = s.pop() return r } toString () { const s = items.get(this) return s.toString() } } const stack = new Stack() stack.push(1) stack.push(2) stack.push(3) console.log(stack.toString()) // 1,2,3 console.log(stack.items) // undefined
使用该方式，items是Stack类里的私有属性，但是此种方式代码的可读性不强，而且在扩展该类时无法继承私有属性。
- ECMAScript类属性提案
> 有一个关于JavaScript类中增加私有属性的提案。通过在属性前添加井号(#)作为前缀来声明私有属性。
class Stack { #count = 0 #items = [] }
使用栈来解决问题
栈的实际应用非常广泛。在回溯问题中，它可以存储访问过的任务或路径、撤销的操作（后续会在讨论图和回溯问题时进一步详细讲解）。栈的使用场景有很多，如汉诺塔问题、平衡圆括号、计算机科学问题：十进制转二进制问题
/** * decimalToBinary() 实现十进制转二进制的算法 */ 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 console.log(decimalToBinary(23)) // 10111
