栈和队列：你以为很熟，其实暗藏玄机

我的前言：三道题测测你的"线性数据结构"底子

先别往下翻，看看这三道题你能不能讲清楚：

这三个问题，面试官随便拎出一个都能聊十分钟。本文带你从数组出发，一路打通栈、队列、链表，把线性数据结构这块拼图完整拼上。

📌 适合人群：有一年 JS 经验，刷过几个算法题但总觉得"栈和队列太简单没啥好学的"的开发者。

📌 你将收获：栈/队列的底层本质、为什么不能只把它们当数组用、链表的实现与适用场景、JS 数组的"真实身份"、经典算法题的解题思路。

背景：为什么"栈和队列"值得单独写一篇文章？

我刚学数据结构的时候，看到"栈和队列"这一章是这么想的：

“不就是数组加两个限制条件吗？push/pop 是栈，push/shift 是队列，有什么好学的？”

我相信很多人跟我一样。但恰恰是这种心态，导致了两个问题：

第一，面试官问"用栈实现队列"，你第一反应是"我用数组不就完了？"——考官要的是你对两种数据结构出栈顺序的理解，不是让你秀 JS 数组 API。

第二，实际开发中遇到递归爆栈、BFS 遍历、浏览器历史记录这些场景，你看不到"栈和队列"的影子，自然想不到用它们来优化。

这篇文章要做的，就是让你从"会用"升级到"真懂"。

目标：这个模块要解决什么问题？

一句话概括：在合适的场景，用合适的线性数据结构。

关键认知：栈和队列不是"简化版的数组"，而是在特定约束下最大化效率的数据结构。约束本身不是限制，是优化方向。

设计：前端视角看数据结构设计

线性 vs 非线性

整个数据结构的世界可以这么分：

数据结构
├── 线性结构
│ ├── 数组（连续存储 + 下标访问）
│ ├── 链表（离散存储 + 指针串联）
│ ├── 栈（LIFO，操作受限的线性表）
│ └── 队列（FIFO，操作受限的线性表）
└── 非线性结构
├── 树
└── 图

栈和队列本质上是"操作受限的数组/链表"——你只能在一端操作，但恰恰是这个限制，让它们在特定场景下比"万能数组"更可靠。

栈的设计：只能在一头操作

想象一个冰柜里的雪糕——你只能从最上面拿，也只能从最上面放。这就是栈：

• push：在栈顶添加元素（数组尾部）
• pop：从栈顶取出元素
• peek：看一眼栈顶，但不取出（stack[stack.length – 1]）

┌─────────┐
栈顶 → │ 巧乐兹 │ ← push/pop 操作入口
├─────────┤
│ 冰工厂 │
├─────────┤
│ 可爱多 │
├─────────┤
栈底 → │ 东北大板 │
└─────────┘

队列的设计：一头进，另一头出

就像食堂排队打饭——新来的人排到队尾，打完饭的人从队头离开：

• enqueue（入队）：在队尾添加（push）
• dequeue（出队）：从队头移除（shift）

出队 ← [ 张三 | 李四 | 王五 | 赵六 ] ← 入队
队头 队尾

链表的设计：离散节点 + 指针串联

数组在内存中是连续存储的，而链表的节点可以"散落"在任何位置，靠每个节点上的 next 指针串联起来：

// JS 中链表的节点就是一个对象字面量
{
val: 1,
next: {
val: 2,
next: {
val: 3,
next: null // 尾节点，next 为空
}
}
}

head tail
↓ ↓
[val:1|next] → [val:2|next] → [val:3|next=null]

访问链表中的任意节点，必须从头开始逐个遍历。 这是链表最大的"代价"——也是它与数组最本质的区别。

实现：核心代码和流程

1. 数组的本质：你以为的"增删改查"

先看数组增加元素的三种方式：

const arr = [1, 2];

// push：尾部追加，时间复杂度 O(1)
arr.push(3); // arr = [1, 2, 3]

// unshift：头部插入，时间复杂度 O(n)——所有元素都要往后挪
arr.unshift(0); // arr = [0, 1, 2, 3]

// splice：任意位置插入/删除，时间复杂度 O(n)
arr.splice(1, 0, 3); // 在索引1处插入3 → [1, 3, 2]
arr.splice(1, 1); // 删除索引1 → [1, 2]

三个需要记住的点：

核心结论：假设数组长度是 n，增删操作需要移动的元素数量随 n 线性增长 —— O(n)。

2. 栈的完整实现

const stack = []; // 空栈
stack.push("东北大板");
stack.push("可爱多");
stack.push("冰工厂");
stack.push("巧乐兹");

// 出栈：后进先出
while (stack.length) {
const top = stack[stack.length – 1]; // peek 栈顶
console.log(`取出来的是`, top);
stack.pop();
}
// 输出顺序：巧乐兹 → 冰工厂 → 可爱多 → 东北大板
console.log(stack); // []

