数组链表栈队列

1. 一句话总结

数组适合随机访问，链表适合灵活插入删除，栈和队列限制访问顺序来解决特定问题。

2. 通俗解释

数组像连续座位，知道编号就能直接找到；链表像每个人拿着下一个人的地址，找第 k 个要从头走。栈像盘子后进先出，队列像排队先进先出。

3. 核心概念

• 数组：连续内存，下标随机访问 O(1)。
• 链表：节点用指针连接，查找位置 O(n)。
• 栈：后进先出，常用于递归、括号、单调栈。
• 队列：先进先出，常用于 BFS 和任务排队。
• 单调栈/队列：维护有序性减少重复比较。

4. 底层原理

• 数组地址可由基地址加偏移计算，且 Cache 友好。
• 链表插入删除不搬移元素，但指针跳转容易 Cache miss。
• 栈的访问限制和函数调用栈一致。
• 队列用头尾指针维护顺序，循环队列可复用数组空间。
• 单调结构中每个元素最多进出一次，总体 O(n)。

5. 面试标准回答

数组、链表、栈、队列的核心区别在于内存布局和访问规则。数组连续内存，能 O(1) 下标访问，遍历 Cache 友好，但中间插入删除要搬移元素。链表节点分散，已知位置插入删除方便，但查找位置 O(n)，并且有额外指针开销。栈限制后进先出，适合递归模拟、括号匹配和单调栈；队列限制先进先出，适合 BFS、任务调度和消息缓冲。选型看访问模式，不是只背复杂度。

6. 高频追问

追问 1：数组链表栈队列面试第一句话怎么答？

先给结论：数组：连续内存，下标随机访问 O(1)。 再补充它解决的问题和使用场景，避免一上来背长定义。

追问 2：它为什么需要底层机制支撑？

数组地址可由基地址加偏移计算，且 Cache 友好。 面试官追问时要把“现象”落到“机制”和“代价”。

追问 3：常见误区是什么？

不要把平均情况说成绝对结论，也不要忽略边界条件、退化情况和工程成本。

追问 4：如果继续追问怎么展开？

可以沿着“定义 → 原理 → 对比 → 场景 → 缺点 → 优化”展开，重点说清：链表插入删除不搬移元素，但指针跳转容易 Cache miss。

追问 5：实际开发中怎么体现？

ArrayList 查询快，但扩容和中间插入有成本。 这类联系能把基础知识从“背概念”变成“解释工程选择”。

追问 6：回答时怎么收尾？

最后用一句话总结适用条件和代价，说明什么时候该用、什么时候不该用。

7. 易混淆点

8. 实际开发联系

• ArrayList 查询快，但扩容和中间插入有成本。
• 线程池任务队列、消息队列体现 FIFO。
• 浏览器前进后退和函数调用体现栈结构。

9. 背诵速记

数组连续、随机访问快、Cache 友好；链表查找慢但已知位置插删灵活；栈后进先出，队列先进先出。单调栈和单调队列用有序性把重复比较压缩为线性复杂度。