数据结构第三章栈与队列

🤖 Assistant

# 🧱 第三章 栈与队列

## 🌟 基本概念
### 🎯 什么是数据结构中的"栈"？
```c
// 栈的操作特点：LIFO（Last In First Out）
#define MaxSize 50  
typedef struct {
    ElemType data[MaxSize];  
    int top;  // 栈顶指针
} SqStack;

🔹 核心规则：

• 插入/删除只能在一端进行（栈顶）
• 后进入的元素先被访问（就像叠盘子）
  🔸 关键操作：
• Push（入栈） → data[++top] = x
• Pop（出栈） → x = data[top--]
  ⚠️ 注意：空栈时top=-1（图示↓）
  

---

🎯 队列是什么？

// 队列的操作特点：FIFO（First In First Out）
typedef struct {
    ElemType data[MaxSize];  
    int front, rear;  // 队头队尾指针
} SqQueue;

🔹 基本规则：

• 插入在队尾（rear），删除在队头（front）
• 先进入的元素先离开（类似排队）
  🔸 关键操作：
• 入队 → data[rear++] = x
• 出队 → x = data[front++]
  ⚠️ 假溢出图示↓
  

---

🧱 栈的深度解析

🔧 两种实现方式对比

类型	存储方式	操作复杂度	典型应用场景
顺序栈	静态数组+栈顶指针	O(1)	函数调用栈、表达式求值
链栈	链表+头插法	O(1)	递归转非递归

📌 栈的溢出问题

flowchart TD
    A[栈空] -->|top=-1时pop| Underflow
    B[栈满] -->|top=MaxSize-1时push| Overflow

---

🚦 队列的全面剖析

🔧 三种实现方案

1. 顺序队列（基础版）

🔸 缺陷：产生假溢出 → 已出队的空间无法复用

2. 循环队列（经典解决方案）

// 关键算法：
// 入队操作
rear = (rear + 1) % MaxSize;
// 出队操作
front = (front + 1) % MaxSize;

🔹 判空条件：front == rear
🔹 判满策略：

• 方案一：留空一个元素 → (rear+1)%MaxSize == front
• 方案二：新增size变量 → size == MaxSize

3. 链式队列（动态增长）

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

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

🔸 优点：永不溢出（除非内存不足）

---

🎭 特殊队列

🔄 双端队列（Deque）

// 支持两端操作的队列
void addFirst(ElemType x);  // 队头插入
void addLast(ElemType x);   // 队尾插入
ElemType removeFirst();     // 队头删除
ElemType removeLast();      // 队尾删除

🔸 应用场景：滑动窗口算法、撤销/重做功能

🔝 优先级队列

🔹 本质：出队顺序由元素优先级决定（常用于操作系统任务调度）

---

📊 栈与队列的终极对决

特性	栈	队列
数据进出规则	LIFO（后进先出）	FIFO（先进先出）
典型结构	单开口容器	双开口管道
核心指针	top指针	front/rear指针
经典应用	括号匹配/递归调用	消息队列/BFS遍历

---

🛠️ 实战应用场景

1. 栈的典型应用：
   • 函数调用栈（执行上下文管理）
   • 编辑器撤销功能（Ctrl+Z）
   • 括号有效性检测（{[()]}判断）
2. 队列的经典场景：
   • 打印机任务队列（先到先打印）
   • 线程池任务调度（保持处理顺序）
   • 广度优先搜索（BFS逐层遍历）
3. 混合应用：
   • 用两个栈实现队列
   • 用队列实现栈

---

🧠 思维导图

graph TD
    A[栈与队列] --> B[栈]
    A --> C[队列]
    
    B --> D[顺序栈]
    B --> E[链栈]
    B --> F[共享栈]
    
    C --> G[顺序队列]
    C --> H[循环队列]
    C --> I[链式队列]
    C --> J[优先级队列]
    
    J --> K[最大优先队列]
    J --> L[最小优先队列]

---

📌 重要公式速查表

描述	计算公式
顺序栈元素个数	top + 1
循环队列元素个数	(rear - front + MaxSize) % MaxSize
循环队列判满（方案一）	(rear + 1) % MaxSize == front