当前位置：首页 > JavaScript

js 实现单链表实现栈

2026-02-02 13:04:01JavaScript

js 实现单链表实现栈

单链表实现栈的原理

栈是一种后进先出（LIFO）的数据结构，单链表实现栈的关键在于利用链表的头部作为栈顶，这样插入和删除操作的时间复杂度均为 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 null;
    }
    const poppedValue = this.top.value;
    this.top = this.top.next;
    this.size--;
    return poppedValue;
  }

  // 查看栈顶元素
  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.top.value;
  }

  // 判断栈是否为空
  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.value);
      current = current.next;
    }
    console.log(elements.join(' -> '));
  }
}

使用示例

const stack = new LinkedListStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.print(); // 输出: 3 -> 2 -> 1

console.log(stack.pop()); // 输出: 3
stack.print(); // 输出: 2 -> 1

console.log(stack.peek()); // 输出: 2
console.log(stack.getSize()); // 输出: 2
console.log(stack.isEmpty()); // 输出: false

stack.clear();
console.log(stack.isEmpty()); // 输出: true