这就是 LIFO：最后放进去的巧乐兹第一个被拿出来。

3. 队列：FIFO 的经典实现

const queue = [];

// 入队
queue.push('a');
queue.push('b');
queue.push('c');

// 出队
while (queue.length) {
console.log(queue.shift()); // a → b → c
}

shift() 会将数组第一个元素移除并返回，同时所有后续元素前移——这是一个 O(n) 的操作。如果追求 O(1) 的队列出队，可以用链表实现。

4. 链表的 JS 实现

function ListNode(val) {
this.val = val;
this.next = null;
}

const node = new ListNode(1);
node.next = new ListNode(2);
// 链表：1 → 2 → null

链表添加元素的核心：操作 next 指针

原链表：A → B → C
在 A 后面插入 X：
X.next = A.next // X 指向原 B
A.next = X // A 指向 X
结果：A → X → B → C

关键：一定要先让新节点指向后继节点，再断开前驱节点的 next。顺序反了就会"坐过站"——B 节点就找不到了。

数组 vs 链表，什么时候用哪个？

选择原则：

• 数据规模小、需要频繁遍历/索引访问 → 数组
• 数据规模大、需要频繁增删 → 链表
• 数组的遍历优势明显，链表的增删优势明显，没有绝对的好坏

踩坑：JS 数组的"真实身份"

这是很多前端开发者踩过的坑：JS 的数组不是传统意义上的"数组"。

const arr = [1, 2, 3, 4, 5]; // 看起来是标准数组

const arr2 = ['haha', 1, { a: 1 }]; // 不同类型混在一起
console.log(arr2[2]); // { a: 1 } —— 依然能用下标访问

为什么不同类型的元素还能用下标 O(1) 访问？

因为 V8 引擎中，JS 的数组底层其实是哈希表（HashTable），而不是 C 语言那种连续内存的纯数组。所以：

• 你可以往数组里塞任何类型
• 下标访问是通过哈希查找实现的
• 不连续的数组（稀疏数组）也能正常工作

const arr = [];
arr[999] = 1; // 这是合法的，arr.length = 1000
arr[0] = 2; // 中间全是 empty

另一个坑：sort() 默认按 ASCII 排序

let arr = [10, 2, 5];
arr.sort(); // [10, 2, 5] —— 按 ASCII 排序，"10" < "2"
arr.sort((a, b) => a – b); // [2, 5, 10] —— 数字升序，正确

sort() 如果不传比较函数，会把元素转成字符串按 Unicode 码点排序。这是一个经典的前端坑，面试也常考。

复盘：下次怎么优化

1. 学习的优化

如果让我重新学一遍栈和队列，我会这样做：

• 不要先看定义，先看场景。 先问"什么情况下需要 LIFO？什么情况下需要 FIFO？"带着场景去学数据结构，比背定义高效。
• 画图。 栈就是竖着的管子，队列就是横着的管道，链表就是散落的珠子串在一根线上。图想明白了，代码自然写出来。
• 手写，不要复制粘贴。 ListNode 的构造函数、链表插入的指针操作，默写多遍，肌肉记忆就形成了。

2. 代码的优化

• 队列尽量用链表实现，避免 shift() 的 O(n) 开销。JS 的 Array.shift() 在数据量大时性能很差。
• 栈用数组的 push/pop 就够了，因为这两个操作都在数组尾部，时间复杂度都是 O(1)，不会触发元素移动。
• sort() 永远传比较函数，养成肌肉记忆。

3. 知识体系的优化

把这四个数据结构的增删改查复杂度做成一张表，时常回顾：

访问 插入(头/尾/中) 删除(头/尾/中)
数组 O(1) O(n)/O(1)/O(n) O(n)/O(1)/O(n)
链表 O(n) O(1)/O(1)/O(1) O(1)/O(1)/O(1)
栈 — –/O(1)/– –/O(1)/–
队列 — –/O(1)/– O(1)/–/–

这张表是面试和实际开发中的"速查手册"。理解了它，选数据结构的决策就变成了下意识反应。

一张图串联全文

线性数据结构
│
┌──────────────┼──────────────┐
▼ ▼ ▼
数组 链表 受限结构
连续存储+下标 离散存储+指针 │
│ │ ┌─────┴─────┐
│ │ ▼ ▼
│ │ 栈(LIFO) 队列(FIFO)
│ │ push/pop push/shift
│ │
JS特殊性： 添加元素本质：
底层是哈希表 操作next指针
混合类型ok 别"坐过站"
sort()要传参

引用说明：本文代码和笔记来自【我的算法学习仓库】(github.com/xz878787)， 笔记参考了《算法图解》和 MDN 相关资料。

如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、评论三连。有任何问题也欢迎在评论区交流讨论！ 。