当前位置：首页 > JavaScript

js实现堆栈

2026-04-07 00:14:51JavaScript

使用数组实现堆栈

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

js实现堆栈

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 = [];
  }
}

// 使用示例
const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.pop()); // 输出 20
console.log(stack.peek()); // 输出 10

使用链表实现堆栈

链表实现堆栈可以避免数组动态扩容的开销，适合频繁的入栈和出栈操作。

js实现堆栈

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 "Stack is empty";
    }
    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;
  }

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

// 使用示例
const linkedListStack = new LinkedListStack();
linkedListStack.push(30);
linkedListStack.push(40);
console.log(linkedListStack.pop()); // 输出 40
console.log(linkedListStack.peek()); // 输出 30

堆栈的应用场景

堆栈常用于需要后进先出操作的场景，如函数调用栈、括号匹配、表达式求值等。

// 括号匹配示例
function isBalanced(expression) {
  const stack = new Stack();
  const brackets = { '(': ')', '[': ']', '{': '}' };

  for (let char of expression) {
    if (brackets[char]) {
      stack.push(char);
    } else if (char === ')' || char === ']' || char === '}') {
      if (stack.isEmpty() || brackets[stack.pop()] !== char) {
        return false;
      }
    }
  }

  return stack.isEmpty();
}

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