JavaScript 算法与数据结构：实用指南

JavaScript 算法与数据结构：从理论到实践

掌握算法与数据结构是任何开发人员的关键技能，无论使用何种编程语言。JavaScript（尤其是在 Node.js 环境中）也不例外。在本文中，我们将使用纯 JavaScript 实现基本的数据结构和经典算法。您将看到栈、队列、链表、树以及排序/搜索算法如何应用于 Node.js 后端开发的实际任务中。

1. 栈和队列：用于数据管理的基本结构

栈 (Stack) 和队列 (Queue) 是线性数据结构，它们的元素添加和删除规则不同。栈遵循 LIFO（后进先出）原则，而队列遵循 FIFO（先进先出）原则。

JavaScript 中栈的实现

在 JavaScript 中，栈可以基于数组或链表实现。我们来看一个简单的数组实现：

class Stack {\n    constructor() {\n        this.items = [];\n    }\n\n    push(element) {\n        this.items.push(element);\n    }\n\n    pop() {\n        if (this.isEmpty()) return null;\n        return this.items.pop();\n    }\n\n    peek() {\n        if (this.isEmpty()) return null;\n        return this.items[this.items.length - 1];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// 使用示例\nconst stack = new Stack();\nstack.push('A');\nstack.push('B');\nstack.push('C');\nconsole.log(stack.pop());  // 'C'\nconsole.log(stack.peek()); // 'B'

栈常用于检查括号是否平衡、实现浏览器中的“后退”按钮或进行深度优先遍历。

JavaScript 中队列的实现

队列也可以基于数组构建，但为了更好的性能（避免 shift 操作导致的重新索引），我们可以使用链表或两个栈。这是一个简单的数组实现：

class Queue {\n    constructor() {\n        this.items = [];\n    }\n\n    enqueue(element) {\n        this.items.push(element);\n    }\n\n    dequeue() {\n        if (this.isEmpty()) return null;\n        return this.items.shift();\n    }\n\n    front() {\n        if (this.isEmpty()) return null;\n        return this.items[0];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// 使用示例\nconst queue = new Queue();\nqueue.enqueue(1);\nqueue.enqueue(2);\nqueue.enqueue(3);\nconsole.log(queue.dequeue()); // 1\nconsole.log(queue.front());   // 2

队列用于任务管理系统、BFS（广度优先搜索）算法以及 Node.js 中的数据缓冲（例如流）。

2. 链表：适用于频繁插入的动态结构

链表 (Linked List) 是一系列节点，每个节点包含数据和对下一个节点的引用。与数组不同，在链表中间插入和删除元素的时间复杂度为 O(1)（前提是拥有对节点的引用）。

单向链表的实现

class ListNode {\n    constructor(value, next = null) {\n        this.value = value;\n        this.next = next;\n    }\n}\n\nclass LinkedList {\n    constructor() {\n        this.head = null;\n        this.tail = null;\n        this.length = 0;\n    }\n\n    append(value) {\n        const newNode = new ListNode(value);\n        if (!this.head) {\n            this.head = newNode;\n            this.tail = newNode;\n        } else {\n            this.tail.next = newNode;\n            this.tail = newNode;\n        }\n        this.length++;\n        return this;\n    }\n\n    prepend(value) {\n        const newNode = new ListNode(value, this.head);\n        this.head = newNode;\n        if (!this.tail) this.tail = newNode;\n