爱囡囡，爱前端

0%

TypeScript数据结构与算法：栈

发表于 分类于 ， ，

《学习 JavaScript 数据结构与算法》的地铁读书计划已经读到了图的深度优先遍历部分，现在边学边复习，用刚学的 TypeScript 重新捋一下每种数据结构的源代码。源代码参考自作者的Github 仓库。

栈 （Stack）是一种遵从 后进先出（Last In First Out，LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作 栈顶 ，另一端就叫 栈底 。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

数据结构

一个栈应有几个操作方法如下：

  • push(element)：入栈，添加新元素到栈顶。
  • pop()：出栈，移除栈顶的元素，同时返回被移除的元素。
  • peek()：返回栈顶的元素，不对栈做任何修改。
  • isEmpty()：栈是否为空。
  • clear()：移除栈里的所有元素。
  • size()：返回栈里的元素个数。
  • toString(): 覆盖 Object 默认的 toString 方法

数组实现

栈其实很类似一个功能不全的数组，只能从单端进出。所以用 Array 来实现栈数据结构是最简单的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
export default class StackArray<T> {
  // 存储的Array
  private items: T[];

  constructor() {
    this.items = [];
  }

  /**
   * @description: 入栈
   * @param {T} element 要入栈的元素
   */
  push(element: T) {
    this.items.push(element);
  }

  /**
   * @description: 出栈
   * @return {T} 返回出栈的元素
   */
  pop(): T {
    return this.items.pop();
  }

  /**
   * @description: 返回栈顶的元素
   * @return {T}
   */
  peek(): T {
    return this.items[this.items.length - 1];
  }

  /**
   * @description: 返回栈是否为空
   * @return {Boolean}
   */
  isEmpty(): boolean {
    return this.items.length === 0;
  }

  /**
   * @description: 返回栈里的元素个数
   * @return {Number}
   */
  size(): number {
    return this.items.length;
  }

  /**
   * @description: 清空栈
   */
  clear() {
    this.items = [];
  }

  /**
   * @description: 覆盖Object默认的toString
   * @return {String}
   */
  toString(): string {
    return this.items.toString();
  }
}

Map 实现

在使用数组时，大部分方法的时间复杂度是 O(n)。找寻某个元素时，在最坏的情况下需要迭代数组的所有位置，所以如果直接使用字典 Map 来存储所有的栈元素能获得更好的性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
export default class Stack<T> {
  // 存储的Map
  private items: Map<number, T>;

  //
  constructor() {
    this.items = new Map();
  }

  /**
   * @description: 入栈
   * @param {T} element 要入栈的元素
   */
  push(element: T) {
    this.items.set(this.items.size, element);
  }

  /**
   * @description: 出栈
   * @return {T} 返回出栈的元素
   */
  pop(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items.get(this.items.size - 1);
    this.items.delete(this.items.size - 1);
    return result;
  }

  /**
   * @description: 返回栈顶的元素
   * @return {T}
   */
  peek(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.get(this.items.size - 1);
  }

  /**
   * @description: 返回栈是否为空
   * @return {Boolean}
   */
  isEmpty(): boolean {
    return this.items.size === 0;
  }

  /**
   * @description: 返回栈里的元素个数
   * @return {Number}
   */
  size(): number {
    return this.items.size;
  }

  /**
   * @description: 清空栈
   */
  clear() {
    this.items.clear();
  }

  /**
   * @description: 覆盖Object默认的toString
   * @return {String}
   */
  toString(): string {
    if (this.isEmpty()) {
      return '';
    }
    let result: string = '';
    this.items.forEach((value, key) => {
      result = `${result}${key === 0 ? '' : ', '}${value}`;
    });
    return result;
  }
}

相关算法

栈的实际应用非常广泛。比如在 Javascript 运行时，就是用栈来存储变量和方法调用，每次调试和报错时，都可以看到这个调用栈。下面用栈来实现两个经典的算法。

进制转换

要把十进制转化成 N 进制，我们可以将该十进制数除以 N（N 进制是满 N 进一）并对商取整，直到结果是 0 为止。举个例子，把十进制的数 8039 转化成 N 进制的数字，过程算法如下所示：

10 to 16

