栈

用 ES6 的 WeakMap 实 现 类

有 一 种 数 据 类 型 可 以 确 保 属 性 是 私 有 的， 这 就是 WeakMap。 我 们 会 在 后 面 深 入 探 讨 Map 这 种 数 据 结 构， 现 在 只 需 要 知 道 WeakMap 可 以 存 储 键 值 对， 其 中 键 是 对 象， 值 可 以 是 任 意 数 据 类 型。 如 果 用 WeakMap 来 存 储 items 变 量， Stack 类 就 是 这 样 的：

const items = new WeakMap(); //{1} 　
class Stack {
    constructor() {
        items.set(this, []); //{2} 
    }
    push(element) {
        let s = items.get(this); //{3} 
        s.push(element);
    }
    pop() {
        let s = items.get(this);
        let r = s.pop();
        return r;
    } // 其 他 方 法 
}

行{ 1}， 声 明 一 个 WeakMap 类 型 的 变 量 items。

行{ 2}， 在 constructor 中， 以 this（ Stack 类 自 己 的 引 用） 为 键， 把 代 表 栈 的

行{ 3}， 从 WeakMap 中 取 出 值， 即 以 this 为 键（ 行{ 2} 设 置 的） 从 items 中 取 值。

现 在 我 们 知 道， items 在 Stack 类 里 是 真 正 的 私 有 属 性 了， 但 还 有 一 件 事 要 做。 items 现 在 仍 然 是 在 Stack 类 以 外 声 明 的， 因 此 谁 都 可 以 改 动 它。 我 们 要 用 一 个 闭 包（ 外 层 函 数） 把 Stack 类 包 起 来， 这 样 就 只 能 在 这 个 函 数 里 访 问 WeakMap：

let Stack = (function () {
    const items = new WeakMap();
    class Stack {
        constructor() {
            items.set(this, []);
        } // 其 他 方 法 
    }
    return Stack; //{5} 
})();

当 Stack 函 数 里 的 构 造 函 数 被 调 用 时， 会 返 回 Stack 类 的 一 个 实 例（ 行{ 5}）。

栈 的 实 际 应 用 非 常 广 泛。 在 回 溯 问 题 中， 它 可 以 存 储 访 问 过 的 任 务 或 路 径、 撤 销 的 操 作（ 后 面 的 章 节 讨 论 图 和 回 溯 问 题 时， 我 们 会 学 习 如 何 应 用 这 个 例 子）。 Java 和 C# 用 栈 来 存 储 变 量 和 方 法 调 用， 特 别 是 处 理 递 归 算 法 时， 有 可 能 抛 出 一 个 栈 溢 出 异 常（ 后 面 的 章 节 也 会 介 绍）。 既 然 我 们 已 经 了 解 了 Stack 类 的 用 法， 不 妨 用 它 来 解 决 一 些 计 算 机 科 学 问 题。 本 节， 我 们 将 学 习 使 用 栈 的 三 个 最 著 名 的 算 法 示 例。 首 先 是 十 进 制 转 二 进 制 问 题， 以 及 任 意 进 制 转 换 的 算 法； 然 后 是 平 衡 圆 括 号 问 题； 最 后， 我 们 会 学 习 如 何 用 栈 解 决 汉 诺 塔 问 题。

从 十 进 制 到 二 进 制

现 实 生 活 中， 我 们 主 要 使 用 十 进 制。 但 在 计 算 科 学 中， 二 进 制 非 常 重 要， 因 为 计 算 机 里 的 所 有 内 容 都 是 用 二 进 制 数 字 表 示 的（ 0 和 1）。 没 有 十 进 制 和 二 进 制 相 互 转 化 的 能 力， 与 计 算 机 交 流 就 很 困 难。 要 把 十 进 制 转 化 成 二 进 制， 我 们 可 以 将 该 十 进 制 数 字 和 2 整 除（ 二 进 制 是 满 二 进 一）， 直 到 结 果 是 0 为 止。 举 个 例 子， 把 十 进 制 的 数 字 10 转 化 成 二 进 制 的 数 字， 过 程 大 概 是 这 样：

 

