数据结构：JS实现链表、栈与队列

JavaScript实现链表、栈和队列：1. 链表通过节点连接，支持高效插入删除；2. 栈遵循后进先出原则，常用push和pop操作；3. 队列遵循先进先出原则，可用数组实现但shift性能较差需优化。

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

落笔AI

AI写作，AI写网文、AI写长篇小说、短篇小说

41

查看详情

  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) 出队。

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

以上就是数据结构：JS实现链表、栈与队列的详细内容，更多请关注php中文网其它相关文章！