系列文章目录《JavaScript 基础与进阶笔记》前期偏基础巩固与常见面试点后续进入闭包、异步、工程化等进阶主题第 01 篇数据类型与类型判断第 02 篇变量声明与作用域第 03 篇闭包与高阶函数第 04 篇函数工厂第 05 篇this 指向与绑定第 06 篇原型与原型链第 07 篇类与继承第 08 篇JS 执行机制与异步队列第 09 篇数组常用方法第 10 篇字符串算法第 11 篇常见手写题合集上第 12 篇常见手写题合集下第 13 篇Promise 与 async/await第 14 篇数据结构基础本文文章目录系列文章目录前言一、栈Stack1.1 特性1.2 数组实现1.3 典型场景二、队列Queue2.1 特性2.2 数组实现与注意点2.3 典型场景三、链表Linked List3.1 与数组对比3.2 单向链表节点与基本操作3.3 经典题反转链表3.4 快慢指针简述四、二叉树Binary Tree4.1 基本概念4.2 深度优先遍历DFS4.3 广度优先遍历BFS / 层序五、哈希与 Map / Set5.1 哈希表思想5.2 Map / Set 常用 API5.3 Object vs Map面试简表5.4 典型应用六、复杂度速查七、递归 vs 迭代八、易混淆点归纳九、思考与练习总结前言Promise 与 async/await 解决的是异步流程许多算法与面试题则建立在数据结构之上。本篇梳理前端最常碰到的栈、队列、链表、二叉树、哈希Map/Set每种结构说清特性、典型操作复杂度、JavaScript 实现或内置替代并强调递归 vs 迭代如何选。与第 09 篇数组去重、第 12 篇 LRUMap 维护顺序可对照阅读——LRU 本质是「哈希 顺序」的组合应用。一、栈Stack1.1 特性后进先出LIFO, Last In First Out只在同一端插入与删除。操作含义数组实现均摊复杂度push入栈O(1)pop出栈O(1)peek / top看栈顶O(1)1.2 数组实现classStack{#items[];push(x){this.#items.push(x);}pop(){returnthis.#items.pop();}peek(){returnthis.#items[this.#items.length-1];}getsize(){returnthis.#items.length;}isEmpty(){returnthis.#items.length0;}}1.3 典型场景函数调用栈引擎内置记录调用上下文递归过深 →栈溢出。括号匹配、表达式求值逆波兰。DFS 迭代用栈替代递归第 09 篇扁平化也有「迭代栈」写法。浏览器历史后退可建模为栈前进栈另说。constisValidParentheses(s){conststack[];constmap{):(,]:[,}:{};for(constcofs){if(([{.includes(c))stack.push(c);elseif()]}.includes(c)){if(stack.pop()!map[c])returnfalse;}}returnstack.length0;};isValidParentheses(()[]{});// trueisValidParentheses((]);// false二、队列Queue2.1 特性先进先出FIFO, First In First Out从队尾入队、队头出队。操作含义说明enqueue入队加到尾部dequeue出队从头部移除front队头元素只读2.2 数组实现与注意点classQueue{#items[];enqueue(x){this.#items.push(x);}dequeue(){returnthis.#items.shift();// 注意shift 为 O(n)}front(){returnthis.#items[0];}getsize(){returnthis.#items.length;}}Array.prototype.shift需要移动后续元素复杂度O(n)。数据量大时可用头尾指针或链表实现O(1) 出队classQueueFast{#head0;#tail0;#items[];enqueue(x){this.#items[this.#tail]x;}dequeue(){if(this.#headthis.#tail)returnundefined;returnthis.#items[this.#head];}}2.3 典型场景BFS 广度优先层序遍历二叉树、最短路径无权图。任务调度宏任务/微任务队列概念层见第 08 篇。限流、消息缓冲生产者先进先出消费。双端队列Deque两端都可入队/出队滑动窗口最大值等题常用。三、链表Linked List3.1 与数组对比数组单向链表随机访问O(1)O(n)头插O(n) 需移动元素O(1)已知节点删除O(n) 找下标O(1) 改指针内存连续节点分散额外存指针3.2 单向链表节点与基本操作classListNode{constructor(val,nextnull){this.valval;this.nextnext;}}classLinkedList{constructor(){this.headnull;this.size0;}prepend(val){this.headnewListNode(val,this.head);this.size;}append(val){constnodenewListNode(val);if(!this.head){this.headnode;}else{letcurthis.head;while(cur.next)curcur.next;cur.nextnode;}this.size;}find(val){letcurthis.head;while(cur){if(cur.valval)returncur;curcur.next;}returnnull;}}3.3 经典题反转链表迭代三指针constreverseList(head){letprevnull;letcurhead;while(cur){constnextcur.next;cur.nextprev;prevcur;curnext;}returnprev;};递归constreverseListRec(head){if(!head||!head.next)returnhead;constnewHeadreverseListRec(head.next);head.next.nexthead;head.nextnull;returnnewHead;};迭代O(n) 时间O(1) 额外空间面试常优先写。递归O(n) 时间O(n) 调用栈空间代码短注意栈深度。3.4 快慢指针简述找链表中点 / 判环快指针每次走 2 步慢指针走 1 步若有环两指针终将相遇。判环与找入口为常见 follow-up本篇记思路即可。四、二叉树Binary Tree4.1 基本概念二叉树每个节点最多2个子节点。满二叉树 / 完全二叉树堆、优先队列常用完全二叉树性质。二叉搜索树BST左 根 右中序遍历得有序序列。classTreeNode{constructor(val,leftnull,rightnull){this.valval;this.leftleft;this.rightright;}}4.2 深度优先遍历DFS遍历顺序递归口诀前序根 → 左 → 右先处理根中序左 → 根 → 右BST 中序有序后序左 → 右 → 根删树、算子树信息constpreorder(root,res[]){if(!root)returnres;res.push(root.val);preorder(root.left,res);preorder(root.right,res);returnres;};constinorder(root,res[]){if(!root)returnres;inorder(root.left,res);res.push(root.val);inorder(root.right,res);returnres;};迭代前序栈constpreorderIter(root){if(!root)return[];conststack[root];constres[];while(stack.length){constnodestack.pop();res.push(node.val);if(node.right)stack.push(node.right);if(node.left)stack.push(node.left);}returnres;};4.3 广度优先遍历BFS / 层序用队列按层从左到右constlevelOrder(root){if(!root)return[];constqueue[root];constres[];while(queue.length){constlevelSizequeue.length;constlevel[];for(leti0;ilevelSize;i){constnodequeue.shift();level.push(node.val);if(node.left)queue.push(node.left);if(node.right)queue.push(node.right);}res.push(level);}returnres;};复杂度访问每个节点一次时间O(n)递归 DFS 额外栈深O(h)h 为树高最坏 O(n)BFS 队列最多一层节点O(w)w 为最大宽度。五、哈希与 Map / Set5.1 哈希表思想通过hash 函数将 key 映射到存储位置期望O(1)查找/插入/删除冲突时用链地址法或开放寻址均摊仍常记 O(1)。JavaScript 中Object键多为字符串/Symbol有原型链适合固定 shape 的 record。Map任意类型作键插入顺序迭代size可读频繁增删更直观。Set唯一值集合SameValueZeroNaN等于NaN。5.2 Map / Set 常用 APIconstmnewMap();constkey{id:1};m.set(key,meta);m.set(name,test);m.get(key);// metam.has(name);// truem.size;// 2constsnewSet([1,2,2,3,NaN,NaN]);[...s];// [1, 2, 3, NaN]5.3 Object vs Map面试简表对比项ObjectMap键类型字符串 / Symbol 为主任意值键顺序整数键升序 插入序混排严格插入序大小需自行计数.size默认键有原型链无典型场景JSON 形数据对象作键、LRU、计数5.4 典型应用两数之和Map存「值 → 下标」一遍扫描 O(n)。数组去重Set第 09 篇。频次统计Map计数字符/单词出现次数。缓存键为对象时用Map勿用普通对象{}当对象键字典键会被转成[object Object]。consttwoSum(nums,target){constmapnewMap();for(leti0;inums.length;i){constneedtarget-nums[i];if(map.has(need))return[map.get(need),i];map.set(nums[i],i);}return[];};twoSum([2,7,11,15],9);// [0, 1]WeakMap / WeakSet键/值须为对象、弱引用、不可遍历与垃圾回收相关下一篇专讲此处知道「存 DOM 元数据、不阻止 GC」即可。六、复杂度速查结构访问搜索插入删除备注数组O(1)O(n)尾 O(1) / 头 O(n)尾 O(1) / 中 O(n)连续内存链表O(n)O(n)已知节点 O(1)已知节点 O(1)无随机访问栈/队列数组栈顶/队头—push O(1)pop O(1) / shift O(n)队列用指针优化哈希 Map/Set—均摊 O(1)均摊 O(1)均摊 O(1)依赖 hash二叉树—O(n)O(1) 挂子节点O(n) 找父BST 搜索 O(h)树相关n 个节点DFS/BFS 遍历均为O(n)。七、递归 vs 迭代维度递归迭代代码简洁、贴近定义常需栈/队列显式模拟空间调用栈 O(h) 或 O(n)可控通常 O(1)O(w)风险深度过大栈溢出逻辑稍繁琐适用树/链表定义性操作超长链、性能敏感、工程约束实践建议面试先写递归再提迭代优化展示两种思路。反转链表、树遍历两种都要会。BFS 必用队列DFS 可递归可栈。八、易混淆点归纳栈 vs 队列LIFO vs FIFODFS 常用栈BFS 常用队列。shift出队数组实现队列时 dequeue 是 O(n)别在面试里说成全 O(1)。Map vs Object对象键、频繁增删、要size→ 优先Map。Set 去重 vsindexOfSet 正确解决NaNindexOf不行。中序 vs 前序BST中序有序前序常用于复制/序列化思路。递归深度链表/树不平衡时递归可能O(n) 栈空间。九、思考与练习1.用栈判断([{}])是否合法括号串解析合法。依次匹配入栈出栈最后栈空。2.数组[1,2,3,4,5]用shift循环出队 5 次总复杂度量级解析约O(n²)每次 shift O(n)。3.BST 中序遍历输出什么性质解析升序左 根 右。4.twoSum用 Map 为什么是一遍 O(n)解析查target - nums[i]是否在 Map查/插均摊 O(1)扫一遍即可。5.100 层极不平衡链表退化成链递归反转有何风险解析递归深度 100可能栈溢出应改用迭代三指针。总结栈LIFO括号、DFS、调用栈push/pop O(1)。队列FIFOBFS、调度数组shift注意O(n)可用指针优化。链表无随机访问头插 O(1)反转递归/迭代都要会快慢指针判环。二叉树DFS 三种序 BFS 层序遍历O(n)。Map/Set哈希均摊 O(1)对象键、去重、计数与 Object 分清场景。递归 vs 迭代面试双写法深度大优先迭代。下一篇讲垃圾回收与内存标记清除、分代、闭包泄漏以及WeakMap / WeakSet / WeakRef的使用场景。