栈和队列有什么区别？各有哪些应用场景？

简化版

栈是后进先出（LIFO），只在一端（栈顶）进出，像叠盘子；队列是先进先出（FIFO），一端进、另一端出，像排队。栈用于「函数调用、回溯、括号匹配、表达式求值」，队列用于「BFS、任务/消息排队、缓冲区」。

详细版

维度	栈 Stack	队列 Queue
规则	后进先出 LIFO	先进先出 FIFO
操作端	只在栈顶：push 入、pop 出、peek 看	队尾入队 offer、队头出队 poll、peek 看队头
直观类比	叠盘子（后放的先拿）	排队买票（先来先服务）
典型应用	函数调用栈、递归、DFS/回溯、括号匹配、表达式求值、撤销(Undo)、浏览器后退	BFS 层序遍历、生产者-消费者、消息队列、打印/请求排队、缓冲区

两者都是操作受限的线性表：区别只在于「从哪端进、从哪端出」。栈同端进出，队列异端进出。

完整版教学

一、LIFO vs FIFO 的本质

栈限制你只能碰最近放进去的那个：想拿底下的，得先把上面的都拿走。这个「最近优先」的特性天然适合需要回退/嵌套的场景。队列则保证先来的先处理，天然适合公平排队/按序处理的场景。记住一句：栈管「嵌套与回溯」，队列管「排队与调度」。

二、栈的经典应用，为什么非它不可

• 函数调用栈：A 调 B、B 调 C，返回时必须先回到 C→B→A，正是后进先出。递归能工作就是靠这个栈；递归太深会 StackOverflow。
• 括号匹配 / 表达式求值：遇到左括号入栈，遇到右括号弹出配对；中缀转后缀、后缀求值都靠栈处理运算符优先级。
• DFS / 回溯：深度优先本质是「一条路走到底再回退」，回退就是弹栈（递归用系统栈，或手动用显式栈）。
• 撤销操作 / 浏览器后退：最近一步最先撤销。

三、队列的经典应用

• BFS 层序遍历：一层一层扩展，先访问的节点其邻居先入队、先处理，保证按层推进。
• 生产者-消费者 / 消息队列：任务按到达顺序排队处理，削峰、解耦。
• 缓冲区 / 请求排队：打印任务、网络请求按先来先服务处理。

四、实现方式

• 栈：数组或链表都行。Java 里别用老旧的 Stack 类（继承 Vector、方法带 synchronized、性能差且设计有历史包袱），推荐用 Deque：Deque<Integer> stack = new ArrayDeque<>();，push/pop/peek。
• 队列：Queue<Integer> q = new LinkedList<>(); 或 ArrayDeque；用 offer/poll/peek。需要循环利用空间时用循环队列避免「假溢出」。

五、一个常见混淆点

栈和队列不是新的数据结构，而是在线性表上加了访问限制。底层可以是数组也可以是链表——限制的是「你能从哪端操作」，不是「底层怎么存」。

六、常见误区与追问

结构	顺序规则	入/出示例
栈	LIFO 后进先出	入 1,2,3，先出 3
队列	FIFO 先进先出	入 1,2,3，先出 1
双端队列	两端都可操作	可当栈也可当队列

Stack:  push 1,2,3  -> pop 3,2,1
Queue:  offer 1,2,3 -> poll 1,2,3

易错点：栈和队列的差异不是“哪个更高级”，而是它们约束了不同的处理顺序。选结构时先问业务顺序，再谈实现。

如果有 100 个待处理任务，按提交顺序公平执行，用队列；如果做括号匹配、浏览器后退、函数调用返回，最新进入的状态要最先处理，用栈。这个顺序差异会直接决定算法正确性，不是简单替换容器 API。

再换成算法题语言：迷宫最短步数通常用队列做 BFS，因为第 1 层、第 2 层、第 3 层按距离推进，第一次到终点就是最短；而枚举所有路径或处理嵌套结构常用栈做 DFS，因为需要沿着最近分支一路深入，走不通再回退。结构选择来自问题需要的“处理顺序”，不是来自题目名字里有没有“栈”或“队列”。

• 误区：栈和队列只是方法名不同。 栈约束 LIFO，队列约束 FIFO，处理顺序完全不同。
• 误区：BFS 和 DFS 随便换容器也能得到同样结果。 BFS 用队列按层扩展，DFS 用栈深入分支，遍历顺序和适用问题不同。
• 误区：数组实现就一定比链表实现好。 数组缓存友好但扩容和固定容量要考虑；链表无需连续空间但指针开销更大。
• 追问：栈为什么适合括号匹配？ 最近打开的括号必须最先闭合，正好符合后进先出。
• 追问：队列为什么适合 BFS？ 先发现的节点先扩展，能保证按层推进。
• 追问：双端队列和它们是什么关系？ Deque 放开两端操作限制，可以模拟栈、队列，也能支持单调队列。

七、加强记忆

栈后进先出、同端进出，管嵌套回溯（调用栈、括号匹配、DFS、撤销）；队列先进先出、异端进出，管排队调度（BFS、消息队列、缓冲区）。Java 里栈和队列都优先用 ArrayDeque，别用老 Stack。