# 栈

# 背景

# 数组

数组(Array)是一种聚合数据类型，它可以将若干变量有序地组织在一起。数组还可以有一维、二维以及多维等表现形式。（在 JavaScript 或 TypeScript 有现有的数组，不用再自己实现）

# 线性表

线性表(LinearList)是一种具有线性结构的有限序列。也就是说它的数据元素都是首尾相接的，依次形成一对一的关系。（例如栈、队列、链表等都是线性结构。在这里也不去实现线性表了，后面会去实现栈、队列、链表等数据结构）

# 栈数据结构

栈(Stack)是一种遵从后进先出(LIFO)原则的受限线性表（受限表示对结点的操作受限制）。新添加或待删除的元素保存在栈的一端，这一端叫作栈顶；另一端是最先进入或者说最旧的元素，叫栈底。栈中没有数据时，称为空栈。
栈的例子有很多，例如一摞书、餐厅里的盘子、编译器和内存中保存的变量和方法等、浏览器历史记录。

# 基于数组的栈

基于数组的栈代码细节：stack-array.ts (opens new window)

    1.声明一个私有变量_items，类型为数组（用数组来保存栈里的元素，一维的数组也是线性结构特性），在下一节会介绍使用对象来保存栈（基于对象的栈）。
    2.栈的后进先出实现：用数组原生方法 push 和 pop。（在实现栈时你也可以只用数组的 unshift 和 shift 方法，只要保证在一端进行操作）
    3.再提供一些栈常用的方法，例如：
        peek 查看栈顶元素（相当于查看数组的最后一项）
        isEmpty 栈是否为空（相当于判断数组是否为空）
        size 栈的大小（相当于查看数组的大小）
        clear 清空栈（相当于把数组置空）
        toString 返回栈的字符串形式（返回数组的字符串形式）

# 基于对象的栈

基于对象的栈代码细节：stack-object.ts (opens new window)

在处理大量数据的时候，需要评估方法的时间复杂度。而使用数组时，大部分方法的时间复杂度是 O(n)。还有一点就是数组是元素的一个有序集合，要保证元素排列有序，它会占用更多的内存空间。
而对象的使用，可以根据属性名直接获取元素，占用的内存空间也较少，也能保证一定的顺序。

1.同样声明一个私有变量_items，但类型选用对象；再声明一个私有变量_count，用来记录栈的大小并且用来作为属性名。（用对象和 count 作为属性也能形成线性结构特性）

    2.栈的后进先出实现：
        入栈：_count 作为属性名将其添加到对象里，_count 也要更新值（_count ++）
        出栈：要删除对象最后一个属性（使用 delelte 运算符），并将_count 更新值（_count --）

3.栈其他常用方法同上一节类似，只有一个 toString 方法实现需要遍历对象得到每个元素再使用 toString 最后将这些字符串连接起来。

# 保护数据结构内部元素

我们实现的 Stack 中声明的私有属性其实并不是真正意义上的私有属性，在 js 层面上它是基于原型的类还是可以通过一定的方法（getOwnPropertyNames）改变它（其实 tslint 可以辅助开发者，提示他不要修改私有变量_items）。

1.下划线命名约定（上面用过）

2.使用 ES6 限定作用域 Symbol
（这个方法其实也不行，用 getOwnPropertySymbols 可以拿到私有属性）

const _items = Symbol("stackItems");
class Stack {
  constructor() {
    this[_items] = [];
  }
  // 每次操作时用this[_items]替换this._items
}

1
2
3
4
5
6
7

3.使用 ES6 的 WeakMap
（这个方法其实可以，就是可读性差了一些）

class Stack {
    private _items = new WeakMap();
    constructor() {
        this._items.set(this, []);
    }
    // 每次操作时需要this._items.get(this);
}

1
2
3
4
5
6
7

4.ECMAScript 类属性提案
（用#号作为前缀来声明私有属性，这是在 JavaScript 类中增加私有属性的提案，暂时使用不了）

class Stack {
  #count = 0;
  #items = {};
}

1
2
3
4

# 用栈解决问题

# 从十进制转换为二进制或任意进制

从十进制转换为二进制或任意进制代码细节：base-converter.ts (opens new window)

将十进制数除以 2，余数作为二进制的低位，保留商，再对商进行同样的操作（余数放到上一个位置稍高的位置）直到余数为 0。用栈的方式去存储的话，就是把每个余数推入栈里，最后从栈里取出每个数用字符串连起来就是二进制了。

# 平衡圆括号

平衡圆括号代码细节：balanced-symbols.ts (opens new window)

将字符串里的左括号存进栈结构里，遍历到右括号时与栈顶元素相匹配，栈为空或者匹配不成功就判为 false，否则遍历完所有都匹配就认为这是平衡的圆括号

# 汉诺塔

汉诺塔代码细节 (opens new window)

汉诺塔问题：

有三根柱子，第一根柱子放有从下往上按大小顺序摆放的圆盘，第二个柱子是临时存放点，第三根柱子是目的点。
需要把所有的圆盘从第一根柱子移动到第三根柱子，规定在小圆盘上不能放大圆盘并且在三根柱子之间一次只能移动一个圆盘。

思路：

假如有 n 个盘子，我们可以分解成三个大步骤：想办法将最上面的 n-1 个盘子放到临时点 b 处，然后将最底下的最大的盘子从源地点 a 移到目标地点 c 处，最后想办法将临时点 b 处的 n 个盘子移到目标地点 c 处。(用 3 个或者 4 个盘子移动可以验证)
仔细想一下，将最上面的 n-1 个盘子放到临时点 b 处是不是可以理解为，b 作为终点 c 作为临时点，n-1 个盘子根据汉诺塔规则从 a 移动到 b；而将临时点 b 处的 n 个盘子移到目标地点 c 处是不是可以理解为，b 作为源地点 a 作为临时点，n-1 个盘子根据汉诺塔规则从 b 移动到 c。
总的来说就是两个递归加一个 a 到 c 的移动

← 1.环境搭建 3.队列 →