欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2__栈(先进后出)__

程序员文章站 2024-03-17 21:52:10
...

栈(先进后出)

创建一个基于数组的栈

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;
}