您什么时候应该使用堆栈而不是队列？请给出真实的例子。

Question

IT Interview Practice · Accepted Answer

两者都是具有 O(1) 端点的线性 ADT，但**移除顺序**相反：**堆栈是 LIFO**（最近的优先），**队列是 FIFO**（最旧的优先）。将数据结构与问题所需的顺序相匹配。

## 核心区别

```text
Stack (LIFO):  push 1,2,3  -> pop order 3,2,1
Queue (FIFO):  enq  1,2,3  -> deq order 1,2,3
```

## 真实例子

| 何时使用堆栈... | 何时使用队列... |
|---|---|
| 撤销/重做（最近的操作优先） | 任务调度（到达顺序） |
| 浏览器后退按钮 | 打印队列 / 任务队列 |
| 函数调用/递归 | BFS / 图上的最短路径 |
| 括号匹配、解析 | 服务间消息缓冲 |
| DFS（深度优先探索） | 速率限制 / 请求处理 |

## 代码对比

```python
# DFS uses a stack: explore newest branch first
stack = [start]
while stack:
    node = stack.pop()        # LIFO -> goes deep
    for nb in graph[node]: stack.append(nb)

# BFS uses a queue: explore nearest first
from collections import deque
q = deque([start])
while q:
    node = q.popleft()        # FIFO -> goes level by level
    for nb in graph[node]: q.append(nb)
```

## 为什么这很重要

LIFO 与 FIFO 的选择直接改变算法行为：同一个图遍历用堆栈变成 DFS，用队列变成 BFS。

识别问题是需要

撤销/重做（最近的操作优先）	任务调度（到达顺序）
浏览器后退按钮	打印队列 / 任务队列
函数调用/递归	BFS / 图上的最短路径
括号匹配、解析	服务间消息缓冲
DFS（深度优先探索）	速率限制 / 请求处理

核心区别

真实例子

相关问题

代码对比

为什么这很重要