JavaScript数据结构深度解析：栈、队列与树的实现与应用
JavaScript数据结构深度解析：栈、队列与树的实现与应用
当函数调用层层嵌套，JavaScript 引擎如何管理这些调用？当事件循环处理异步任务时，背后的数据结构是什么？本文将深入探讨栈、队列和树在前端开发中的核心应用。
前言：从函数调用说起
// 一个简单的函数调用栈示例functionfuncA(){ console.log('进入函数A');funcB(); console.log('离开函数A');}functionfuncB(){ console.log('进入函数B');funcC(); console.log('离开函数B');}functionfuncC(){ console.log('进入函数C'); console.log('离开函数C');}funcA();这段代码的输出顺序是什么？进入函数A 进入函数B 进入函数C 离开函数C 离开函数B 离开函数A 。
这种"先进后出"的执行顺序，正是栈的典型特征。
栈（Stack）的实现与应用
栈的基本概念
栈 是一种后进先出（LIFO）的数据结构，就像一摞盘子，我们只能从最上面取放盘子。
栈的操作示意图
push(3) push(5) pop() → 5 ┌───┐ → ┌───┐ → ┌───┐ → ┌───┐ │ │ │ 3 │ │ 5 │ │ 3 │ ├───┤ ├───┤ ├───┤ ├───┤ │ │ │ │ │ 3 │ │ │ └───┘ └───┘ └───┘ └───┘ 空栈 栈底:3 栈顶:5 栈底:3 用数组实现栈
classArrayStack{constructor(capacity =10){this.items =newArray(capacity);// 底层数组this.top =-1;// 栈顶指针this.capacity = capacity;// 栈容量}// 入栈操作push(element){if(this.isFull()){thrownewError('栈已满');}this.top++;this.items[this.top]= element;returnthis;}// 出栈操作pop(){if(this.isEmpty()){thrownewError('栈为空');}const element =this.items[this.top];this.items[this.top]=undefined;// 清理引用this.top--;return element;}// 查看栈顶元素（不弹出）peek(){if(this.isEmpty()){returnnull;}returnthis.items[this.top];}// 判断栈是否为空isEmpty(){returnthis.top ===-1;}// 判断栈是否已满isFull(){returnthis.top ===this.capacity -1;}// 获取栈大小getsize(){returnthis.top +1;}// 清空栈clear(){this.items =newArray(this.capacity);this.top =-1;}}用链表实现栈
classListNode{constructor(value, next =null){this.value = value;this.next = next;}}classLinkedListStack{constructor(){this.top =null;// 栈顶节点this.length =0;// 栈长度}// 入栈操作push(element){// 创建新节点，指向原来的栈顶const newNode =newListNode(element,this.top);this.top = newNode;this.length++;returnthis;}// 出栈操作pop(){if(this.isEmpty()){thrownewError('栈为空');}const value =this.top.value;this.top =this.top.next;// 移动栈顶指针this.length--;return value;}peek(){if(this.isEmpty()){returnnull;}returnthis.top.value;}isEmpty(){returnthis.top ===null;}getsize(){returnthis.length;}clear(){this.top =null;this.length =0;}}数组栈 vs 链表栈
- 数组栈：内存连续，CPU缓存友好，访问速度快
- 链表栈：动态扩容，无容量限制，但内存不连续
- 实际选择：JavaScript 数组经过V8引擎优化，通常数组栈性能更好
栈的实际应用
应用1：函数调用栈模拟
classCallStackSimulator{constructor(){this.callStack =newArrayStack(50);this.currentDepth =0;this.maxDepth =0;}// 函数调用callFunction(funcName){const frame ={ funcName,timestamp: Date.now(),localVars:{}};this.callStack.push(frame);this.currentDepth++;this.maxDepth = Math.max(this.maxDepth,this.currentDepth); console.log(`调用: ${funcName} (深度: ${this.currentDepth})`);this.printStack();return frame;}// 函数返回returnFromFunction(){if(this.callStack.isEmpty()){ console.log('调用栈已空');returnnull;}const frame =this.callStack.pop();const duration = Date.now()- frame.timestamp;this.currentDepth--; console.log(`返回: ${frame.funcName} (耗时: ${duration}ms)`); console.log(`剩余深度: ${this.currentDepth}`);return frame;}}队列（Queue）与双端队列（Deque）
队列（Queue）的基本概念
队列 是一种先进先出（FIFO）的数据结构，就像排队买票，先来的人先服务。
队列的操作示意图
enqueue(3) enqueue(5) dequeue() → 3 ┌───┬───┐ → ┌───┬───┐ → ┌───┬───┐ → ┌───┬───┐ │ │ │ │ 3 │ │ │ 3 │ 5 │ │ │ 5 │ └───┴───┘ └───┴───┘ └───┴───┘ └───┴───┘ front rear front↑rear front rear↑ ↑front rear 双端队列（Deque）的基本概念
双端队列 允许在两端进行插入和删除操作，结合了栈和队列的特性。
双端队列的实现
classDeque{constructor(capacity =10){this.items =newArray(capacity);this.capacity = capacity;this.front =0;this.rear =0;this.count =0;}// 前端添加addFront(element){if(this.isFull()){this._resize();}this.front =(this.front -1+this.capacity)%this.capacity;this.items[this.front]= element;this.count++; console.log(`前端添加: ${element}, front: ${this.front}`);returnthis;}// 后端添加addRear(element){if(this.isFull()){this._resize();}this.items[this.rear]= element;this.rear =(this.rear +1)%this.capacity;this.count++; console.log(`后端添加: ${element}, rear: ${this.rear}`);returnthis;}// 前端删除removeFront(){if(this.isEmpty()){thrownewError('队列为空');}const element =this.items[this.front];this.items[this.front]=undefined;this.front =(this.front +1)%this.capacity;this.count--; console.log(`前端删除: ${element}, front: ${this.front}`);return element;}// 后端删除removeRear(){if(this.isEmpty()){thrownewError('队列为空');}this.rear =(this.rear -1+this.capacity)%this.capacity;const element =this.items[this.rear];this.items[this.rear]=undefined;this.count--; console.log(`后端删除: ${element}, rear: ${this.rear}`);return element;}// 查看前端peekFront(){if(this.isEmpty()){returnnull;}returnthis.items[this.front];}// 查看后端peekRear(){if(this.isEmpty()){returnnull;}const index =(this.rear -1+this.capacity)%this.capacity;returnthis.items[index];}// 扩容_resize(){const newCapacity =this.capacity *2;const newItems =newArray(newCapacity);// 复制元素到新数组for(let i =0; i <this.count; i++){const index =(this.front + i)%this.capacity; newItems[i]=this.items[index];}this.items = newItems;this.front =0;this.rear =this.count;this.capacity = newCapacity; console.log(`队列扩容: ${this.capacity /2} → ${newCapacity}`);}isEmpty(){returnthis.count ===0;}isFull(){returnthis.count ===this.capacity;}getsize(){returnthis.count;}}队列的实际应用
应用1：任务调度器
classTaskScheduler{constructor(){this.taskQueue =newCircularQueue(100);// 任务队列this.currentTask =null;this.taskId =0;this.isProcessing =false;}// 创建任务createTask(name, duration, priority =0){return{id:++this.taskId, name, duration,// 任务执行时间（毫秒） priority,// 优先级（数值越小优先级越高）status:'pending',createdAt: Date.now(),startedAt:null,completedAt:null};}// 添加任务到队列addTask(task){this.taskQueue.enqueue(task); console.log(`任务添加: ${task.name} (ID: ${task.id})`);this.printQueueStatus();// 如果没有正在处理的任务，开始处理if(!this.isProcessing){this.processNextTask();}}// 处理下一个任务asyncprocessNextTask(){if(this.taskQueue.isEmpty()){this.isProcessing =false; console.log('所有任务处理完成！');return;}this.isProcessing =true;this.currentTask =this.taskQueue.dequeue();this.currentTask.status ='processing';this.currentTask.startedAt = Date.now(); console.log(`\n开始处理任务: ${this.currentTask.name}`); console.log(`任务ID: ${this.currentTask.id}, 预计耗时: ${this.currentTask.duration}ms`);this.printQueueStatus();// 模拟任务执行awaitthis.executeTask(this.currentTask);// 任务完成this.currentTask.completedAt = Date.now();this.currentTask.status ='completed';const totalTime =this.currentTask.completedAt -this.currentTask.startedAt; console.log(`任务完成: ${this.currentTask.name}`); console.log(`实际耗时: ${totalTime}ms`);// 处理下一个任务setTimeout(()=>{this.processNextTask();},0);}// 模拟任务执行executeTask(task){returnnewPromise(resolve=>{setTimeout(()=>{resolve();}, task.duration);});}}树（Tree）的实现与应用
树的基本概念
树是一种分层的数据结构，由节点和边组成。每个节点有零个或多个子节点，没有父节点的节点称为根节点；没有子节点的节点称为叶子节点。
二叉树结构示意图
A(根节点)/ \ BC/ \ \ DEF/G术语解释：
- 根节点: A
- 叶子节点: E, F, G
- 深度: 节点G的深度是3
- 高度: 树的高度是3
- 子树: B、D、E、G构成一个子树
二叉树的实现
classTreeNode{constructor(value){this.value = value;// 节点值this.left =null;// 左子节点this.right =null;// 右子节点this.parent =null;// 父节点（可选）}// 判断是否为叶子节点isLeaf(){returnthis.left ===null&&this.right ===null;}// 判断是否有左子节点hasLeft(){returnthis.left !==null;}// 判断是否有右子节点hasRight(){returnthis.right !==null;}// 获取高度getHeight(){const leftHeight =this.left ?this.left.getHeight():0;const rightHeight =this.right ?this.right.getHeight():0;return Math.max(leftHeight, rightHeight)+1;}}二叉树遍历算法
classBinaryTree{constructor(){this.root =null;// 根节点}// 前序遍历：根 → 左 → 右preorderTraversal(callback){const result =[];this._preorder(this.root, callback, result);return result;}_preorder(node, callback, result){if(node ===null)return;// 访问当前节点if(callback)callback(node); result.push(node.value);// 遍历左子树this._preorder(node.left, callback, result);// 遍历右子树this._preorder(node.right, callback, result);}// 中序遍历：左 → 根 → 右（对二叉搜索树会得到有序序列）inorderTraversal(callback){const result =[];this._inorder(this.root, callback, result);return result;}_inorder(node, callback, result){if(node ===null)return;// 遍历左子树this._inorder(node.left, callback, result);// 访问当前节点if(callback)callback(node); result.push(node.value);// 遍历右子树this._inorder(node.right, callback, result);}// 后序遍历：左 → 右 → 根postorderTraversal(callback){const result =[];this._postorder(this.root, callback, result);return result;}_postorder(node, callback, result){if(node ===null)return;// 遍历左子树this._postorder(node.left, callback, result);// 遍历右子树this._postorder(node.right, callback, result);// 访问当前节点if(callback)callback(node); result.push(node.value);}// 层序遍历：按层级从上到下，从左到右levelOrderTraversal(callback){if(this.root ===null)return[];const result =[];const queue =newCircularQueue(100); queue.enqueue(this.root);while(!queue.isEmpty()){const node = queue.dequeue();// 访问当前节点if(callback)callback(node); result.push(node.value);// 将子节点加入队列if(node.left){ queue.enqueue(node.left);}if(node.right){ queue.enqueue(node.right);}}return result;}// 深度优先搜索（DFS）dfs(targetValue){returnthis._dfs(this.root, targetValue);}_dfs(node, targetValue){if(node ===null)returnnull;// 检查当前节点if(node.value === targetValue){return node;}// 搜索左子树const leftResult =this._dfs(node.left, targetValue);if(leftResult !==null){return leftResult;}// 搜索右子树returnthis._dfs(node.right, targetValue);}// 广度优先搜索（BFS）bfs(targetValue){if(this.root ===null)returnnull;const queue =newCircularQueue(100); queue.enqueue(this.root);while(!queue.isEmpty()){const node = queue.dequeue();// 检查当前节点if(node.value === targetValue){return node;}// 将子节点加入队列if(node.left){ queue.enqueue(node.left);}if(node.right){ queue.enqueue(node.right);}}returnnull;}}数据结构选择的关键因素
访问模式
- 随机访问：数组（O(1)）
- 顺序访问：链表、栈、队列
- 层级访问：树
操作频率
- 频繁插入/删除开头：链表
- 频繁插入/删除两端：双端队列
- 频繁随机访问：数组
内存考虑
- 内存连续：数组（缓存友好）
- 内存分散：链表（无扩容成本）
- 动态大小：链表、树
结语
本文讲解了栈、队列和树的实现与应用，理解这些数据结构，不仅能帮助我们在面试中表现出色，更能让我们在实际开发中写出更高效、更可靠的代码。对于文章中错误的地方或者有任何问题，欢迎在评论区留言讨论！
