记沉

数据结构与算法-知识点(第三章栈和队列)

4/11/2025 13003

# 一、栈（Stack）

# 1. 基本概念

  • 定义：一种**先进后出（FILO）**的线性数据结构，操作仅在一端（栈顶）进行。
  • 核心术语：
    • 栈顶（Top）：唯一允许插入和删除元素的位置。
    • 栈底（Bottom）：不允许操作的一端。
    • 栈容量（Capacity）：栈最多可存储的元素数量。
    • 入栈（Push）：向栈顶添加元素。
    • 出栈（Pop）：删除栈顶元素。
    • 栈顶元素（Top Element）：当前栈顶的值。
    • 栈空（Empty）：栈中无元素（如顺序栈的top = -1）。
    • 栈满（Full）：栈容量已满（如顺序栈的top == capacity-1）。

# 2. 实现方式

# (1) 顺序栈（数组实现）
  • 存储结构：使用数组存储元素，栈顶指针top记录当前栈顶位置。
  • 关键操作：
    • 判空：top == -1。
    • 判满：top == capacity-1。
    • 入栈：top++; stack[top] = element（需先判断栈是否满）。
    • 出栈：element = stack[top]; top--（需先判断栈是否空）。
# (2) 链式栈（链表实现）
  • 存储结构：使用单链表，栈顶是链表的头节点。
  • 关键操作：
    • 判空：head == NULL。
    • 判满：一般无固定容量（除非限制链表长度）。
    • 入栈：在链表头部插入新节点。
    • 出栈：删除链表头节点。

# 3. 合理出栈序列

  • 卡特兰数（Catalan Number）：
    n 个元素的合法出栈序列总数为 Cₙ = (1/(n+1)) * C(2n, n)。
  • 示例：
    入栈顺序为 A→B→C 时，合法出栈序列为 5 种：
    CBA、BAC、ACB、ABC、BCA。
  • 判断方法：
    模拟栈操作，若序列无法通过合法入栈、出栈得到，则为非法。

# 4. 栈的应用

# (1) 括号匹配
  • 算法步骤：
    1. 遍历字符串，遇到左括号（(、[、{）则入栈。
    2. 遇到右括号时，检查栈顶是否匹配：
      • 若匹配则出栈；
      • 否则返回不匹配。
    3. 最终栈为空则匹配成功。
# (2) 中缀表达式转后缀表达式
  • 规则：
    1. 操作数直接输出。
    2. 运算符与栈顶比较优先级：
      • 若栈顶优先级高，则弹出栈顶；
      • 当前运算符入栈。
    3. 左括号入栈，右括号弹出直到左括号。
  • 示例：
    A + B * C → A B C * +
# (3) 计算后缀表达式
  • 算法步骤：
    1. 遇到操作数则入栈。
    2. 遇到运算符则弹出两个操作数，计算后将结果入栈。
    3. 最终栈顶为计算结果。

# 二、队列（Queue）

# 1. 基本概念

  • 定义：一种**先进先出（FIFO）**的线性数据结构，队尾插入，队头删除。
  • 核心术语：
    • 队头（Front）：允许删除的一端。
    • 队尾（Rear）：允许插入的一端。
    • 队列长度（Length）：当前元素个数。
    • 入队（Enqueue）：向队尾添加元素。
    • 出队（Dequeue）：删除队头元素。
    • 队空（Empty）：队列中无元素。
    • 队满（Full）：队列容量已满。

# 2. 实现方式

# (1) 循环队列（数组实现）
  • 存储结构：使用数组，通过模运算实现循环。
  • 关键指针：
    • 队头指针 front：指向队头元素。
    • 队尾指针 rear：指向下一个插入位置。
  • 判空与判满（牺牲一个存储单元）：
    • 空：front == rear。
    • 满：(rear + 1) % capacity == front。
  • 入队：rear = (rear + 1) % capacity。
  • 出队：front = (front + 1) % capacity。
# (2) 链式队列（链表实现）
  • 存储结构：使用单链表，队头为链表头，队尾为链表尾。
  • 关键操作：
    • 判空：front == NULL。
    • 入队：在链表尾部插入新节点。
    • 出队：删除链表头节点。

# 3. 队列的应用

  • 典型场景：
    • 广度优先搜索（BFS）。
    • 任务调度（如打印队列）。
    • 缓冲区管理（如消息队列）。

# 三、对比与总结

特性 栈（Stack） 队列（Queue）
操作规则 先进后出（FILO） 先进先出（FIFO）
核心操作 push、pop enqueue、dequeue
实现方式 顺序栈、链式栈 循环队列、链式队列
应用场景 函数调用栈、括号匹配、表达式转换 BFS、任务调度、缓冲区管理

# 四、算法实现示例

# 1. 顺序栈基本操作（C语言）

#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int top;
} SeqStack;

void InitStack(SeqStack *S) {
    S->top = -1;
}

int Push(SeqStack *S, int x) {
    if (S->top == MAX_SIZE - 1) return 0; // 栈满
    S->data[++S->top] = x;
    return 1;
}

int Pop(SeqStack *S, int *x) {
    if (S->top == -1) return 0; // 栈空
    *x = S->data[S->top--];
    return 1;
}

# 2. 循环队列基本操作（C语言）

#define MAX_QUEUE_SIZE 100
typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front, rear;
} CircularQueue;

void InitQueue(CircularQueue *Q) {
    Q->front = Q->rear = 0;
}

int Enqueue(CircularQueue *Q, int x) {
    if ((Q->rear + 1) % MAX_QUEUE_SIZE == Q->front) return 0; // 队满
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAX_QUEUE_SIZE;
    return 1;
}

int Dequeue(CircularQueue *Q, int *x) {
    if (Q->front == Q->rear) return 0; // 队空
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_QUEUE_SIZE;
    return 1;
}

# 五、综合练习题

  1. 判断合法出栈序列：
    给定入栈顺序为 1,2,3,4，判断 3,1,2,4 是否合法。
  2. 括号匹配：
    设计算法判断字符串 "{([])}" 是否合法。
  3. 中缀转后缀：
    将表达式 (A + B) * C - D / E 转换为后缀形式。
  4. 循环队列操作：
    容量为 5 的循环队列，依次入队 1,2,3,4，再出队两次，最后入队 5，画出最终存储结构。