javascript数据结构如何实现_怎样编写栈队列和链表【教程】

javaScript中栈、队列、链表应优先用数组或对象高效模拟，关键在接口封装与边界控制：栈需封装push/pop/peek/isEmpty并校验入参与空栈；队列避免shift/unshift，推荐双索引法或Deque；链表重点是insertAt/removeAt的下标校验与引用维护。

javascript 里实现栈、队列、链表，不需要造轮子式地从零手写底层指针逻辑——现代 js 用数组或对象就能高效模拟，关键在接口设计和边界控制。

用 Array 实现栈：别只用 push/pop，得封住非法操作

栈的核心是 LIFO，但直接暴露原生数组方法会破坏封装性（比如用户调用 arr[5] = 'x' 就绕过栈逻辑）。应该封装成类，只暴露 push、pop、peek、isEmpty 四个接口：

• push 内部调用 Array.prototype.push，但要检查入参是否为有效值（比如拒绝 undefined 或 NULL，视业务而定）
• pop 必须先判空，空栈时返回 undefined 而不是抛错（除非你明确要求强契约）
• peek 用 this.items[this.items.Length - 1]，别用 slice(-1)[0]——后者创建新数组，不必要开销

用 Array 实现队列：避免 shift 导致的 O(n) 性能陷阱

用数组模拟队列时，unshift 入队 + pop 出队，或 push 入队 + shift 出队，都会因数组元素移动导致出队操作变成 O(n)。实际项目中更推荐：

• 双索引法：维护 head 和 tail 指针，所有操作 O(1)，空间复用（类似循环队列）
• 或直接用 Deque（chrome 124+、node.js 20.12+ 已支持），它底层优化了两端增删
• 若必须兼容老环境，可用两个栈组合实现队列（一个专入、一个专出，出栈空时把入栈全倒过去），均摊 O(1)

手写单向链表：重点不在节点构造，而在 insertAt 和 removeAt 的下标校验

链表节点本身很简单：class Node { constructor(val) { this.val = val; this.next = null; } }。真正容易出错的是操作方法：

立即学习“Java免费学习笔记（深入）”；

• insertAt(index, val)：必须严格校验 index this.size，越界应直接返回或抛 RangeError，而不是静默失败
• removeAt(index)：当 index === 0 时要重置 this.head；当 index === this.size - 1 时要遍历到倒数第二个节点并设其 next = null
• 不要在 toString() 里用递归遍历——长链表易爆栈，改用 while 循环

链表的“复杂”不在结构，而在每个操作都要手动维护引用关系；栈和队列的“坑”也不在逻辑，而在对原生数组性能特性的误判。写之前先想清楚：这个结构会被高频读写？是否需要随机访问？有没有内存敏感场景？这些比“怎么写”更重要。