js实现stack

使用数组实现栈

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

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 Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

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

  pop() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    const poppedValue = this.top.value;
    this.top = this.top.next;
    this.size--;
    return poppedValue;
  }

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

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

  getSize() {
    return this.size;
  }

  print() {
    let current = this.top;
    const elements = [];
    while (current) {
      elements.push(current.value);
      current = current.next;
    }
    console.log(elements.join(" -> "));
  }
}

栈的应用示例

栈常用于解决需要后进先出处理的问题，如括号匹配、函数调用栈等。

// 括号匹配检查
function isBalanced(expression) {
  const stack = new Stack();
  for (const char of expression) {
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char);
    } else {
      if (stack.isEmpty()) return false;
      const top = stack.pop();
      if (
        (char === ')' && top !== '(') ||
        (char === '}' && top !== '{') ||
        (char === ']' && top !== '[')
      ) {
        return false;
      }
    }
  }
  return stack.isEmpty();
}

console.log(isBalanced("({[]})")); // true
console.log(isBalanced("({[})"));  // false

性能优化建议

对于高频操作的场景，数组实现的栈可能因动态扩容导致性能波动。链表实现避免了这一问题，但需要额外的内存存储节点指针。

// 测试两种实现的性能
const testStack = (stack, operations) => {
  const start = performance.now();
  for (let i = 0; i < operations; i++) {
    stack.push(i);
    if (i % 3 === 0) stack.pop();
  }
  return performance.now() - start;
};

const arrayStack = new Stack();
const linkedStack = new LinkedListStack();
console.log(`Array Stack: ${testStack(arrayStack, 1e6)} ms`);
console.log(`Linked Stack: ${testStack(linkedStack, 1e6)} ms`);