# 第 3 章 栈与队列（示例讲义）

> 本文件是示例知识库的演示材料，为简化版讲义提纲。

## 3.1 栈（Stack）

栈是**只允许在一端（栈顶）进行插入和删除**的线性表，
后进先出（LIFO）。基本操作：push（入栈）、pop（出栈）、top（取栈顶）。

### 顺序栈

用数组 + 栈顶指针 top 实现。`top = -1` 表示空栈；
入栈 `data[++top] = x`；出栈 `x = data[top--]`。
上溢：满栈再入栈；下溢：空栈再出栈（必须判错）。

### 共享栈

两个栈共用一个数组，栈底分设两端、栈顶相向生长，
`top1 + 1 == top2` 时栈满。提高空间利用率。

### 栈的典型应用

1. **括号匹配**：遇左括号入栈，遇右括号弹栈比对。
2. **表达式求值**：中缀转后缀（操作符栈），后缀求值（操作数栈）。
3. **递归与函数调用**：系统用调用栈保存现场；递归可借助显式栈
   改写为非递归。
4. **出栈序列计数**：n 个元素的合法出栈序列数为卡特兰数
   C(2n,n)/(n+1)（常考选择题：判断某序列是否可能的出栈序列）。

## 3.2 队列（Queue）

队列是**只允许队尾插入、队头删除**的线性表，先进先出（FIFO）。

### 循环队列

用数组实现时为避免「假溢出」，把数组看成首尾相接的环：
`rear = (rear + 1) % MaxSize`。

- 牺牲一个单元区分队空/队满：
  队空 `front == rear`；队满 `(rear + 1) % MaxSize == front`。
- 队列长度：`(rear - front + MaxSize) % MaxSize`（必考公式）。

### 链式队列

带头结点的单链表 + front/rear 两个指针；不存在溢出问题
（除非内存耗尽）。注意删除最后一个元素时 rear 要重新指向头结点。

### 双端队列（deque）

两端都可插入删除。受限双端队列（一端只进、一端只出等）的
合法输出序列判断是常考题型。

### 队列的典型应用

1. 层次遍历（树的按层访问、图的 BFS）。
2. 操作系统的任务调度、打印缓冲。
3. 用两个栈模拟队列 / 用两个队列模拟栈（经典面试题）。

## 本章要点（考试常考）

1. 循环队列队满/队空判定与长度公式（必考填空/计算）。
2. 出栈序列合法性判断（必考选择）。
3. 中缀表达式转后缀并求值（必考大题）。
4. 栈在递归消除中的作用（简答）。
