用js实现堆栈

使用数组实现堆栈

堆栈是一种后进先出（LIFO）的数据结构，可以通过数组的 push 和 pop 方法简单实现。

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

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

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    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());
  }
}

使用对象实现堆栈

使用对象实现堆栈可以避免数组的 shift 和 unshift 操作带来的性能问题。

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

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

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

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    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;
  }
}

使用闭包实现堆栈

闭包可以隐藏内部实现细节，提供更好的封装性。

const Stack = (() => {
  const items = new WeakMap();

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

    push(element) {
      const s = items.get(this);
      s.push(element);
    }

    pop() {
      const s = items.get(this);
      if (s.length === 0) {
        return "Stack is empty";
      }
      return s.pop();
    }

    peek() {
      const s = items.get(this);
      if (s.length === 0) {
        return "Stack is empty";
      }
      return s[s.length - 1];
    }

    isEmpty() {
      const s = items.get(this);
      return s.length === 0;
    }

    size() {
      const s = items.get(this);
      return s.length;
    }

    clear() {
      items.set(this, []);
    }

    print() {
      const s = items.get(this);
      console.log(s.toString());
    }
  }

  return Stack;
})();

使用链表实现堆栈

链表实现可以避免数组的大小限制问题。

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  push(element) {
    const node = new Node(element);
    node.next = this.top;
    this.top = node;
    this.size++;
  }

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const removedNode = this.top;
    this.top = removedNode.next;
    this.size--;
    return removedNode.element;
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.element;
  }

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

  getSize() {
    return this.size;
  }

  clear() {
    this.top = null;
    this.size = 0;
  }

  print() {
    let current = this.top;
    const elements = [];
    while (current) {
      elements.push(current.element);
      current = current.next;
    }
    console.log(elements.toString());
  }
}