从"冰柜里的雪糕"到"候车室的长队"——栈与队列的优雅哲学

引言：程序的骨骼，藏在最简单的结构里

如果你问我，算法世界里最容易被忽视却又无处不在的东西是什么？我会毫不犹豫地回答：栈和队列。

它们不像二叉树那样枝繁叶茂，不像图那样纵横交错，甚至不如动态规划那般让人望而生畏。它们只是两个"操作受限的数组"——是的，你没有看错，就是那个你第一天学编程就会用的数组 ——只不过被加上了几条温柔的"规矩"，便脱胎换骨，成为支撑函数调用、任务调度、编译器解析乃至操作系统运转的基石。

这不禁让人想起一句古老的箴言：约束不是自由的敌人，而是优雅的起点。

---

第一章：数组——一个被低估的"万能积木"

在谈论栈和队列之前，我们必须先向它们的"母体"——数组——致以足够的敬意。

数组是什么？它是内存中一片"连续的土地"，每一块都标好了门牌号（索引），你可以在 O(1)
的时间内敲开任意一扇门。这种"开箱即用、下标直达"的爽快感，是数组最大的魅力所在。正如代码里那一行行朴素的声明——const arr = [1, 2]——它简单到让人忘记思考。

然而，世界从来不是只有"读取"这一种操作。当我们需要增加或删除元素时，数组的另一面便显露出来：

• push：往数组末尾追加，乍看无懈可击，但当 arr.length 触及底层 capacity
  的天花板时，数组必须整体扩容——这意味着重新申请一块更大的连续内存，再把原有元素悉数搬运过去。这是一次隐性的、但不可忽视的性能代价。
• unshift：往数组开头插入，从内存视角来看，是一场"全体搬家"——每一个后续元素都必须向后挪动一格，为新人腾出位置。当数组长度为 n 时，最坏情况下需要挪动 n 个元素。
• splice：数组的"瑞士军刀"，集增、删、改于一身——arr.splice(start_index, delete_count, item1, item2, …)——它在 start_index 处删除 delete_count
  个元素，再插入新的元素。本质上，这是一次"剪切+替换"手术，同样伴随着元素的批量位移。

▎ 📝 动手试一试：打开 1.js，运行 arr.splice(1, 0, 3) ——在索引 1 处删除 0 个、插入 3。数组从 [1, 2] 变成了 [1, 3, 2]。再运行 arr.splice(1, 1)，3 被剔除，恢复为 [1,
▎ 2]。短短两行代码，却暗藏了 O(n) 的时间复杂度。

更重要的是，数组的增删操作都不是纯函数——它们直接修改原数组。这在函数式编程的语境下是需要警惕的。

---

第二章：栈——冰柜里那根被遗忘的雪糕

理解了数组的"全能"之后，我们主动给它戴上镣铐，便创造出了栈（Stack）。

栈的规则只有一条，却铁面无情：所有操作只能在栈顶进行。你可以把栈想象成一个冰柜，你只能从最上层取雪糕——放在最下面的那根东北大板，必须等上面的可爱多和冰工厂都被拿走之
后，才能重见天日。这就是 LIFO（Last In First Out，后进先出）。

在代码层面，栈就是一个只能用 push（入栈）和 pop（出栈）的数组。读取栈顶元素有一个约定俗成的操作叫 peek——在 JS 里就是 stack[stack.length - 1]。

让我们品读 2.js 中的这段出栈代码：

const stack = [];
stack.push(“dongbeidaban”);
stack.push(“keaiduo”);
stack.push(“binggongchang”);

while (stack.length > 0) {
const top = stack[stack.length - 1]; // peek
console.log(“出栈的:”, top);
stack.pop(); // pop
}

运行结果是什么？“冰工厂"先出来，然后"可爱多”，最后才是"东北大板"——后进先出，铁律如山。当循环结束，栈已经空空如也。

这种看似简单的"受限"，蕴含着深刻的适用场景：

• 函数调用栈：当 A 调用 B，B 调用 C，C 执行完毕后必须返回 B，B 返回 A。完美的 LIFO。
• 括号匹配：编译器遇到 { 就入栈，遇到 } 就检查栈顶是否匹配——不匹配？报错。
• 浏览器的后退按钮：你访问过的页面被压入栈中，点"后退"就是一次 pop。

---

第三章：队列——请排队，先来后到

如果说栈是"后来者居上"的冰柜，那么**队列（Queue）**就是"先来先服务"的候车室。

队列的规矩同样简洁：只能在队尾入队，只能在队首出队。这就是 FIFO（First In First Out，先进先出）。

