JavaScript数据结构与算法——栈及其应用

1.使用ES6模拟栈的实现

let Stack = (function() {
  const items = new WeakMap();   // 放入WeakMap统一管理，避免外部直接修改数据
  class Stack {
    constructor() {
      items.set(this, [])
    }
    push(element) {
      items.get(this).push(element);
      return items.get(this);
    }

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

    isEmpty() {
      return items.get(this).length === 0;
    }

    size() {
      return items.get(this).length;
    }

    peer() {
      let s = items.get(this);
      return s[s.length - 1];
    }

    clear() {
      let s = items.get(this);
      items.set(this, []);
    }
    print() {
        console.log(this.toString());
    }

    toString() {
      return items.get(this).toString();
    }
  }
  return Stack;
})();

---

2.栈应用之进制转换

问题描述：将十进制转换为其他进制数据。

function baseConverter(decNumber, base){

    var 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()];
    }

    return baseString;
}

---

3.栈应用之括号匹配

问题描述：括号格式应该正确，不形成语法错误。

function isBracketBalanced(str) {
  let stack = new Stack(),
      i;
  if (!/^[(|)]*$/.test(str)) {
    throw new Error("the str can only contain '(' or ')'");
  }    // 若包含除括号以外的其他字符，则报错
  for (i = 0; i < str.length; i++) {
    if (str[i] === '(') {
      stack.push('(');
    } else {
      if (!stack.pop()) {
        return false;
      }
    }
  }
  return stack.isEmpty();
}

// test
var res = isBracketBalanced('(((()())(())))(');
console.log(res);

---

4.栈的应用之汉诺塔问题

问题描述：塔上有三根柱子和一套直径各不相同的空心圆盘，开始时源柱子上的所有圆盘都按从大到小的顺序排列。目标是通过每一次移动一个圆盘到另一根柱子上，最终把一堆圆盘移动到目标柱子上，过程中不允许把较大的圆盘放置在较小的圆盘上。

三个盘子时的移动过程：

N个盘子时，只能使用递归。思路如下图：

代码实现：

var towerOfHanoi = function(n, from, help, to) {
  if (n > 0) {
    towerOfHanoi(n-1, from, to, help);
    to.push(from.pop());
    console.log('----------------');
    from.print();
    help.print();
    to.print();
    towerOfHanoi(n-1, help, from, to);

  }
}

var a = new Stack(),
    b = new Stack(),
    c = new Stack(),
    n = 10;

for(let i = n; i > 0; i--) {
  a.push(i);
}
// test
towerOfHanoi(a.size(), a, b, c);