当前位置：首页 > JavaScript

js栈实现

2026-02-01 07:30:45JavaScript

栈的基本概念

栈是一种遵循后进先出（LIFO）原则的数据结构，仅允许在栈顶进行插入（压栈）和删除（弹栈）操作。JavaScript中可通过数组或链表实现栈。

基于数组的栈实现

利用数组的push()和pop()方法可高效模拟栈操作：

js栈实现

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

使用示例

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.length = 0;
  }

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

  pop() {
    if (this.isEmpty()) return null;
    const poppedValue = this.top.value;
    this.top = this.top.next;
    this.length--;
    return poppedValue;
  }

  peek() {
    return this.top?.value;
  }

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

性能对比

数组栈：操作时间复杂度为O(1)，但可能触发动态扩容。
链表栈：无需扩容，但每个操作需处理指针，常数时间略高。

应用场景

函数调用栈：记录函数执行上下文。
括号匹配：检查表达式中的括号是否成对。
撤销操作：保存操作历史以便回退。

括号匹配示例

function isBalanced(expr) {
  const stack = new Stack();
  const map = { '(': ')', '[': ']', '{': '}' };

  for (const char of expr) {
    if (map[char]) stack.push(char);
    else if (char !== map[stack.pop()]) return false;
  }
  return stack.isEmpty();
}
console.log(isBalanced("{[()]}")); // true