第一章、栈

栈遵循后进先出原则。

创建一个基于数组的栈

class Stack {
  constructor() {
    this.items = [];
  }

  // 添加元素
  push(item) {
    this.items.push(item);
  }

  // 移除元素并返回移除的元素
  pop(item) {
    return this.items.pop(item);
  }

  // 查看栈顶元素
  peek() {
    return this.items[this.items.length - 1];
  }

  // 检查栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // 返回数组的大小
  size() {
    return this.items.length;
  }

  // 清空栈
  clear() {
    this.items = [];
  }
}

创建一个基于对象的栈

class Stack {
  constructor() {
    // 记录栈大小
    this.count = 0;
    this.items = {};
  }

  // 添加元素
  push(item) {
    this.items[this.count] = item;
    this.count++;
  }

  // 移除元素并返回移除的元素
  pop(item) {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  // 查看栈顶元素
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }

  // 检查栈是否为空
  isEmpty() {
    return this.count === 0;
  }

  // 返回数组的大小
  size() {
    return this.count;
  }

  // 清空栈
  clear() {
    this.items = {};
    this.count = 0;
  }

  // 打印栈内容
  toString() {
    if (this.isEmpty()) {
      return "";
    }
    let objString = `${this.items[0]}`;
    for (let i = 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString
  }
}

使用栈解决问题

十进制到二进制转换

function decimalToBinary(decNumber) {
  const remStack = new Stack();
  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.isEmpty()) {
    binaryString += remStack.pop() + "";
  }
  return binaryString;
}

十进制转换为2~36的任意进制

function decimalToBinary(decNumber, base) {
  const remStack = new Stack();
  // 对余数进行转换
  const digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  let number = decNumber;
  let rem;
  let binaryString = "";

  // 参数不合规直接返回空字符串
  if (!(base >= 2 && base <= 36)) {
    return "";
  }

  // 向栈中推入每一位数
  while (number > 0) {
    rem = Math.floor(number % 2);
    remStack.push(rem);
    number = Math.floor(number / 2);
  }
  // 取出栈中推入每一位数组成字符串返回
  while (!remStack.isEmpty()) {
                    // 取余数对应的值
    binaryString += digits[remStack.pop()];
  }
  return binaryString;
}

方法只是展示栈思想，JS中可以直接转换

// 表示将changeNumber当做nowBase进制数，并返回它的base进制字符串形式
function changeDecimal(changeNumber, nowBase, base) {
  return parseInt(decNumber, nowBase).toString(base)
}

// 将100当做10进制数，并返回它的2进制字符串形式
console.log(changeDecimal(100, 10, 2));