IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    数据结构与算法之栈

    冷石发表于 2022-08-29 09:01:22
    love 0

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

    前言

    栈是一种高效的数据结构,因为它只能在栈顶添加或删除,这样的操作很快,它是被称之为后入先出(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


沪ICP备19023445号-2号
友情链接