棧數(shù)據(jù)結(jié)構(gòu)

棧是一種遵從后進(jìn)先出（LIFO）原則的有序集合。新添加的或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。

Stack類的實(shí)現(xiàn)

一個(gè)棧應(yīng)該具有這些方法：添加元素，移除元素，查看棧頂元素，檢查棧是否為空，清空和打印棧元素。

ES5實(shí)現(xiàn)

function Stack() {
  let items = [] // 使用數(shù)據(jù)來保存棧里的元素

  this.push = function (element) { // 添加元素
    items.push(element)
  }

  this.pop = function () { // 移除元素
    return items.pop()
  }

  this.peek = function () { // 查看棧頂元素(最后一個(gè)元素)
    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

但這樣寫有一個(gè)明顯的問題：實(shí)例的方法不能共享，每生成一個(gè)實(shí)例都要新創(chuàng)建這么多的方法 。

ES6實(shí)現(xiàn)

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

  pop() { // 移除元素
    return this.items.pop()
  }

  peek() { // 查看棧頂元素(最后一個(gè)元素)
    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()
  }
}

這樣的優(yōu)點(diǎn)是：實(shí)例的方法放到原型鏈上共享，可以有效節(jié)省內(nèi)存。
缺點(diǎn)是：items不是私有屬性，會被直接訪問到，破壞了類的完整性。比如:

let stack=new Stack()
stack.items.push('4')
stack.print() // 3,2,1,4，這里沒有調(diào)用實(shí)例的方法，卻依然改變了這個(gè)實(shí)例

利用ES6提供的一些新特性，有下面解決方法。

一.用Symbol類型實(shí)現(xiàn)私有屬性

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

  // Stack方法
}

ES6新增了Object.getOwnPropertySymbols方法，能夠取到類里面聲明的所有Symbols屬性，因此類依然會被破壞。
二.用ES6的WeakMap實(shí)現(xiàn)類
有一種數(shù)據(jù)類型可以確保屬性是私有的，這就是WeakMap。WeakMap可以存儲鍵值對，其中鍵是對象，值可以是任意數(shù)據(jù)類型。

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
})()

棧的應(yīng)用

下面是使用棧的三個(gè)最著名的算法示例。

十進(jìn)制轉(zhuǎn)二進(jìn)制

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

}

從二進(jìn)制轉(zhuǎn)換很容易抽象出任意進(jìn)制轉(zhuǎn)換。

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進(jìn)制轉(zhuǎn)換中，余數(shù)超過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個(gè)圓盤，現(xiàn)要求將A柱子上的圓盤移到C柱子上去，期間只有一個(gè)原則：一次只能移到一個(gè)盤子且大盤子不能在小盤子上面，求移動(dòng)的步驟和移動(dòng)的次數(shù)。

Tower_of_Hanoi.gif

算法思路：

• (1): 先將A柱的n-1個(gè)移動(dòng)到B柱
• (2): 再將A柱的最后一個(gè)移動(dòng)到C柱
• (3): 最后再將B柱的n-1個(gè)移動(dòng)到C柱

然后運(yùn)用遞歸，重復(fù)以上步驟。

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)