当前位置：首页 > JavaScript

js 实现栈

2026-03-15 05:01:17JavaScript

栈的基本概念

栈是一种遵循后进先出（LIFO）原则的数据结构。栈的操作主要包括压栈（push）和弹栈（pop），其他常见操作包括查看栈顶元素（peek）和判断栈是否为空（isEmpty）。

基于数组的栈实现

使用数组可以简单高效地实现栈。数组的末尾作为栈顶，压栈和弹栈操作的时间复杂度均为 O(1)。

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

基于链表的栈实现

链表也可以用来实现栈，链表的头部作为栈顶。链表的插入和删除操作在头部进行，时间复杂度同样为 O(1)。

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;
  }
}

栈的应用示例

栈在计算机科学中有广泛的应用，例如函数调用栈、表达式求值、括号匹配等。以下是括号匹配的示例代码：

js 实现栈

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

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

  return stack.isEmpty();
}

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