基本用法

• 一个后进先出的数据结构；
• Array 模拟；push 以及 pop 方法模拟；

const stack = []

// 入栈
stack.push(1)
stack.push(2)

// 出栈 - 移除数组的最后一项
const item1 = stack.pop()
const item2 = stack.pop()

使用场景

• 需要后进先出的场景
• 比如：十进制转二进制、判断字符串的括号是否有效、函数调用堆栈。

算法题：判断字符串的括号是否有效：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

链接：https://leetcode-cn.com/problems/valid-parentheses

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s.length % 2 === 1) {return false;}
    const stack = [];
    const map = new Map();
    map.set('(',')');
    map.set('[', ']');
    map.set('{', '}');
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (map.has(c)) {
            stack.push(c);
        } else {
            // 获取栈顶元素
            const t = stack[stack.length - 1];
            if(map.get(t) === c) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.length === 0;
};

算法题：从十进制到二进制

function decimalToBinary(decNumber) {
  const remStack = []
  let number = decNumber
  let rem
  let binaryString = ''

  while (number > 0) {
    rem = Math.floor(number % 2)
    remStack.push(rem)
    number = Math.floor(number / 2)
  }
  while(remStack.length !== 0) {
    binaryString += remStack.pop().toString()
  }
  return binaryString
}
const result = decimalToBinary(10)

console.log(result) // '0101'

算法题：进制转换算法

function  baseConverter(decNumber, base) {
  const remStack = []
  const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  let number = decNumber
  let rem
  let baseString = ''

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

  while (number > 0) {
    rem = Math.floor(number % base)
    remStack.push(rem)
    number = Math.floor(number / base)
  }

  while (remStack.length !== 0) {
    baseString += digits[remStack.pop()]
  }

  return baseString
}

阅读量：

评 论：