C语言栈与队列核心考点：考研数据结构精讲

栈的核心概念与操作

栈（Stack）是一种只允许在一端进行插入和删除操作的线性表，该端称为栈顶（Top），另一端称为栈底（Bottom）。栈遵循后进先出（LIFO）原则。若采用递归方式求解问题（如斐波那契数列），通常可利用栈模拟函数调用过程，但需注意非递归重写时并非必须使用栈，某些情况可通过循环直接解决以提高效率。

栈的基本操作主要包括：

• InitStack(&S)：初始化栈，构造空栈。
• Push(&S, x)：入栈，将元素x压入栈顶。
• Pop(&S, &x)：出栈，弹出栈顶元素并用x返回其值。
• GetTop(S, &x)：读取栈顶元素，不删除。
• StackEmpty(S)：判空，空则返回true，否则false。
• DestroyStack(&S)：销毁栈并释放内存。

当两个栈共享同一块连续内存空间时，可称为共享栈。从两端向中间填充可有效利用空间，避免其中一个栈满而另一个栈仍有大量空闲的情况。此外，对于长度为n的进栈序列，其可能的出栈序列个数为卡特兰数 C(2n, n) / (n + 1)。

队列的原理与存储实现

队列（Queue）是另一种受限线性表，仅允许在表尾（Rear）进行插入（入队），在表头（Front）进行删除（出队），遵循先进先出（FIFO）原则。在考研真题中，队列的考查重点通常在于画初始状态图、推导判空/判满条件以及理解入队出队的基本流程，而非具体的代码编写。

顺序队列与循环队列处理

顺序队列使用数组存储，定义如下结构体：

#define Maxsize 50
typedef struct {
    ElemType data[Maxsize];
    int front, rear;
} SqQueue;

初始化时 Q.front = Q.rear = 0。在普通顺序队列中，随着入队和出队，指针后移会导致“假溢出”现象。为解决此问题，通常采用循环队列，即指针移动时取模运算：
入队后队尾指针：Q.rear = (Q.rear + 1) % Maxsize
出队后队首指针：Q.front = (Q.front + 1) % Maxsize

此时面临一个关键问题：队空（front == rear）与队满时两者数值相同，无法区分。考研中常考以下三种解决方案：

方法一：牺牲一个存储单元（最常用）
规定少用一个单元作为队满的标志。入队时需确保空间充足，故少用一个位置。
- 队满条件：(Q.rear + 1) % Maxsize == Q.front
- 队空条件：Q.front == Q.rear
- 队列长度：(Q.rear - Q.front + Maxsize) % Maxsize

方法二：增设数据成员记录元素个数
在结构体中增加 int size 字段。
- 队空：Q.size == 0
- 队满：Q.size == Maxsize

方法三：增设标记位 tag
- 入队操作令 tag = 1，出队操作令 tag = 0。
- 当 Q.front == Q.rear 时，若 tag == 1 则为队满，若 tag == 0 则为队空。

链式队列

链式队列通过指针连接节点，无需担心溢出，但需动态分配内存。其结构定义如下：

typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;

typedef struct {
    LinkNode *front, *rear;
} LinkQueue;

栈的应用：表达式转换与求值

栈在计算机科学中的应用极为广泛，包括括号匹配、递归展开、深度优先搜索（DFS）以及表达式求值。考研重点考查中缀表达式转换为前缀或后缀表达式的算法逻辑。

中缀转后缀表达式

后缀表达式（逆波兰表示法）便于计算机计算。转换规则涉及两个栈：运算符栈 S1 和结果暂存栈 S2。具体步骤如下：

1. 扫描方向：从左至右扫描中缀表达式。
2. 操作数处理：遇到操作数，直接压入 S2。
3. 运算符处理：
   - 若 S1 为空，或栈顶为左括号 “(”，直接将运算符压入 S1。
   - 若当前运算符优先级 大于 S1 栈顶运算符优先级，压入 S1。
   - 否则（优先级小于或等于），弹出 S1 栈顶运算符压入 S2，重复比较直到满足上述条件。
4. 括号处理：
   - 左括号 “(”：直接压入 S1。
   - 右括号 “)”：依次弹出 S1 栈顶运算符压入 S2，直到遇到左括号，丢弃该对括号。
5. 结束处理：表达式扫描完毕后，将 S1 中剩余运算符依次弹出压入 S2。
6. 输出结果：依次弹出 S2 元素，**逆序**排列即为最终的后缀表达式。

中缀转前缀表达式

前缀表达式（波兰表示法）的转换逻辑与后缀类似，但细节有差异：

1. 扫描方向：从右至左扫描中缀表达式。
2. 操作数处理：遇到操作数，直接压入 S2。
3. 运算符处理：
   - 若 S1 为空或栈顶为右括号 “)”，直接压入 S1。
   - 若当前运算符优先级 大于或等于 S1 栈顶优先级，压入 S1（注意这里包含等于的情况，不同于后缀）。
   - 否则，弹出 S1 栈顶压入 S2，继续比较。
4. 括号处理：
   - 右括号 “)”：直接压入 S1。
   - 左括号 “(”：依次弹出 S1 栈顶运算符压入 S2，直到遇到右括号，丢弃该对括号。
5. 结束处理：扫描完毕，将 S1 剩余运算符压入 S2。
6. 输出结果：依次弹出 S2 元素，输出顺序即为前缀表达式（无需逆序）。

其他应用简述

• 后缀表达式求值：遍历表达式，操作数入栈；遇运算符则弹出栈顶两个数据进行计算，结果再入栈。
• 广度优先搜索（BFS）：图的遍历算法中，BFS 需要借助队列来管理待访问顶点。
• 特殊矩阵压缩存储：对称矩阵、三角矩阵和三对角矩阵（带状矩阵）可利用二维数组的特殊性进行压缩；稀疏矩阵可采用三元组或十字链表存储以节省空间。