js实现stack

使用数组实现栈

在JavaScript中，栈可以通过数组的原生方法轻松实现。数组的push()和pop()方法天然符合栈的后进先出（LIFO）原则。

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

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    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.items.toString());
  }
}

使用对象实现栈

对于需要更高性能的场景，可以用对象来模拟栈，避免数组方法的一些潜在开销。

class Stack {
  constructor() {
    this.count = 0;
    this.items = {};
  }

  push(element) {
    this.items[this.count] = element;
    this.count++;
  }

  pop() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  peek() {
    return this.items[this.count - 1];
  }

  isEmpty() {
    return this.count === 0;
  }

  size() {
    return this.count;
  }

  clear() {
    this.items = {};
    this.count = 0;
  }

  toString() {
    return Object.values(this.items).toString();
  }
}

栈的典型应用

十进制转二进制是栈的经典应用场景之一：

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().toString();
  }

  return binaryString || '0';
}

性能考虑

数组实现的栈在大多数现代JavaScript引擎中性能足够好，因为push()和pop()都是O(1)操作。对象实现方式在极高频操作场景可能略有优势，但差异通常不大。选择实现方式时应优先考虑代码可读性，除非有明确的性能瓶颈。