所以可以用栈来存储余数，余数每个入栈，提取结果时余数挨个出栈，转换成算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * @description: 将十进制数字转换为对应进制
 * @param {Number} decNumber 要转换的数字
 * @param {Number} base 要转换的进制
 * @return {String} 返回base进制的数字文本
 */
function baseConverter(decNumber: number, base: number): string {
  // 余数栈
  const remStack = new Stack<number>();
  // 10个数字 + 26个英文字母，最高能表示 36 进制
  const digits: string = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  let rem: number;
  let baseString: string = '';

  if (!(2 <= base && base <= 36)) {
    return '';
  }

  // 普通的计算进制算法
  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;
}

测试下：

1
2
3
4
console.log(baseConverter(8039, 32)); // output =>  7R7
console.log(baseConverter(8039, 16)); // output =>  1F67
console.log(baseConverter(8039, 8)); // output => 17547
console.log(baseConverter(8039, 2)); // output => 1111101100111

汉诺塔

汉诺塔（Tower of Hanoi）源于印度传说中，大梵天创造世界时造了三根金刚石柱子，其中一根柱子自底向上叠着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。根据这个传说抽象的数学问题：

有三根杆子 A，B，C。A 杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

  • 每次只能移动一个圆盘；
  • 大盘不能叠在小盘上面；

如何移？最少要移动多少次？这里的算法在在知乎上看到了几个精彩的回答：如何理解汉诺塔的递归？。总的来说，就是利用数学归纳法，如下图所示，把算法分为四步：

首先看 b 图状态，该状态中最大的盘子在起始塔上，比它小的所有的盘子在辅助塔上。当前应该做的就是把最大的盘子从起始塔挪到目标塔，所以:

  • 在执行该步骤之前，要做的就是把比它小的所有的盘子从起始塔挪到辅助塔；
  • 在执行该步骤之后，要做的就是把比它小的所有的盘子从辅助塔挪到目标塔；

所以就形成了递归，每根塔都是只能从最上面挪入和挪出，所以可以用栈来完美的抽象表示，算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import Stack from '../data-structures/stack';
// 汉诺塔的每根塔的格式定义{name: string, stack: Stack}
interface Tower {
  name: string;
  stack: Stack<number>;
}

// 移动步骤数组的格式定义[Map<towerName:string, plates:string>]
type Moves = Array<Map<string, string>>;

/**
 * @description: 移动盘子递归方法
 * @param {number} plates 需移动的盘子数
 * @param {Tower} source 该次移动的起始塔
 * @param {Tower} helper 该次移动的辅助塔
 * @param {Tower} dest 该次移动的终点塔
 * @param {Moves} moves 截止至上一次移动的步骤数组
 * @return {Moves} 返回本次移动后步骤数组
 */
const hanoiStackRecur = (
  plates: number,
  source: Tower,
  helper: Tower,
  dest: Tower,
  moves: Moves = []
): Moves => {
  // 边角情况处理
  if (plates <= 0) {
    return moves;
  }
  // 基线条件
  if (plates === 1) {
    // 不管是第一步还是最后一步，都只是简单的把最小的盘子从当前回合的起始塔转移到目标塔而已
    dest.stack.push(source.stack.pop());
    const move = new Map<string, string>();
    move.set(source.name, source.stack.toString());
    move.set(helper.name, helper.stack.toString());
    move.set(dest.name, dest.stack.toString());
    moves.push(move);
  } else {
    /**
     * 首先记住，本回合初始状态如下：
     * 起始塔：第 plates 个盘子
     * 辅助塔：前 1 到 plates-1 个盘子
     * 目标塔：没有小于等于 plates 的盘子
     */
    // 本回合之前的任务：把前 1 到 plates-1 个盘子从起始塔挪到辅助塔
    hanoiStackRecur(plates - 1, source, dest, helper, moves);
    // 本回合任务：将当前最大的盘子从本回合的起始塔挪到本回合的目标塔
    dest.stack.push(source.stack.pop());
    // 👇 单纯的记录步骤，给步骤数组添加当前步骤
    const move = new Map<string, string>();
    move.set(source.name, source.stack.toString());
    move.set(helper.name, helper.stack.toString());
    move.set(dest.name, dest.stack.toString());
    moves.push(move);
    // 👆
    // 本回合之后的任务：将前 1 到 plates-1 个盘子从辅助塔挪到目标塔
    hanoiStackRecur(plates - 1, helper, source, dest, moves);
  }
  return moves;
};

