栈数据结构
栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
Stack类的实现
一个栈应该具有这些方法：添加元素，移除元素，查看栈顶元素，检查栈是否为空，清空和打印栈元素。
ES5实现
function Stack() {
let items = [] // 使用数据来保存栈里的元素
this.push = function (element) { // 添加元素
items.push(element)
}
this.pop = function () { // 移除元素
return items.pop()
}
this.peek = function () { // 查看栈顶元素(最后一个元素)
return items[items.length - 1]
}
this.isEmpty = function () { // 检查栈是否为空
return items.length === 0
}
this.size = function () { // 查看栈的长度
return items.length
}
this.clear = function () { // 清空栈
items.length = 0
}
this.print = function () { //打印栈所有元素
console.log(items.toString())
}
this.toString = function () {
return items.toString()
}
}
let stack = new Stack()
stack.push(3)
stack.push(2)
stack.push(1)
stack.print() // 3,2,1
但这样写有一个明显的问题：实例的方法不能共享，每生成一个实例都要新创建这么多的方法 。
ES6实现
class Stack {
constructor() {
this.item = []
}
push(element) {
this.items.push(element)
}
pop() { // 移除元素
return this.items.pop()
}
peek() { // 查看栈顶元素(最后一个元素)
return this.items[items.length - 1]
}
isEmpty() { // 检查栈是否为空
return this.items.length === 0
}
size() { // 查看栈的长度
return this.items.length
}
clear() { // 清空栈
this.items.length = 0
}
print() { //打印栈所有元素
console.log(this.items.toString())
}
toString() {
return this.items.toString()
}
}
这样的优点是：实例的方法放到原型链上共享，可以有效节省内存。
缺点是：items不是私有属性，会被直接访问到，破坏了类的完整性。比如:
let stack=new Stack()
stack.items.push('4')
stack.print() // 3,2,1,4，这里没有调用实例的方法，却依然改变了这个实例
利用ES6提供的一些新特性，有下面解决方法。
一.用Symbol类型实现私有属性
let _items = Symbol()
class Stack {
constructor() {
this[_items] = []
}
// Stack方法
}
ES6新增了Object.getOwnPropertySymbols方法，能够取到类里面声明的所有Symbols属性，因此类依然会被破坏。
二.用ES6的WeakMap实现类
有一种数据类型可以确保属性是私有的，这就是WeakMap。WeakMap可以存储键值对，其中键是对象，值可以是任意数据类型。
const items = new WeakMap()
class Stack {
constructor() {
items.set(this, [])
}
push(element) {
let s = items.get(this)
s.push(element)
}
pop() {
let s = items.get(this)
let r = s.pop()
return r
}
// 其他方法
}
最后用闭包防止items被污染
let Stack = (function () {
const items = new WeakMap()
class Stack {
constructor() {
items.set(this, [])
}
// 其他方法
}
return Stack
})()
栈的应用
下面是使用栈的三个最著名的算法示例。
十进制转二进制
function divideBy2(decNumber) {
let remStack = new Stack(),
rem,
binaryString = ''
while (decNumber > 0) {
rem = Math.floor(decNumber % 2)
remStack.push(rem)
decNumber = Math.floor(decNumber / 2)
}
while (!remStack.isEmpty()) {
binaryString += remStack.pop().toString()
}
return binaryString
}
从二进制转换很容易抽象出任意进制转换。
function baseConverter(decNumber, base) {
let remStack = new Stack(),
rem,
baseString = '',
digits = '0123456789ABCDEF'
while (decNumber > 0) {
rem = Math.floor(decNumber % base)
remStack.push(rem)
decNumber = Math.floor(decNumber / base)
}
while (!remStack.isEmpty()) {
baseString += digits[remStack.pop()]
}
}
这里需要注意的是，16进制转换中，余数超过9的，将用字母ABCDEF代替。
平衡圆括号
平衡圆括号问题是指检查括号是否全部闭合（平衡）的算法。比如{{([][])}()}显然就不是平衡括号，{([])}是平衡括号。
function match(open, close) {
let opens = '([{',
closers = ')]}'
return opens.indexOf(open) === closers.indexOf(close)
}
function parenthesesChecker(symbols) {
let stack = new Stack(),
balanced = true
index = 0
symbols, top,
opens = '([{'
while (index < symbols.length && balanced) {
symbol = symbols[index]
if (opens.indexOf(symbol) > -1) {
stack.push(symbol)
} else {
top = stack.pop()
if (!match(top, symbol)) {
balanced = false
}
}
index++
}
if (balanced && stack.isEmpty()) {
return true
}
return false
}
console.log(parenthesesChecker('{{([][])}()}'))
console.log(parenthesesChecker('[{()]'))
汉诺塔
汉诺塔问题是指： 从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。
Tower_of_Hanoi.gif
算法思路：
- (1): 先将A柱的n-1个移动到B柱
- (2): 再将A柱的最后一个移动到C柱
- (3): 最后再将B柱的n-1个移动到C柱
然后运用递归，重复以上步骤。
let count = 0
function towerOfHanoi(n, from, to, helper) {
if (n > 0) {
towerOfHanoi(n - 1, from, helper, to)
to.push(from.pop())
count++
console.log('第'+count+'次')
console.log('Source: ' + from.toString());
console.log('Dest: ' + to.toString());
console.log('Helper: ' + helper.toString());
towerOfHanoi(n - 1, helper, to, from)
}
}
let source = new Stack()
source.push(3)
source.push(2)
source.push(1)
let dest = new Stack()
let helper = new Stack()
let n = source.size()
towerOfHanoi(n, source, dest, helper)
