usehook - 前端码易

基础实现
实战一：进制转换
实战二：有效的括号
思考题

基础实现

栈数据结构的基础理论：先进后出，后进先出。

我们需要用代码体现出来，才算是真正的掌握了栈的思维。

在上一章介绍了数组的栈方法，我们可以依赖于数组，快速实现栈对象。

code.ts

10class Stack {
20  constructor() {
30    // 特别关注，此处的基础数据为数组
40    this.items = [] 
50  }
60  push(node) {
70    this.items.push(node)
80  }
90  pop() {
10    this.items.pop()
11  }
12  peek() {
13    return this.items[this.items.length - 1]
14  }
15  isEmpty() {
16    return this.items.length === 0
17  }
18  clear() {
19    this.items = []
20  }
21}

这种基于数组的实现方式非常简单，因为数组本身就已经实现了一部分栈的特性，因此，我们几乎不用处理额外的逻辑，只是在数组之外套了一层无意义的代码就能实现。

那如果我们不依赖已经具备栈特性的数组，自己来实现应该怎么做呢？

熟悉原型链之后我们会知道，原型链的终点是 Object 原型对象。因此，在 JavaScript 中，最基础的数据结构表达，就是一个 Object 对象。例如对于数组来说，Array 对象中的基础数据结构，应该是这样子

code.ts

1{
2  0: 'Tom',
3  1: 'Tony',
4  2: 'Jim'
5}

实现栈数据结构，也应该跟数组一样，以对象字面量的表达方式，来作为数据结构的基础。实现如下:

code.ts

10class Stack {
20  constructor() {
30    this.items = {}
40    this.length = 0
50  }
60  push(node) {
70    this.items[this.length] = node;
80    this.length++
90  }
10  pop() {
11    if (this.isEmpty()) {
12      return null;
13    }
14    this.length--
15    const r = this.items[this.length]
16    delete this.items[this.length]
17    return r
18  }
19  // 获取栈顶节点
20  peek() {
21    if (this.isEmpty()) {
22      return null
23    }
24    return this.items[this.length - 1]
25  }
26  isEmpty() {
27    return this.length === 0
28  }
29  clear() {
30    this.items = {}
31    this.length = 0
32  }
33}

上例以最基础的对象作为基础数据结构存储栈内容，声明实例并且往栈中添加几个元素，大概长这样。

code.ts

1const stack = new Stack()
2
3stack.push({a: 1})
4stack.push({b: 2})
5stack.push({c: 3})

还需要继续优化。

在我们的设想中，Stack 对象中的基础数据 items 应该只能通过 push, pop, clear 等 api 来修改。但是我们发现，如果 Stack 的实现仅仅如此，我们就还可以通过直接访问 items 的方式来修改它。这违背了我们的初衷，也违背了栈的基础思想。

code.ts

1// 可以这样直接修改
2stack.items = {}

因此，在这里，items 只能作为私有变量被保护起来，才能避免出现这样的情况。在 class 语法中，我们可以直接使用 # 的方式，直接指定对应的变量为私有变量。

code.ts

1class Demo {
2  // 属性名前面加上 #，即为私有变量
3  #length = 0
4  
5  constructor() {
6    this.#items = {}
7  }
8}

不过遗憾的是，私有变量语法，各浏览器的支持程度并不高。因此我们可以使用基础数据类型 Symbol 来模拟私有变量，避免外部的直接访问。

代码如下：

code.ts

10class Stack {
20  constructor() {
30    this._i = Symbol('Stack')
40    this[this._i] = {}
50    this.length = 0
60  }
70  push(node) {
80    this[this._i][this.length] = node;
90    this.length++
10  }
11  pop() {
12    if (this.isEmpty()) {
13      return null;
14    }
15    this.length--
16    const r = this[this._i][this.length]
17    delete this[this._i][this.length]
18    return r
19  }
20  getItems() {
21    return this[this._i]
22  }
23  // 获取栈顶节点
24  peek() {
25    if (this.isEmpty()) {
26      return null
27    }
28    return this[this._i][this.length - 1]
29  }
30  isEmpty() {
31    return this.length === 0
32  }
33  clear() {
34    this[this._i] = {}
35    this.length = 0
36  }
37}

当然，Symbol 也并非完全不能访问，我们可以通过 Object.getOwnPropertySymbols(stack) 来访问实例 stack 的 Symbol 属性。

实战一：进制转换

现在我们有一个需求，利用上面的栈对象，封装一个十进制转二进制的方法

我们知道，二进制是一堆由 0 和 1 组合而成的数字。它的特点就是「逢 2 进 1」。那么如果需要要将 10 进制的数字，转化为二进制的数字，应该怎么做呢？

在我上大学时的教科书上提供了一种方法，叫做「相除取余数」。

