一、栈与队列的基本概念
1. 共同点
- 都是限制存取点的线性结构（线性结构 = 元素间一对一关系）。
- 插入和删除操作都只允许在端点进行。
- 存储方式既可以是顺序存储，也可以是链式存储。
2. 区别与存取原则
| 结构 | 存取原则 | 插入端 | 删除端 |
|---|---|---|---|
| 栈 | 先进后出 (LIFO) | 栈顶 | 栈顶 |
| 队列 | 先进先出 (FIFO) | 队尾 (rear) | 队头/队首 (front) |
3. 关于表结构的通用理解
- 一个线性表，若限制一端插入和删除 → 栈。
- 若限制一端插入、另一端删除 → 队列。
- 若不限制操作端 → 普通线性表。
- 因此：同一个表结构，对于不同使用者，既可以是栈也可以是队列。
二、顺序队列与循环队列
1. 普通顺序队列
- 初始化：
front = rear = -1（有的教材用0，具体看约定）。 - 假溢出：当
rear达到数组上限但队头前面有空位置时，无法继续入队，这种现象称为假溢出。 - 解决方式：引入循环队列。
2. 循环队列的存储特点
- 用数组存储，空间必须连续。
- 通过取模运算使队尾和队头在逻辑上连接成环。
- 数组有 n 个单元时，下标范围是 0 ~ n-1。
- 为区分队空和队满，通常牺牲一个存储单元，即：容量为 MAXLEN 的循环队列，队满时实际存放 MAXLEN-1 个元素。
3. 循环队列核心公式（必须掌握）
设：front 指向队首元素，rear 指向队尾元素的下一空闲位置，MAXLEN 为数组总长度。
| 操作/判断 | 公式 |
|---|---|
| 队空条件 | front == rear |
| 队满条件 | (rear + 1) % MAXLEN == front |
| 入队后 rear 移动 | rear = (rear + 1) % MAXLEN |
| 出队后 front 移动 | front = (front + 1) % MAXLEN |
| 队列中元素个数 | (rear - front + MAXLEN) % MAXLEN |
| 队尾元素所在位置 | (rear - 1 + MAXLEN) % MAXLEN |
4. 公式理解：环形思想
- 把数组看作一个首尾相接的环，
MAXLEN就是环上的刻度总数。 - 入队：在
rear位置放元素，然后rear顺时针移动一格（取模）。 - 出队：取出
front位置元素，然后front顺时针移动一格（取模）。 - 判满：
rear再走一步就追上front→(rear + 1) % MAXLEN == front。 - 判空：
front和rear在同一位置。 - 算个数：
rear领先front的格数。如果rear >= front，则是rear - front；如果rear < front（跨过数组末尾），则是rear - front + MAXLEN。统一用取模公式(rear - front + MAXLEN) % MAXLEN。
5. 典型题目举例
例1：数组大小6，front=3, rear=0，先删一个元素，再加入两个元素，求新的 front 和 rear。
- 删除一个：
front = (3+1) % 6 = 4 - 加入第一个：放入
rear=0处，rear = (0+1) % 6 = 1 - 加入第二个：放入
rear=1处，rear = (1+1) % 6 = 2 - 结果：
front=4, rear=2
例2：最大容量为 n 的循环队列，队满条件是什么？
- 牺牲一个单元后，队满时
rear再走一步就追上front：(rear+1) % n == front - 注意必须取模，否则
rear在数组末尾时rear+1会越界。
例3：数组 Q[n] 表示循环队列，f 为队头元素的前一位置，r 为队尾元素的位置，求队列元素个数。
- 有效元素从
f+1到r，环形差值为(r - f + n) % n，即(n + r - f) % n。
例4：非循环顺序队列，最多元素 m0（下标 0~m0-1），队满条件是什么？
- 非循环队列不看 front 前面的空位，只看 rear 是否到达数组末尾：
rear == m0 - 1。 - 这与循环队列的取模公式不同，不可混淆。
三、链队列
1. 结构特点
- 用单链表实现，通常带有头结点。
front指向头结点（不变），rear指向队尾结点。- 链队列为空时：
front == rear（都指向头结点），或者front->next == NULL。
2. 链队列是否会出现队满？
- 不会。链队列动态申请内存，只要系统内存没有耗尽，就不会有队满的情况。
- 但循环链队列在内存不足时仍可能溢出。
3. 出队操作
- 有头结点的链队列，出队时删除的是头结点的后继结点。
- 修改的是
front->next，front指针本身不改变。 - 若删除的是最后一个元素，则还需要让
rear指向头结点（即rear = front），恢复为空队列状态。
四、易混判断题辨析
| 判断内容 | 正误 | 解析 |
|---|---|---|
| 栈和队列都是顺序存储的线性结构 | 错 | 它们是线性结构，但存储方式可以是顺序的也可以是链式的，不限于顺序存储。 |
| 队列是限制在两端进行操作的线性表 | 对 | 一端插入（队尾），一端删除（队头），操作限制在两端。 |
| 链队列在一定范围内不会出现队满 | 对 | 链式存储按需分配，不会出现"队满"状态（除非内存耗尽）。 |
| 同一个表结构既可以是栈也可以是队列 | 对 | 物理结构相同，只是施加的操作限制不同。 |
| 循环队列 rear>front 时元素个数 = rear-front | 对 | 此时 rear 在 front 之后且未跨数组末尾，环形公式退化为 rear - front。 |
| 链队列出队时会改变 front 指针的值 | 错 | 有头结点时，front 始终指向头结点，出队只改变 front->next。 |
| 栈和队列的存储方式既可是顺序也可是链接 | 对 | 两种存储方式都适用。 |
五、知识速记卡
- 循环队列三要素：取模实现循环、牺牲一单元判满、
(rear-front+MAXLEN)%MAXLEN算个数。 - 判空 vs 判满：空是
front == rear；满是(rear+1)%MAXLEN == front，两个公式长的像但不能混。 - 链队列：有头结点、动态扩容不队满、出队不改变 front 指针值。
- 栈与队列：都是线性结构、都是端点操作、都能顺序/链式存储；区别在存取原则——栈是后进先出，队列是先进先出。