链表栈队列实现全解析

本文深入浅出地讲解了JavaScript中三种核心数据结构——链表、栈与队列的原理与手写实现：链表通过节点指针连接，规避数组移动开销，实现高效动态增删；栈严格遵循后进先出（LIFO），以简洁数组封装支持括号匹配、函数调用等典型场景；队列则坚持先进先出（FIFO），在基础数组实现基础上点明shift性能瓶颈，并提示O(1)优化思路。无论你是算法入门者还是想夯实工程底层能力的开发者，掌握这三者的JS实现逻辑，都将为你理解更复杂结构、写出高性能代码打下坚实基础。

JavaScript 是一门灵活的语言，适合实现常见的数据结构。链表、栈和队列是基础但非常重要的数据结构，在算法和实际开发中广泛使用。下面分别用 JS 实现这三种结构，并说明其核心操作。

链表（Linked List）

链表由节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表在插入和删除时效率更高，因为不需要移动元素。

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  // 在末尾添加节点
  append(val) {
    const node = new ListNode(val);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  // 打印链表值
  display() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.val);
      current = current.next;
    }
    console.log(result.join(' -> '));
  }
}

说明：上面实现了一个单向链表，支持 append 添加节点和 display 显示所有值。可以进一步扩展 insert、remove 等方法。

栈（Stack）

栈是一种后进先出（LIFO）的数据结构，常用操作是 push（入栈）和 pop（出栈）。

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) return undefined;
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) return undefined;
    return this.items[this.items.length - 1];
  }

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

  size() {
    return this.items.length;
  }
}

建议：栈可用于括号匹配、函数调用模拟、表达式求值等场景。用数组实现简单高效。

队列（Queue）

队列是先进先出（FIFO）的结构，常用于任务调度、广度优先搜索等。

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    return this.items.shift();
  }

  front() {
    if (this.isEmpty()) return undefined;
    return this.items[0];
  }

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

  size() {
    return this.items.length;
  }
}

注意：使用 shift() 删除第一个元素的时间复杂度是 O(n)，如果对性能要求高，可以用对象加头尾索引的方式优化为 O(1) 出队。

基本上就这些。链表、栈和队列是构建更复杂结构的基础。理解它们的特性和实现方式，有助于写出更高效的代码。

今天关于《链表栈队列实现全解析》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！