作者: Jim_Fun | 来源:发表于2019-03-17 20:53 被阅读0次
  • 是一种后入先出(LIFO,last-in-first-out)的数据结构
  • 栈使用两种基本操作:推入(压栈,push)和弹出(弹栈,pop)
  • 在javascript中,栈可以看成是数组的子集

1、实现

class Stack{
    constructor() {
        this.stack= [];
    }
    push(item) {
        this.stack.push(item);
    }
    pop() {
        this.stack.pop();
    }
}

2、应用

数制间的相互转换

可以利用栈将一个数字从一种数制转换成另一种数制。假设想将数字 n 转换为以 b 为基数 的数字,实现转换的算法如下:

  1. 最高位为 n % b,将此位压入栈
  2. 使用 n/b 代替 n
  3. 重复步骤 1 和 2,直到 n 等于 0,且没有余数
  4. 持续将栈内元素弹出,直到栈为空,依次将这些元素排列,就得到转换后数字的字符 串形式
function mulBase(num, base) {    
    const s = new Stack();
    do {
        s.push(num % base);    
        num = Math.floor(num /= base);
    } while (num > 0);
    let converted = "";
    while (s.length() > 0) {
        converted += s.pop();
    }    
    return converted;
}

括号匹配

/**
 * @param {string} s
 * @return {boolean}
 */
function isValid(s) {
    const stack = [];
    const mapping = {
        ')': '(',
        '}': '{',
        ']': '['
    };
    for (v of s) {
        if (v in mapping) {
            let top_el = stack.pop();
            if (top_el !== mapping[v]) {
                return false;
            }
        } else {
            stack.push(v)
        }
    }
    return stack.length === 0;
};

相关文章

  • Java实现栈

    数组栈:压栈、出栈、返回栈顶元素 链式栈:压栈、出栈、返回栈顶元素

  • 数据结构之 栈

    栈结构 链式栈 一.栈结构体 1构建空栈 2栈置空 3判断栈空 4获取栈顶 5入栈 6出栈 7便利栈 二.链式栈 ...

  • 栈和队列

    1、栈 栈是一种先进先出的数据结构。栈顶进栈,栈顶出栈。 数据结构 栈的初始化 进栈 出栈 栈的最小值 2、队列 ...

  • 递归累加数组

    入栈 5入栈 4入栈 3入栈 2入栈 1出栈 [1 0]出栈 [2 1 0]出栈 [3 2 1 0]出栈 [4 3...

  • 栈的逻辑结构和存储结构

    main()进栈s(1)进栈s(0)进栈 s(0)出栈s(1)出栈main()出栈 顺序栈 一个数组 + 指向栈顶...

  • 单调栈 2020-06-12(未经允许,禁止转载)

    1.单调栈 指栈内元素保持单调性的栈结构,分为单调增栈(栈底到栈顶元素递增)和单调减栈(栈底到栈顶元素递减) 2....

  • 链栈的操作

    链栈的定义 链栈的操作 初始化 判断栈空 入栈 出栈

  • 函数调用栈平衡

    栈平衡 栈平衡:函数调用前后的栈顶指针指向的位置不变 内平栈 外平栈 内平栈: 指的是在函数调用返回之前使栈保持...

  • 栈的简单Java实现

    栈栈的特点是先进后出,出栈、入栈都是在栈顶操作。

  • 汇编学习-入栈和出栈

    栈有两个基本的操作:入栈和出栈。入栈就是将一个新的元素放到栈顶,出栈就是从栈顶取出一个元素。栈顶的元素总是最后入栈...

网友评论

      本文标题:

      本文链接:https://www.haomeiwen.com/subject/rgzymqtx.html