在 3.js 中，我们用数组模拟了一个队列：

const queue = [];
queue.push(“dongbeidaban”); // 入队
queue.push(“keaiduo”); // 入队
queue.push(“binggongchang”); // 入队

while (queue.length > 0) {
const front = queue[0]; // 查看队首
console.log(“出队的:”, front);
queue.shift(); // 出队
}

这一次，输出顺序截然不同：“东北大板"第一个出来，然后是"可爱多”，最后是"冰工厂"——先来的先走，后来的后走，公平公正，童叟无欺。

队列的现实映射俯拾皆是：

• 打印机任务队列：先提交的文档先打印。
• 消息队列：Kafka、RabbitMQ 等中间件的核心思想。
• BFS（广度优先搜索）：算法世界里，队列是层序遍历的灵魂。

---

第四章：链表——数组的"镜像对手"

如果数组是内存世界里的"联排别墅"（连续存储），那么链表就是散落在城市各处的"独栋小院"——每个节点之间不连续，通过 指针（next） 串联起来。

在 JS 中，一个链表节点不过是一个对象字面量：

{
val: 1,
next: {
val: 2,
next: null
}
}

头节点 head 是访问一切的起点——你要找到任何一个元素，都必须从头开始，沿着 next 指针逐一遍历，直到目标为止。尾节点的 next 指向 null，象征着链表的终点。

增与删：一场指针的魔术

链表的增删操作，本质上是对 next 指针的重新编织：

• 插入节点：找到目标节点的前驱节点 → 将前驱节点的 next 指向新节点 → 将新节点的 next
  指向原目标节点。三步走，干净利落。但切记——“不要坐过站”，如果先丢失了前驱节点对目标节点的引用，后面的链条就断了。
• 删除节点：找到目标节点的前驱节点 → 将前驱节点的 next 改为目标节点的后继节点 → 将目标节点的 next 置为 null。被删除的节点从此被链路抛弃，等待垃圾回收。

数组 vs 链表：没有银弹，只有取舍

这是一场延续了几十年的经典对决，答案从来不是非黑即白：

┌──────────────────┬────────────────────┬────────────────┐
│ 维度 │ 数组 │ 链表 │
├──────────────────┼────────────────────┼────────────────┤
│ 访问（按索引） │ O(1)，下标直达 │ O(n)，从头遍历 │
├──────────────────┼────────────────────┼────────────────┤
│ 增删（已知位置） │ O(n)，元素需要移动 │ O(1)，只改指针 │
├──────────────────┼────────────────────┼────────────────┤
│ 内存分布 │ 连续，扩容有开销 │ 离散，每次申请 │
├──────────────────┼────────────────────┼────────────────┤
│ 缓存友好度 │ 高（连续内存） │ 低（跳跃访问） │
└──────────────────┴────────────────────┴────────────────┘

选择策略：数据规模小、频繁遍历和随机访问？用数组。数据规模大、频繁增删？用链表。

还有一个不容忽视的细节：当你假设数组长度为 n 时，因删除或增加操作导致需要移动的元素数量，随着 n 的增大而线性增长——这就是 O(n) 线性时间复杂度的来源。

▎ ⚠️ JS 的"伪数组"陷阱：在 JavaScript 中，数组未必是真正的数组。如果数组中每一项类型一致（例如全是整数），V8
▎ 引擎会将其存储为一段连续内存的"纯数组"。但如果类型混杂（数字、字符串、对象混在一起），底层会用 哈希表
▎ 来分配内存——此时所谓的"数组"，已经丧失了连续内存的优势，沦为披着数组外衣的哈希表。所以，当你追求极致性能时，请保持数组元素的类型一致。

---

终章：约束之美，结构之魂

回到开篇那句话：栈和队列只是操作受限的数组。

但正是这"受限"二字，赋予了它们独特的语义和力量。你不需要检查数组中间的元素是否被意外篡改，因为栈根本就不给你碰中间的机会。你不需要担心"后来者插队"的问题，因为队列的
规则天然保证了公平。

古人云"大巧若拙"。栈和队列没有炫技的姿势，没有眼花缭乱的 API，它们只是两个被精心约束的线性结构，却在计算机科学的每一个角落默默运转——从你敲下 console.log()
那一刻，函数调用栈就在为你服务；从你访问这个网页的那一刻，网络请求就在队列中排队等候。

所以，下一次当你打开冰柜拿雪糕，或者在火车站排队检票时，不妨会心一笑——你手里握着的，正是数据结构世界里最优雅的两条规则。