04｜栈与队列
1. 核心概念
栈（Stack）和队列（Queue）都是按照特定顺序存取元素的数据结构。 两者最主要的区别是元素的取出顺序。
- 栈：后进先出（LIFO），最后加入的元素最先取出。
- 队列：先进先出（FIFO），最先加入的元素最先取出。
flowchart TB
A["依次加入 A、B、C"] --> B{"取出规则"}
B --> C["栈 LIFO"]
B --> D["队列 FIFO"]
C --> E["取出：C → B → A"]
D --> F["取出：A → B → C"]2. 基本操作
| 结构 | 加入元素 | 移除元素 | 查看但不移除 |
|---|---|---|---|
| 栈 | Push：放入栈顶 | Pop：移除栈顶 | Peek / Top |
| 队列 | Enqueue：加入队尾 | Dequeue：移除队头 | Peek / Front |
两者都需要处理空结构；使用固定容量存储时，还需要处理容量已满。栈和队列都可以采用数组或链表实现。
3. 适用场景
| 需求 | 优先考虑 | 原因 |
|---|---|---|
| 撤销最近一次操作 | 栈 | 最近记录先取出 |
| 暂存回退路径 | 栈 | 按相反顺序回退 |
| 按到达顺序处理消息 | 队列 | 先入队的数据先取出 |
| 在生产与处理之间暂存任务 | 队列 | 按规则组织等待处理的数据 |
函数调用栈体现了后进先出的思想，但与用户自行实现的栈容器不完全相同。
4. 使用边界
- 栈适合处理最近加入的数据，不适合直接访问中间任意元素。
- 队列保证符合 FIFO 规则的取出顺序，但并发任务的完成顺序不一定与出队顺序相同。
- 栈和队列描述操作规则，并不规定必须使用哪一种内存存储方式。
5. 总结
需要优先处理最近加入的数据，考虑栈；需要按进入顺序取出数据，考虑队列。