1. 项目概述从生活场景到代码世界最近在带新人发现很多朋友一听到“数据结构”四个字就头大觉得这是科班出身、算法竞赛选手才需要钻研的高深学问。其实不然数据结构就藏在我们每天的生活里。今天我们不谈枯燥的理论就从两个最贴近生活的例子——“食堂排队打饭”和“叠放盘子”——来聊聊JavaScript中的栈Stack和队列Queue。你会发现理解它们不仅能让你写出更优雅的代码更是深入理解JavaScript运行机制比如函数调用的一把钥匙。无论你是刚入门的前端新手还是想巩固基础的开发者这篇内容都能帮你把这两个核心概念吃得透透的。简单来说栈是一种“后进先出”LIFO: Last In, First Out的数据结构就像一摞盘子你总是取最上面的那个最后放上去的。而队列是一种“先进先出”FIFO: First In, First Out的数据结构正如食堂排队讲究先来后到后来的人只能排在队尾。在JavaScript中虽然没有内置的Stack和Queue类但用数组Array或对象Object来模拟它们非常简单而其应用却无处不在从浏览器历史记录的前进后退栈到异步任务的处理如回调队列、微任务队列再到复杂的算法实现都离不开它们的身影。2. 核心概念深度解析栈与队列的底层逻辑2.1 栈后进先出的“叠盘子”模型栈的核心操作只有两个入栈push和出栈pop它们都发生在栈的同一端我们称之为“栈顶”。你可以想象成向一个桶里放网球你只能从桶口放入或取出最先放进去的球总是在最底部最后才能被拿出来。在JavaScript中数组天然支持栈的行为// 用数组模拟一个栈 let stack []; // 入栈操作 stack.push(盘子A); // 栈底 stack.push(盘子B); stack.push(盘子C); // 栈顶 console.log(stack); // 输出: [盘子A, 盘子B, 盘子C] // 出栈操作 let topItem stack.pop(); // 移除并返回‘盘子C’ console.log(topItem); // 输出: ‘盘子C’ console.log(stack); // 输出: [盘子A, 盘子B]盘子B成为新的栈顶为什么是“后进先出”这种设计源于栈要解决的典型问题需要记录一系列操作并且最新最近的操作拥有最高的优先级需要被最先处理或撤销。一个经典的例子就是“撤销”功能。你每做一个编辑操作这个操作就被“压入”历史栈当你点击撤销时最近的一次操作被“弹出”并回滚。注意虽然数组的push/pop组合是模拟栈的完美搭档但务必注意数组的unshift在头部插入和shift从头部移除操作对于数组来说性能开销较大因为需要移动所有后续元素的索引。所以严格用push和pop来操作栈的“顶部”是保证效率的关键。2.2 队列先进先出的“排队”模型队列的核心操作也是两个入队enqueue和出队dequeue。入队在队尾进行出队在队头进行完美模拟了“先来先服务”的公平原则。用JavaScript数组模拟队列时我们需要小心选择方法// 方法一使用 push入队 和 shift出队 let queue []; // 入队 queue.push(顾客A); // 队头 queue.push(顾客B); queue.push(顾客C); // 队尾 console.log(queue); // 输出: [顾客A, 顾客B, 顾客C] // 出队 let servedCustomer queue.shift(); // 移除并返回‘顾客A’ console.log(servedCustomer); // 输出: ‘顾客A’ console.log(queue); // 输出: [顾客B, 顾客C]顾客B成为新的队头为什么是“先进先出”队列管理的是需要按序处理的任务流。想象一下JavaScript中的异步任务队列Callback Queue或Task Queue。当一个setTimeout定时器到期时它的回调函数会被放入这个队列。事件循环Event Loop会不断地从队列的头部取出最早进入的任务推入调用栈执行。这确保了异步任务按照它们被“安排”的顺序依次执行避免了混乱。实操心得对于性能要求高的场景频繁使用数组的shift()方法出队可能导致性能问题因为它需要重新索引数组中的所有剩余元素。一个更高效的实现是使用“指针”或自定义队列类避免数组元素的整体移动。我们会在后续实现部分详细探讨。2.3 栈与队列的对比与应用场景抉择理解了两者的区别关键在于知道什么时候该用谁。这里有一个简单的决策表特性栈 (Stack)队列 (Queue)数据顺序后进先出 (LIFO)先进先出 (FIFO)核心操作push压栈,pop弹栈enqueue入队,dequeue出队类比叠盘子、浏览器历史记录、撤销操作排队、打印任务队列、消息缓冲典型应用函数调用栈、括号匹配、深度优先搜索(DFS)事件循环任务队列、广度优先搜索(BFS)、缓存淘汰策略如FIFO缓存JavaScript模拟Array.push()/Array.pop()Array.push()/Array.shift()(或自定义类)如何选择问自己一个问题你处理的数据是否需要保留“历史”或“路径”的上下文并且最近的上下文最重要如果是选栈。例如解析嵌套结构HTML标签、JSON括号。 如果数据项之间是平等的需要公平地按到达顺序处理如果是选队列。例如处理用户请求、管理下载任务。3. 从零实现打造高性能的栈与队列类虽然用数组模拟很方便但为了更清晰地封装概念、优化性能特别是队列以及应对面试自己实现一遍是很有必要的。3.1 基于数组的栈实现这是一个基础但完整的栈类实现它隐藏了底层数组的细节只暴露栈的标准接口。class Stack { constructor() { this.items []; } // 入栈 push(element) { this.items.push(element); } // 出栈并返回被移除的元素 pop() { if (this.isEmpty()) { return undefined; // 或可以抛出错误 } return this.items.pop(); } // 查看栈顶元素不移除 peek() { if (this.isEmpty()) { return undefined; } return this.items[this.items.length - 1]; } // 判断栈是否为空 isEmpty() { return this.items.length 0; } // 返回栈的大小 size() { return this.items.length; } // 清空栈 clear() { this.items []; } // 打印栈内容辅助方法 print() { console.log(this.items.toString()); } } // 使用示例 const myStack new Stack(); myStack.push(10); myStack.push(20); console.log(myStack.peek()); // 20 console.log(myStack.pop()); // 20 console.log(myStack.size()); // 1实现要点封装性内部数组this.items是私有的虽然ES6 Class没有真正的私有字段但约定俗成以下划线开头或使用Symbol/WeakMap可以模拟。外部只能通过定义好的方法进行操作。健壮性在pop和peek方法中检查栈是否为空避免在空栈上操作导致错误。时间复杂度所有操作push, pop, peek, isEmpty, size的时间复杂度都是O(1)非常高效。3.2 基于对象的高效队列实现如前所述用数组的shift()实现出队效率不高。我们可以用对象或Map配合两个指针head和tail来实现一个时间复杂度均为O(1)的队列。class Queue { constructor() { this.items {}; // 用对象存储元素 this.head 0; // 指向队头的索引 this.tail 0; // 指向下一个入队位置的索引 } // 入队 enqueue(element) { this.items[this.tail] element; this.tail; } // 出队 dequeue() { if (this.isEmpty()) { return undefined; } const item this.items[this.head]; delete this.items[this.head]; // 释放内存 this.head; // 可选定期重置指针以回收空间当队列大部分时间为空时 if (this.isEmpty()) { this.head 0; this.tail 0; } return item; } // 查看队头元素 peek() { if (this.isEmpty()) { return undefined; } return this.items[this.head]; } isEmpty() { return this.tail - this.head 0; } size() { return this.tail - this.head; } clear() { this.items {}; this.head 0; this.tail 0; } print() { const result []; for (let i this.head; i this.tail; i) { result.push(this.items[i]); } console.log(result.toString()); } } // 使用示例 const myQueue new Queue(); myQueue.enqueue(任务1); myQueue.enqueue(任务2); console.log(myQueue.peek()); // ‘任务1’ console.log(myQueue.dequeue()); // ‘任务1’ console.log(myQueue.size()); // 1为什么这个实现更高效数组shift()移除第一个元素后需要将后面所有元素的索引向前移动一位时间复杂度为O(n)。对象指针dequeue()只是将head指针向后移动一位并删除原队头元素的属性引用时间复杂度为O(1)。虽然delete操作在某些引擎下可能较慢但整体在元素数量大时远优于数组shift。注意事项这个实现有一个潜在问题随着不断入队和出队head和tail会无限增长this.items对象中可能会残留大量已出队元素的“空”属性键虽然我们用了delete。上面的代码在队列清空时重置了指针这是一种简单的优化。更复杂的实现可以考虑使用循环队列Circular Queue来复用存储空间。4. 核心应用场景实战函数调用栈与任务队列理解了基本操作和实现我们来看看它们在JavaScript引擎中扮演的关键角色。这是面试中高频的考点也是理解异步编程的基石。4.1 函数调用栈代码执行的“上下文管理器”当你执行一个JavaScript函数时引擎会做以下几件事创建一个该函数的“执行上下文”包含变量对象、作用域链、this值等信息。将这个上下文压入push调用栈Call Stack顶部。执行函数体内的代码。函数执行完毕后将其上下文弹出pop调用栈控制权交还给栈中的下一个上下文通常是调用它的函数。function first() { console.log(第一个函数开始); second(); // 调用 second console.log(第一个函数结束); } function second() { console.log(第二个函数开始); third(); // 调用 third console.log(第二个函数结束); } function third() { console.log(第三个函数执行); } first(); // 调用 first console.log(全局执行完毕);执行过程与栈的变化脚本开始全局上下文入栈。执行first()first的上下文入栈。first内部执行second()second的上下文入栈压在first之上。second内部执行third()third的上下文入栈压在second之上。third执行完毕其上下文出栈。控制权回到second继续执行console.log(‘第二个函数结束’)然后second上下文出栈。控制权回到first继续执行console.log(‘第一个函数结束’)然后first上下文出栈。最后执行全局的console.log(‘全局执行完毕’)全局上下文最终出栈页面关闭时。这个过程完美诠释了栈的LIFO特性最后被调用的函数third最先执行完毕并出栈。栈溢出Stack Overflow如果函数递归调用没有正确的终止条件就会不断创建新的执行上下文并入栈直到超过浏览器或Node.js环境分配给调用栈的最大内存限制导致“栈溢出”错误。// 危险的递归 function infiniteRecursion() { infiniteRecursion(); // 无限调用自己 } // infiniteRecursion(); // 执行这行会报错Maximum call stack size exceeded4.2 事件循环与任务队列异步代码的“调度中心”JavaScript是单线程的但又能处理异步操作如网络请求、定时器这背后的功臣就是事件循环Event Loop和任务队列Task Queue 也叫回调队列 Callback Queue。当一个异步操作如setTimeout,fetch,DOM事件完成时它的回调函数不会立即执行而是被放入一个任务队列中等待。事件循环持续监控两个地方调用栈和任务队列。事件循环的工作流程执行调用栈中的所有同步任务这可能会产生新的异步任务并将其回调注册到队列。当调用栈为空时事件循环会去检查任务队列。如果任务队列中有等待的回调事件循环会将其出队dequeue并压入push调用栈开始执行。重复步骤1-3。console.log(脚本开始); // 同步任务1 setTimeout(() { console.log(setTimeout回调); // 异步回调 }, 0); console.log(脚本结束); // 同步任务2 // 输出顺序 // 脚本开始 // 脚本结束 // setTimeout回调为什么setTimeout0秒的回调最后才执行console.log(‘脚本开始’)入栈执行后出栈。遇到setTimeout浏览器/Node.js的定时器模块会处理它并在0毫秒实际上是至少4ms根据HTML5规范的最小延迟后将其回调函数放入任务队列。注意是放入队列不是立即执行。console.log(‘脚本结束’)入栈执行后出栈。此时调用栈为空。事件循环检查任务队列发现有一个回调将其出队并压入调用栈执行于是输出‘setTimeout回调’。这个过程体现了队列的FIFO特性先被放入任务队列的回调会先被事件循环取出执行。深入理解现代JavaScript引擎中实际上有多个具有不同优先级的队列如微任务队列Microtask Queue存放Promise.then、MutationObserver等回调和宏任务队列Macrotask Queue/Task Queue存放setTimeout、setInterval、I/O、UI渲染等回调。事件循环在每一次循环中会先清空整个微任务队列再从宏任务队列中取一个任务执行。这是另一个重要且常考的知识点。5. 算法与问题实战栈与队列的经典应用掌握了原理我们通过几个经典的算法问题来巩固栈和队列的应用这些都是面试和日常开发中可能会遇到的。5.1 使用栈实现括号匹配问题给定一个只包含(){}[]的字符串判断括号是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合且左括号必须以正确的顺序闭合。思路遍历字符串遇到左括号就压栈遇到右括号就检查栈顶的左括号是否与之匹配。如果匹配则弹出栈顶如果不匹配或栈为空则无效。最后如果栈为空说明所有括号都正确匹配。function isValidParentheses(s) { const stack []; const map { (: ), [: ], {: } }; for (let char of s) { if (map[char]) { // 是左括号入栈 stack.push(char); } else { // 是右括号 // 取出栈顶的左括号 const top stack.pop(); // 如果栈为空或栈顶左括号不匹配当前右括号 if (!top || map[top] ! char) { return false; } } } // 最后栈必须为空才有效 return stack.length 0; } // 测试 console.log(isValidParentheses(()[]{})); // true console.log(isValidParentheses(([)])); // false console.log(isValidParentheses({[]})); // true避坑技巧在判断右括号时一定要先检查栈是否为空!top。如果栈为空却遇到了右括号那肯定是无效的例如输入)。使用对象字面量建立括号映射关系比用if-else或switch判断更简洁高效。5.2 使用队列实现“击鼓传花”游戏模拟问题模拟“击鼓传花”游戏。给定一个参与者名字数组和一个数字num从第一个人开始报数每数到num的人被淘汰剩下的人继续从1开始数直到只剩一人。返回最后剩下的人的名字。思路这是一个典型的循环队列应用。将所有人入队。然后开始循环从队头出队一个人并计数。如果计数没到num则把这个人再次入队到队尾相当于安全传递如果计数到了num则这个人被淘汰不再入队重置计数。重复直到队列中只剩一人。function hotPotato(nameList, num) { const queue new Queue(); // 使用我们之前实现的Queue类或用数组模拟 // 初始化队列 for (let name of nameList) { queue.enqueue(name); } while (queue.size() 1) { // 传递 num-1 次 for (let i 0; i num - 1; i) { // 队头的人安全出队后立刻入队到队尾 queue.enqueue(queue.dequeue()); } // 第 num 个人被淘汰 const eliminated queue.dequeue(); console.log(${eliminated} 被淘汰了。); } // 最后剩下的人是胜者 const winner queue.dequeue(); console.log(胜利者是${winner}); return winner; } // 使用数组模拟队列的简化版 function hotPotatoSimple(nameList, num) { const queue [...nameList]; // 将数组作为队列 while (queue.length 1) { for (let i 0; i num - 1; i) { // 将队头元素移到队尾 queue.push(queue.shift()); } // 淘汰队头元素 const eliminated queue.shift(); console.log(${eliminated} 被淘汰了。); } const winner queue.shift(); console.log(胜利者是${winner}); return winner; } // 测试 const names [John, Jack, Camila, Ingrid, Carl]; hotPotatoSimple(names, 7); // 传入不同的num结果不同算法要点循环num-1次的安全传递操作queue.enqueue(queue.dequeue())是模拟“传递”动作的关键。这个算法的时间复杂度是O(n * num)其中n是初始人数。因为最坏情况下num很大每个人被传递多次后才淘汰。这个问题是著名的“约瑟夫环Josephus problem”的一个变体。5.3 使用栈实现十进制转二进制这是一个展示栈“反转顺序”特性的好例子。十进制转二进制的方法是“除2取余逆序排列”。栈的LIFO特性正好可以用来实现“逆序”。function decimalToBinary(decNumber) { if (decNumber 0) return 0; const remStack new Stack(); let number decNumber; let binaryString ; while (number 0) { // 求余数压入栈 const rem Math.floor(number % 2); remStack.push(rem); // 更新number为商 number Math.floor(number / 2); } // 将栈中的余数依次弹出连接成字符串 while (!remStack.isEmpty()) { binaryString remStack.pop().toString(); } return binaryString; } // 测试 console.log(decimalToBinary(10)); // 输出: 1010 console.log(decimalToBinary(233)); // 输出: 11101001 console.log(decimalToBinary(0)); // 输出: 0扩展思考这个方法可以轻松扩展到转换为任意进制2~36。只需要将除数2和求余后的数字到字符的映射关系改一下即可。栈在这里的作用就是充当一个临时容器保存计算过程中的中间结果余数并在最后以相反的顺序输出省去了我们手动反转数组的步骤。6. 性能考量、常见陷阱与进阶话题在实际项目中应用栈和队列时有一些性能细节和常见错误需要留意。6.1 数据结构选择与性能陷阱数组 vs 自定义队列简单场景/数据量小使用数组push/shift完全没有问题代码最简洁。高频出队/数据量大务必使用我们实现的那种基于对象或Map的双指针队列或者使用现成的优化库如p-queue。数组shift()在V8引擎中对于大型数组如数万个元素的性能下降是显著的。栈的访问限制栈只允许在栈顶操作。这意味着你不能也不应该随机访问栈中间的元素。如果你发现自己经常需要访问或修改栈中间的数据那么栈可能不是最适合的数据结构可以考虑数组或链表。内存管理对于自定义的对象队列实现虽然dequeue时使用了delete但head指针之前的索引空间在逻辑上被“废弃”了。在极端的长生命周期、高频入队出队场景下这可能造成内存对象中残留大量未使用的属性键。我们的代码在队列清空时重置了指针是一种缓解方法。更彻底的方案是实现一个循环队列Circular Queue当tail到达存储末尾时可以绕回开头使用head之前释放的空间。6.2 JavaScript运行时的特殊队列微任务与宏任务这是理解现代JavaScript异步编程的关键。除了之前提到的回调队列宏任务队列还有一个优先级更高的微任务队列。执行顺序规则执行一个宏任务如一段script代码、setTimeout回调。执行过程中产生的微任务如Promise.then、await后面的代码、MutationObserver会被添加到微任务队列。当前宏任务执行完毕立即执行当前微任务队列中的所有任务清空微任务队列。进行UI渲染如果需要。从宏任务队列中取下一个任务开始新的一轮循环。console.log(script start); // 宏任务1 setTimeout(() { console.log(setTimeout); // 宏任务2的回调 }, 0); Promise.resolve() .then(() { console.log(promise1); // 微任务1 }) .then(() { console.log(promise2); // 微任务2 }); console.log(script end); // 宏任务1继续 // 输出顺序 // script start // script end // promise1 // promise2 // setTimeout为什么Promise比setTimeout先执行因为Promise.then的回调是微任务而setTimeout的回调是宏任务。在第一个宏任务整体script执行完后引擎会清空微任务队列打印promise1, promise2然后才会从宏任务队列中取出下一个任务setTimeout的回调执行。实操心得在编写异步代码时尤其是混合使用了Promise、async/await和setTimeout时一定要在脑子里过一遍事件循环、宏任务、微任务的顺序。这是解决很多“为什么这段代码不按我写的顺序执行”问题的关键。一个常见的坑是在一个宏任务中同步地修改了DOM然后又期望在同一个宏任务中立刻获取到更新后的DOM计算样式这时可能需要利用微任务如Promise.resolve().then()或宏任务如setTimeout(fn, 0)来确保DOM已渲染。6.3 栈与队列的变体与应用扩展双端队列Deque结合了栈和队列的特性允许从两端进行插入和删除。JavaScript数组本身就近似一个双端队列push/pop/unshift/shift。可用于实现滑动窗口算法、回文检查等。优先队列Priority Queue元素出队的顺序不是由入队时间决定而是由优先级决定。通常用“堆Heap”来实现。Node.js的async/await或某些任务调度器中可能会有类似优先队列的概念。单调栈Monotonic Stack栈中的元素保持单调递增或递减。常用于解决“下一个更大元素”、“柱状图中最大矩形”等算法问题。这是栈的一种高级用法通过维护单调性能在O(n)时间复杂度内解决一些看似复杂的问题。消息队列Message Queue在分布式系统或复杂前端应用中如React的Fiber架构队列常用于管理消息或更新任务确保它们被有序、可靠地处理。虽然底层原理还是队列但通常会附加持久化、重试、确认等复杂机制。理解栈和队列绝不仅仅是学会两个数据结构的API。它们是计算机科学中最基础、最强大的抽象之一是构建更复杂系统如运行时环境、算法、框架的基石。从最简单的数组模拟到深入V8引擎的事件循环再到解决实际的算法问题这条学习路径清晰地展示了如何将抽象概念转化为解决实际问题的能力。下次当你写递归函数、处理异步回调或者设计一个任务处理器时不妨想想这里用的是栈的思想还是队列的模型想明白了你的代码设计会更有底气。