JS数据结构与算法-栈

栈结构

特点

栈结构是一种只能在栈顶进行出栈和进栈的数据结构，其特点是“先进后出(FILO)”。

javaScript 实现

class Stack {
  constructor() {
    this.container = [];
  }
  // 入栈
  enter(element) {
    return this.container.unshift(element);
  }
  // 出栈
  leave() {
    return this.container.shift();
  }
  // 获取栈长度
  size() {
    return this.container.length;
  }
  // 获取栈的内容
  value() {
    return this.container;
  }
}

举例

十进制数转二进制

思路

辗转相除法：将数字 num 除以 2 的余数入栈，然后用除以 2 的商赋值给 num 继续上述操作，直到 num 为 0 为止，最后将栈内所有内容出栈拼成字符串即可。

代码

const num = 45;
console.log(num.toString(2)); // 101101
// 使用栈结构
Number.prototype.decimalToBinary = function decimalToBinary() {
  let stack = new Stack();
  let decimalNum = this.valueOf(); // 因为this是对象，要用valueOf获取数字的值
  if (decimalNum === 0) return "0";
  while (decimalNum > 0) {
    stack.enter(decimalNum % 2);
    decimalNum = Math.floor(decimalNum / 2);
  }
  return stack.value().join("");
};
console.log(num.decimalToBinary()); // 101101