JavaScript数据结构深度解析：栈、队列与树的实现与应用

Ne0inhk

— 9 min read

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)）
  • 顺序访问：链表、栈、队列
  • 层级访问：树

操作频率

  • 频繁插入/删除开头：链表
  • 频繁插入/删除两端：双端队列
  • 频繁随机访问：数组

内存考虑

  • 内存连续：数组（缓存友好）
  • 内存分散：链表（无扩容成本）
  • 动态大小：链表、树

结语

本文讲解了栈、队列和树的实现与应用，理解这些数据结构，不仅能帮助我们在面试中表现出色，更能让我们在实际开发中写出更高效、更可靠的代码。对于文章中错误的地方或者有任何问题，欢迎在评论区留言讨论！

Read more

Llama-Factory是否支持Transformer-XL结构？

Llama-Factory 是否支持 Transformer-XL 结构？ 在当前大语言模型（LLM）快速迭代的背景下，微调已成为将通用预训练模型适配到垂直场景的核心手段。随着 LoRA、QLoRA 等参数高效微调技术的普及，开发者不再需要从零搭建训练流水线，而是借助如 LLama-Factory 这类“一站式”框架，实现低门槛、高效率的模型定制。 这类工具之所以流行，关键在于其对主流架构的高度抽象与统一支持——无论是 LLaMA、Qwen 还是 ChatGLM，用户只需指定模型路径和配置参数，即可启动完整的微调流程。但当面对一些早期或非典型的模型结构时，比如 Transformer-XL，问题就变得复杂了：这些模型是否也能被无缝接入？它们的设计特性是否会打破现有框架的假设前提？ 要回答这个问题，不能只看官方文档有没有列出某个名字，而必须深入理解 LLama-Factory 的底层机制，以及 Transformer-XL 本身的架构特点。 LLama-Factory 并不是一个独立的模型实现库，它本质上是建立在 Hugging Face Transformers 和

By Ne0inhk
从论文到实践：Stable Diffusion模型一键生成高质量AI绘画

从论文到实践：Stable Diffusion模型一键生成高质量AI绘画

🏡作者主页：点击！  🤖编程探索专栏：点击！ ⏰️创作时间：2024年12月24日10点02分 神秘男子影,   秘而不宣藏。 泣意深不见, 男子自持重,    子夜独自沉。  AI绘画一键生成美图-变成画家 本地部署SD模型，一键即可生成自己想要绘制的图画，本文包括论文原理讲解和代码复现 论文讲解 论文题目：High-Resolution Image Synthesis with Latent Diffusion Models（基于潜在扩散模型的高分辨率图像合成） 论文被计算机视觉顶会CVPR 2022收录 Stable diffusion是一个基于Latent Diffusion Models（潜在扩散模型，LDMs）的文图生成（text-to-image）模型。它建立在自注意力机制和扩散过程的基础上。它的设计灵感来自于扩散过程模型（Diffusion Models），这些模型在自然图像建模领域取得了巨大成功。 Stable Diffusion通过一系列的扩散步骤来生成图像。在每一步中，模型逐渐“扩散”图像，从含有较少信息的噪声开始，到包含更多细节的图像。

By Ne0inhk
GitHub Copilot 在 VS Code 上的终极中文指南：从安装到高阶玩法

GitHub Copilot 在 VS Code 上的终极中文指南：从安装到高阶玩法

GitHub Copilot 在 VS Code 上的终极中文指南：从安装到高阶玩法 前言 GitHub Copilot 作为 AI 编程助手，正在彻底改变开发者的编码体验。本文将针对中文开发者，深度解析如何在 VS Code 中高效使用 Copilot，涵盖基础设置、中文优化、核心功能详解，并提供多个实战场景配置模板。 一、安装与配置全流程 1. 完整安装步骤 1. 扩展安装 * 打开 VS Code → 点击左侧活动栏的 Extensions 图标（或按 Ctrl+Shift+X） * 搜索框输入 GitHub Copilot → 点击安装按钮 2. 账号授权 * 安装完成后右下角弹出通知 → 点击 Sign in

By Ne0inhk
虚拟世界的AI魔法：AIGC引领元宇宙创作革命

虚拟世界的AI魔法：AIGC引领元宇宙创作革命

云边有个稻草人-ZEEKLOG博客——个人主页 热门文章_云边有个稻草人的博客-ZEEKLOG博客——本篇文章所属专栏 ~ 欢迎订阅~ 目录 1. 引言 2. 元宇宙与虚拟世界概述 2.1 什么是元宇宙？ 2.2 虚拟世界的构建 3. AIGC在元宇宙中的应用 3.1 AIGC生成虚拟世界环境 3.2 AIGC生成虚拟角色与NPC 3.3 AIGC创造虚拟物品与资产 4. AIGC在虚拟世界与元宇宙的技术实现 4.1 生成式对抗网络（GANs）在元宇宙中的应用 4.2 自然语言处理（NLP）与虚拟角色的对话生成 4.3 计算机视觉与物理引擎 5. 持续创新：AIGC与元宇宙的未来趋势 5.1 个人化与定制化体验 5.

By Ne0inhk