栈

• 什么是栈
• 栈的操作
• 实现一个栈类
• 栈的利用
• 栈属性私有化

什么是栈

堆栈是只能从列表的一端 (称为顶部) 拜访的元素列表. 一个常见的，现实生活中的例子就是自助餐厅的托盘堆. 托盘总是从顶部取走, 当托盘在荡涤后放回堆栈时，它们被搁置在堆栈的顶部. 堆栈被称为后进先出 (LIFO) 数据结构.

因为堆栈的后进先出个性, 以后不在栈顶都不能被拜访的. 如果想拜访栈底的元素必须把下面的元素移除(托盘取走)

栈是一品种队列的数据结构, 能够用解决许多计算问题. 同时栈是十分高效的一种数据结构，因数据新增、删除都只能从栈顶实现, 并且容易以及疾速实现.

栈操作

因为栈后入先出的个性，任何非栈顶元素不能被拜访. 要想拜访栈底的元素必须把下面的元素全副出栈能力拜访到.

上面栈的罕用的两个操作，元素入栈、出栈. 应用 push 操作将元素增加到堆栈中, 应用 pop 操作从堆栈中取出元素. 下图所示

堆栈另一个常见操作是查看堆栈顶部的元素. pop操作拜访堆栈的顶部元素，然而它将永恒地从堆栈中删除该元素. peek操作返回存储在堆栈顶部的值，而不从堆栈中删除它. 除 pop()、push()、peek() 次要办法外, 栈应该蕴含其它的如判断栈是不是空 isEmpty()、获取栈的大小 size()、清空栈 clear().
上面通过代码来实现一个栈.

栈的实现

通过数组来实现一个栈, 代码如下:

class Stack {constructor() {this.items = []
    }

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

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

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

    isEmpty() {return !!this.items.length}
    size() {return this.items.length}
    clear() {this.items = []
    }
    print(){return this.items.toString()
    }
}

上面通过一个案例来测试下定义栈类.

const stack = new Stack()
console.log(stack.isEmpty()) //=> true
stack.push(1) //=> 入栈 1
stack.push(2) //=> 入栈 2
stack.push(3) //=> 入栈 3

stack.pop()   //=> 出栈 3
stack.pop()   //=> 出栈 2

stack.push(4) //=> 入栈 4
console.log(stack.isEmpty()) //=> false
console.log(stack.size());   //=> 2
stack.clear();
console.log(stack.isEmpty()); //=> true

下面代码只是简略操作, 这里就不一一介绍了.

栈的利用

上面通过几个理论的例子来减少咱们对栈的了解：

进制转换

把一个数字从一个基数转为另外一个基数. 给定一个数字 n, 要把它转为基数b, 上面大略的步骤:

1. n % b 取余推入栈中
2. n / b 取模后的值替换 n 值
3. 反复步骤 1、2，直到 n = 0
4. 通过出栈操作获取转换后字符串

进制转换，通过栈非常容易实现，上面大略实现形式

function baseConverter(num, base) {const stack = new Stack()
    const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    if(!(base >= 2 && base <= 32)){return '';}
    do {stack.push(num % base)
        num = Math.floor(num / base)
    } while (num > 0)
    let converted = ''
    while (!stack.isEmpty()) {converted += digits[stack.pop()]
    }
    return converted;
}

上面咱们来测试下: 把一个数字转为二进制、八进制

let num = 32
let base = 2
let converted = baseConverter(num, base)
console.log(`${num} converted to base ${base} is ${converted}`)

num = 125
base = 8
converted = baseConverter(num, base)
console.log(`${num} converted to base ${base} is ${converted}`)

运行输入后后果为:

32 converted to base 2 is 100000
125 converted to base 8 is 175

回文

什么是回文:

回文是前后拼写雷同的单词、短语或数字。例如，“dad”是一个回文;“racecar”是一个回文; 1001 是一个数字回文;

咱们能够应用堆栈来确定给定的字符串是否是回文. 拿到

• 把字符串中的每个字符压入到栈中
• 通过 pop() 办法生成新的字符串
• 拿原字符串与新生成的字符串比拟，雷同则为“回文”

上面通过代码实现判断回文的办法:

function isPalindrome(word) {const stack = new Stack()
    for (let i = 0; i < word.length; i++) {stack.push(word[i])
    }
    let rword = ''
    while (!stack.isEmpty()) {rword += stack.pop()
    }
    return word === rword
}
console.log(isPalindrome('racecar')) // true
console.log(isPalindrome('hello'))   // false

留神
实现判断回文形式很多, 这里只是列举通过栈如何实现

用堆栈模仿递归过程

演示如何用堆栈实现递归，就以阶乘为例.

  5！= 5 * 4 * 3 * 2 * 1 = 120

先用递归办法实现, 具体如下：

function factorial(n) {if (n === 1) {return 1} else {return n * factorial(n-1)
    }
}

???? 应用堆栈模仿递归过程:

function fact(n) {const stack = new Stack()
    while (n > 1) {stack.push(n--)
    }

    let product = 1
    while (!stack.isEmpty()) {product *= stack.pop()
    }
    return product
}

栈属性私有化

私有化理论就是暗藏外部细节，只对外提供操作方法，这样能保障代码安全性. 上面罕用形式:

• 命名约定形式

class Stack {constructor() {this._items = []
    }
}

这种形式只是一种约定并不能起到爱护作用，而且只能依赖应用咱们代码的开发者所具备的常识.

• 借助 ES 模块作用域和 Symbol 属性

const _items = Symbol('stackItems')
class Stack {constructor() {this[_items] = []}
}
//...

}
这种形式其实创立一个假的公有属性, ES2015 新增的 Object.getOwnPropertySymbols 办法能取到类外面申明的所有 Symbol 属性, 上面是毁坏 Stack 类的例子

const stack = new Stack()\
stack.push(1)
stack.push(2)

let objectSymbols = Object.getOwnPropertySymbols(stack)
console.log(objectSymbols.length) // 1
console.log(objectSymbols) // [Symbol(stackItems) ]
console.log(stack[objectSymbols[0]].push(1))
console.log(stack.print()) // 1,2,1

• 利用 WeakMap 来实现是私有化

const items = new WeakMap()
class Stack {constructor() {items.set(this, [])
    }
    push(ele) {const s = items.get(this)
        s.push(ele)
    }
    pop() {const s = items.get(this)
        const r = s.pop()
        return r
    }
}

items 在 Stack 类里是真正的公有属性. 采纳这种形式带来问题代码可读性不强，而且扩大该类时无奈继承公有属性.

• ECMAScript 类属性提案

尽管在 TypeScrpit 中存在通过 private 修饰符来定义公有变量, 然而这只能编译时才无效，在编译后还是能够被内部拜访.

在 ES 草案中提供如下形式进行申明私有化属性

class Stack {#items = [];
    push(ele) {
        // 拜访
        this.#items.push(ele)
    }
}

具体