栈与队列
04-数据结构与算法2026/11/14
栈和队列的差别只有一条出队规则，但这条规则决定了调用栈会溢出、事件循环分微宏任务、撤销重做必须倒着来。
翻浏览器的前进后退、编辑器里连按 Ctrl+Z、Promise 回调比 setTimeout 先执行，背后是同一个判断：这个东西该后进先出，还是先进先出。选错一条出队规则，一万条数据就能把页面卡住。
LIFO 与 FIFO
| 维度 | 栈（LIFO） | 队列（FIFO） |
|---|---|---|
| 出队位置 | 同一端进出，栈顶 | 一端进、另一端出 |
| 语义 | 最近的优先处理 | 最早的优先处理 |
| 典型实现 | 数组 push / pop | 数组 + 头指针、链表 |
| 真实用途 | 调用栈、撤销重做、括号匹配、DFS | 任务队列、BFS、消息队列、缓冲区 |
| 前端对应 | 函数调用、路由历史 | 宏任务队列、微任务队列、事件派发 |
用数组实现栈
栈是数组最贴合的场景，push 和 pop 都在尾部，均摊 O(1)：
class Stack {
constructor() { this.items = []; }
push(x) { this.items.push(x); }
pop() { return this.items.pop(); }
peek() { return this.items[this.items.length - 1]; }
get size() { return this.items.length; }
}
队列的 O(n) 陷阱
用 push 入队、shift 出队写起来最顺手，但 shift 要删掉下标 0 并让后面所有元素前移一位，是实打实的 O(n)。循环里对一万条数据做 shift，就是五千万次搬移：
const q = [];
for (let i = 0; i < 10000; i++) q.push(i);
while (q.length) q.shift(); // 每次 O(n)，整体 O(n²)
正确做法是用头指针记录出队位置，或者用 Map 以自增下标为键。头指针版不搬移，但数组本身不会收缩，需要定期截断：
class Queue {
constructor() { this.arr = []; this.head = 0; }
enqueue(v) { this.arr.push(v); }
dequeue() {
if (this.head === this.arr.length) return undefined;
const v = this.arr[this.head++];
// 头指针越过一半且长度可观时压缩一次，避免数组无限增长
if (this.head > 1024 && this.head * 2 > this.arr.length) {
this.arr = this.arr.slice(this.head);
this.head = 0;
}
return v;
}
get size() { return this.arr.length - this.head; }
}
Map 版把下标当键，delete(this.head++) 不影响其它元素，代价是每次操作多一次哈希查找。
调用栈就是栈
JS 引擎为每次函数调用压一个栈帧（局部变量、返回地址），返回时弹出。递归太深，栈帧堆到上限就抛 RangeError：
function f(n) {
return f(n + 1);
}
f(0); // RangeError: Maximum call stack size exceeded
V8 默认栈约 1MB，普通递归深度上限一万层以内。改成显式栈就能绕开限制，这也是树遍历优先写迭代版的原因。
队列在事件循环里
浏览器把待执行的回调分成两个队列：