什么意思呢？举一个例子，我们要将数字 11 转化为二进制。那么就依次有

code.ts

111 / 2 = 5 余 1  
2// 使用计算结果的整数 5，继续下一次计算
35 / 2 = 2 余 1
42 / 2 = 1 余 0
51 / 2 = 0 余 1

这里，我们得到了每一次计算的余数，把所有的余数拼接起来，就是最终的二进制结果，为 1011 。再换一个数字 20，用这个逻辑继续推演一下

code.ts

120 / 2 = 10 余 0
210 / 2 = 5 余 0 
35 / 2 = 2 余 1
42 / 2 = 1 余 0
51 / 2 = 0 余 1

那么 20 转化为二进制的结果，就是 10100

我们使用代码来实现这个推演过程，只需要在每一次计算时，将余数保存压入栈中，最后将所有栈中的数字拼接起来即可得到二进制结果。

code.ts

10function decimalToBinary(number) {
20  // 声明一个栈容器
30  const stack = new Stack()
40  let result = ''
50
60  while(number > 0) {
70    // 将每一次计算的余数放入栈容器中
80    stack.push(number % 2)
90
10    // 计算下一次参与运算的结果
11    number = Math.floor(number / 2)
12  }
13
14  // 拼接栈中的所有余数，得到二进制结果
15  while(!stack.isEmpty()) {
16    result += stack.pop()
17  }
18
19  return result
20}
21
22
23console.log(decimalToBinary(11))   // 1011 
24console.log(decimalToBinary(20))   // 10100
25console.log(decimalToBinary(25))   // 11001

使用同样的方式，我们可以封装一个通用方法，用于将 10 进制转化为 2/8/16 进制的数字。具体代码如下：

code.ts

10/***
20 * @desc 通用，10进制转其他进制
30 * @param {number} number 10进制数字
40 * @param {number} bs 2进制，8进制，16进制
50 * @return {string} 转换结果 
60 **/
70function converter(number, bs) {
80  const stack = new Stack()
90  const digits = '0123456789ABCDEF'
10  let result = ''
11
12  while(number > 0) {
13    stack.push(number % bs)
14    number = Math.floor(number / bs)
15  }
16
17  while (!stack.isEmpty()) {
18    result += digits[stack.pop()]
19  }
20
21  return result
22}
23
24  console.log(converter(11, 2)) // 1011
25  console.log(converter(20, 2)) // 10100
26  console.log(converter(25, 2)) // 11001
27  console.log(converter(25, 8)) // 31
28  console.log(converter(1231, 16))  // 4CF

实战二：有效的括号

在 LeetCode 中，有这样一道简单算法题。

给定一个只包括小括号 '(' ')' ，中括号 '[' ']' 大括号 ' ' 的字符串，判断字符串是否有效。

有效字符串需要满足：

左括号必须用相同类型的右括号闭合
左括号必须以正确的顺序闭合

示例：

code.ts

10input：'{}'
20out: true
30
40input: '()[]{}'
50out: true
60
70input: '(]'
80out: false
90
10input: '([)]'
11out: false
12        
13input: '{[]}'
14out: true

也就是说，每一个括号，都必须被正确闭合。这个很好理解，而我们要写一个方法来判断字符串的括号是否都正确闭合了，应该怎么办呢？

分析一下，如果我们借助栈的思维来解决问题，我们遍历目标字符串，第一个字符串放入栈中，如果接下来的一个字符串，刚好能够匹配，我们可以将栈中的字符串删除，不能匹配，则继续压入栈中。这样，当字符串的每一个字符都遍历完成之后，如果所有的字符串都成功正确匹配，那是不是栈中应该是空的呀？所以借助这个思路，我们来实现该方法

code.ts

10function isValid(s) {
20  const stack = new Stack()
30
40  for (var i = 0; i < s.length; i++) {
50    // 当前字符
60    const c = s[i]  
70
80    // 栈顶字符
90    const p = stack.peek()
10    if (c == ')' && p == '(' || c == ']' && p == '[' || c == '}' && p == '{') {
11      // 匹配上了，p 出栈，否则，c 入栈
12      stack.pop()
13    } else {
14      stack.push(c)
15    }
16  }
17
18  // 最后，如果栈为空，则表示完全匹配，否则表示没有完全正确匹配
19  return stack.isEmpty()
20}
21
22console.log(isValid('()'))    // true
23console.log(isValid('()[]{}'))  // true
24console.log(isValid('(]'))  // false
25console.log(isValid('([)]'))  // false
26console.log(isValid('{[]}'))  // true

思考题

你在实践场景中，哪些地方运用了栈的基础思维来解决问题？

1、内存与数据结构

3、数据结构：堆

专栏首页

到顶

专栏目录

table of contents

基础实现

实战一：进制转换

实战二：有效的括号

思考题