cover

数据结构与算法之栈

最后更新:  阅读时间: 2 min 知识共享许可协议

前言

栈是一种高效的数据结构，因为它只能在栈顶添加或删除，这样的操作很快，它是被称之为后入先出（LIFO，last in first out）的数据结构。可以将栈想象成一叠装菜的盘子，用的时候先拿最上面的，洗好的盘子又会放到最上面。

实现

用 TypeScript 实现栈

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
class Stack {
  top: number = 0
  data: Array<any> = []

  get length() {
    return this.top
  }

  // 向栈中压入一个新元素
  push(element: any) {
    this.data.push(element)
    this.top += 1
  }

  // 返回栈顶元素, 同时将 top 值减 1
  pop() {
    this.top -= 1
    return this.data.pop()
  }

  // 返回栈顶元素
  peek() {
    if (!this.data.length) {
      return false
    }

    return this.data[this.top - 1]
  }

  // 清空栈
  clear() {
    this.top = 0
  }
}

测试

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
const stack = new Stack()

stack.push('aaa')
stack.push('bbb')
stack.push('ccc')
stack.push('ddd')

console.log('执行 push 方法后\n', stack)

stack.pop()

console.log('执行 pop 方法后\n', stack)

console.log('执行 peek 方法后返回：', stack.peek())

stack.clear()

console.log('执行 clear 方法后\n', stack)

执行 push 方法后
 Stack { data: [ 'aaa', 'bbb', 'ccc', 'ddd' ], top: 4 }
执行 pop 方法后
 Stack { data: [ 'aaa', 'bbb', 'ccc' ], top: 3 }
执行 peek 方法后返回： ccc
执行 clear 方法后
 Stack { data: [ 'aaa', 'bbb', 'ccc' ], top: 0 }

应用

将 10 进制的数转化为另一种进制

此算法只针对基数为 2 ～ 9 的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function mulBase(num: number, base: number) {
  const stack = new Stack()

  while (num > 0) {
    stack.push(num % base)
    num = Math.floor((num /= base))
  }
  let converted = ''
  while (stack.length > 0) {
    converted += stack.pop()
  }

  return converted
}

console.log('num = 2 base = 2：', mulBase(2, 2)) // 10

console.log('num = 32 base = 2：', mulBase(32, 2)) // 100000

console.log('num = 125 base = 8：', mulBase(125, 8)) // 175

判断回文

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
function isPalindrome(word: string) {
  let rword = ''
  const stack = new Stack()

  word.split('').forEach(w => stack.push(w))

  while (stack.length > 0) {
     rword += stack.pop()
  }

  if(word === rword) {
    return true
  }

  return false
}


console.log('hello', isPalindrome('hello'));

console.log('bob', isPalindrome('bob'));

console.log('racecar', isPalindrome('racecar'));

hello false
bob true
racecar true
Buy Me A Coffee
← 关于 Flutter 的安卓打包 数据结构与算法之列表 →