[数据结构与算法]2__栈(先进后出)__

栈(先进后出)

创建一个基于数组的栈

class Stack {
  constructor() {
    this.items = [];
  }
  // 添加一个(或几个)新元素到栈顶
  push(element) {
    this.items.push(element);
  }
  // 移除栈顶的元素，同时返回被移除的元素
  pop() {
    return this.items.pop();
  }
  // 返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）
  peek() {
    return this.items[this.items.length - 1];
  }
  // 如果栈里没有任何元素就返回true，否则返回false
  isEmpty() {
    return this.items.length === 0;
  }
  // 返回栈里的元素个数。该方法和数组的length属性很类似
  size() {
    return this.items.length;
  }
  // 移除栈里的所有元素
  clear() {
    this.items = [];
  }
}

创建一个基于 JavaScript 对象的 Stack 类

class Stack {
  constructor() {
    // 栈的大小
    this.count = 0;
    this.items = {};
  }
  // 向栈中插入元素
  push(element) {
    this.items[this.count] = element;
    this.count++;
  }
  // 栈的大小
  size() {
    return this.count;
  }
  // 栈是否为空
  isEmpty() {
    return this.count === 0;
  }
  // 从栈中弹出元素
  pop() {
    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];
  }
  // 清空栈
  clear() {
    this.items = {};
    this.count = 0;
  }
  // 创建一个toString方法来像数组一样打印出栈的内容
  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;
  }
}

保护数据结构内部元素

const _items = Symbol("stackItems");

class Stack {
  constructor() {
    this[_items] = [];
  }
  // 向栈中插入元素
  push(element) {
    this[_items].push(element);
  }
  // 从栈中弹出元素
  pop() {
    return this[_items].pop();
  }
  // 查看栈顶的值
  peek() {
    return this[_items][this[_items].length - 1];
  }
  // 栈是否为空
  isEmpty() {
    return this[_items].length === 0;
  }
  // 栈的大小
  size() {
    return this[_items].length;
  }
  // 清空栈
  clear() {
    this[_items] = [];
  }
  // 打印栈
  print() {
    console.log(this.toString());
  }
  // 创建一个toString方法来像数组一样打印出栈的内容
  toString() {
    return this[_items].toString();
  }
}

用 ES2015 的 WeakMap 实现类

const _items = new WeakMap();
const _count = new WeakMap();

class Stack {
  constructor() {
    _count.set(this, 0);
    _items.set(this, {});
  }
  // 向栈中插入元素
  push(element) {
    const items = _items.get(this);
    const count = _count.get(this);
    items[count] = element;
    _count.set(this, count + 1);
  }
  // 从栈中弹出元素
  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    const items = _items.get(this);
    let count = _count.get(this);
    count--;
    _count.set(this, count);
    const result = items[count];
    delete items[count];
    return result;
  }
  // 查看栈顶的值
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    const items = _items.get(this);
    const count = _count.get(this);
    return items[count - 1];
  }
  // 栈是否为空
  isEmpty() {
    return _count.get(this) === 0;
  }
  // 栈的大小
  size() {
    return _count.get(this);
  }

  clear() {
    /* while (!this.isEmpty()) {
        this.pop();
      } */
    _count.set(this, 0);
    _items.set(this, {});
  }
  // 清空栈
  toString() {
    if (this.isEmpty()) {
      return "";
    }
    const items = _items.get(this);
    const count = _count.get(this);
    let objString = `${items[0]}`;
    for (let i = 1; i < count; i++) {
      objString = `${objString},${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); // {4}
  }
  while (!remStack.isEmpty()) {
    binaryString += remStack.pop().toString();
  }
  return binaryString;
}

进制转换算法

// 把十进制转换成基数为2～36的任意进制
function baseConverter(decNumber, base) {
  const remStack = new Stack();
  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.isEmpty()) {
    baseString += digits[remStack.pop()];
  }
  return baseString;
}