/**
 * @description: 汉诺塔算法
 * @param {number} plates 需移动的盘子数
 * @return {Moves} 返回所有的移动步骤数组
 */
export function hanoiStack(plates: number): Moves {
  // 初始化起始塔、辅助塔和终点塔
  const source: Tower = { name: 'source', stack: new Stack<number>() };
  const dest: Tower = { name: 'dest', stack: new Stack<number>() };
  const helper: Tower = { name: 'helper', stack: new Stack<number>() };

  // 给起始塔入栈指定数目的盘子
  for (let i = plates; i > 0; i--) {
    source.stack.push(i);
  }

  // 调用递归方法
  return hanoiStackRecur(plates, source, helper, dest);
}

测试下 5 个盘子的运算结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
[
  Map { 'source' => '5, 4, 3, 2', 'helper' => '', 'dest' => '1' },
  Map { 'source' => '5, 4, 3', 'dest' => '1', 'helper' => '2' },
  Map { 'dest' => '', 'source' => '5, 4, 3', 'helper' => '2, 1' },
  Map { 'source' => '5, 4', 'helper' => '2, 1', 'dest' => '3' },
  Map { 'helper' => '2', 'dest' => '3', 'source' => '5, 4, 1' },
  Map { 'helper' => '', 'source' => '5, 4, 1', 'dest' => '3, 2' },
  Map { 'source' => '5, 4', 'helper' => '', 'dest' => '3, 2, 1' },
  Map { 'source' => '5', 'dest' => '3, 2, 1', 'helper' => '4' },
  Map { 'dest' => '3, 2', 'source' => '5', 'helper' => '4, 1' },
  Map { 'dest' => '3', 'helper' => '4, 1', 'source' => '5, 2' },
  Map { 'helper' => '4', 'dest' => '3', 'source' => '5, 2, 1' },
  Map { 'dest' => '', 'source' => '5, 2, 1', 'helper' => '4, 3' },
  Map { 'source' => '5, 2', 'helper' => '4, 3', 'dest' => '1' },
  Map { 'source' => '5', 'dest' => '1', 'helper' => '4, 3, 2' },
  Map { 'dest' => '', 'source' => '5', 'helper' => '4, 3, 2, 1' },
  Map { 'source' => '', 'helper' => '4, 3, 2, 1', 'dest' => '5' },
  Map { 'helper' => '4, 3, 2', 'dest' => '5', 'source' => '1' },
  Map { 'helper' => '4, 3', 'source' => '1', 'dest' => '5, 2' },
  Map { 'source' => '', 'helper' => '4, 3', 'dest' => '5, 2, 1' },
  Map { 'helper' => '4', 'dest' => '5, 2, 1', 'source' => '3' },
  Map { 'dest' => '5, 2', 'source' => '3', 'helper' => '4, 1' },
  Map { 'dest' => '5', 'helper' => '4, 1', 'source' => '3, 2' },
  Map { 'helper' => '4', 'dest' => '5', 'source' => '3, 2, 1' },
  Map { 'helper' => '', 'source' => '3, 2, 1', 'dest' => '5, 4' },
  Map { 'source' => '3, 2', 'helper' => '', 'dest' => '5, 4, 1' },
  Map { 'source' => '3', 'dest' => '5, 4, 1', 'helper' => '2' },
  Map { 'dest' => '5, 4', 'source' => '3', 'helper' => '2, 1' },
  Map { 'source' => '', 'helper' => '2, 1', 'dest' => '5, 4, 3' },
  Map { 'helper' => '2', 'dest' => '5, 4, 3', 'source' => '1' },
  Map { 'helper' => '', 'source' => '1', 'dest' => '5, 4, 3, 2' },
  Map { 'source' => '', 'helper' => '', 'dest' => '5, 4, 3, 2, 1' }
]

下一篇来分析队列。

前端记事本，不定期更新，欢迎关注！

👆 全文结束，棒槌时间到 👇