大 学 的 计 算 机 课 一 般 都 会 先 教 这 个 进 制 转 换。 下 面 是 对 应 的 算 法 描 述：

 1 function divideBy2(decNumber) {
 2     var remStack = new Stack(),
 3         rem, binaryString = '';
 4     while (decNumber > 0) { //{1} 
 5         rem = Math.floor(decNumber % 2); //{2} 
 6         remStack.push(rem); //{3} 
 7         decNumber = Math.floor(decNumber / 2); //{4} 
 8     }
 9     while (!remStack.isEmpty()) { //{5} 
10         binaryString += remStack.pop().toString();
11     }
12     return binaryString;
13 }

在 这 段 代 码 里， 当 结 果 满 足 和 2 做 整 除 的 条 件 时（ 行{ 1}）， 我 们 会 获 得 当 前 结 果 和 2 的 余 数， 放 到 栈 里（ 行{ 2}、{ 3}）。 然 后 让 结 果 和 2 做 整 除（ 行{ 4}）。 另 外 请 注 意： JavaScript 有 数 字 类 型， 但 是 它 不 会 区 分 究 竟 是 整 数 还 是 浮 点 数。 因 此， 要 使 用 Math.floor 函 数 让 除 法 的 操 作 仅 返 回 整 数 部 分。 最 后， 用 pop 方 法 把 栈 中 的 元 素 都 移 除， 把 出 栈 的 元 素 变 成 连 接 成 字 符 串（ 行{ 5}）。 用 刚 才 写 的 算 法 做 一 些 测 试， 使 用 以 下 代 码 把 结 果 输 出 到 控 制 台 里：

1 console.log(divideBy2(233));
2 console.log(divideBy2(10));
3 console.log(divideBy2(1000));

进 制 转 换 算 法

我 们 很 容 易 修 改 之 前 的 算 法， 使 之 能 把 十 进 制 转 换 成 任 何 进 制。 除 了 让 十 进 制 数 字 和 2 整 除 转 成 二 进 制 数， 还 可 以 传 入 其 他 任 意 进 制 的 基 数 为 参 数， 就 像 下 面 算 法 这 样：

 1 function baseConverter(decNumber, base) {
 2     var remStack = new Stack(),
 3         rem, baseString = '',
 4         digits = '0123456789ABCDEF'; //{6} 
 5     while (decNumber > 0) {
 6         rem = Math.floor(decNumber % base);
 7         remStack.push(rem);
 8         decNumber = Math.floor(decNumber / base);
 9     }
10     while (!remStack.isEmpty()) {
11         baseString += digits[remStack.pop()]; //{7} 
12     }
13     return baseString;
14 }

我 们 只 需 要 改 变 一 个 地 方。 在 将 十 进 制 转 成 二 进 制 时， 余 数 是 0 或 1； 在 将 十 进 制 转 成 八 进 制 时， 余 数 是 0 到 7 之 间 的 数； 但 是 将 十 进 制 转 成 16 进 制 时， 余 数 是 0 到 9 之 间 的 数 字 加 上 A、 B、 C、 D、 E 和 F（ 对 应 10、 11、 12、 13、 14 和 15）。 因 此， 我 们 需 要 对 栈 中 的 数 字 做 个 转 化 才 可 以（ 行{ 6} 和 行{ 7}）。

可 以 使 用 之 前 的 算 法， 输 出 结 果 如 下：

1 console.log(baseConverter(100345, 2));
2 console.log(baseConverter(100345, 8));
3 console.log(baseConverter(100345, 16));

 回文判断

//回文判断

function isPalindrome ( word ) {
    var s = new Stack();
    for( var i = 0 ; i < word.length ; i ++ ){
        s.push( word[i] );
    }
    var rword = '';
    while( s.length() > 0 ){
        rword += s.pop();
    }

    if( word == rword ){
        return true;
    }else{
        return false;
    }
}

console.log( isPalindrome('level') )    // true
console.log( isPalindrome('1001') )     // true
console.log( isPalindrome('word') )     // false