# 编程导论（2024-2025冬季学期）
## 第9章：数据结构
### 课程信息
- 授课教师：亚历山大·克劳斯博士（Dr.-Ing. Alexander Krause）
- 所属机构：多特蒙德工业大学（Technische Universität Dortmund）应用信息学12系系统软件工作组
- 课程链接：https://sys.cs.tu-dortmund.de/de/lehre/ws24/eidp/
- 联系邮箱：eidp-problems@ls12.cs.tu-dortmund.de

### 第9章核心内容
1. 数据结构基础
2. 抽象数据类型（ADT）
3. 栈（Stapel）
4. 队列（Schlange）
5. 列表（Liste）
6. 二叉搜索树（Binärer Suchbaum）
7. 图（Graph）
8. 补充知识：简单文件操作（Einfache Dateibehandlung）

## 1. 抽象数据类型（ADT）
### 1.1 定义
抽象数据类型（Abstract Data Type，ADT）是一个三元组 \((T, F, A)\)，其中：
- \(T\)：非空的数据对象集合
- \(F\)：操作集合（对数据对象的操作）
- \(A\)：非空的公理集合（解释操作的含义）

### 1.2 “抽象”的核心含义
- **不关注实现细节**：无需关心数据对象的具体存储方式（如数组、链表）
- **只描述操作效果**：定义操作“做什么”（WAS），而非“怎么做”（WIE）
- 示例：栈的“push”操作仅定义“将元素加入栈顶”，不规定底层用数组还是链表实现

### 1.3 ADT的关键特性
1. **通用性**：已知ADT的定义后，可在任意场景复用
2. **模板实现**：通常以模板（Template）形式编写，支持多种数据类型
3. **分离规范与实现**：
   - 规范（Spezifikation）：对外公开ADT的操作接口
   - 实现（Implementierung）：内部逻辑隐藏，后续可替换实现方式而不影响外部使用
4. **信息隐藏**：仅通过预设操作访问数据，避免直接操作底层存储

## 2. 线性数据结构：栈（Stapel/Stack）
### 2.1 定义与核心语义
- **类比**：堆叠的盘子——只能从顶部添加或移除盘子
- **工作语义**：LIFO（Last-In-First-Out，后进先出）
- **C++标准库支持**：`std::stack`、`std::deque`、`std::vector`（可作为栈的底层容器）

### 2.2 栈的核心操作
| 操作       | 功能描述                          |
|------------|-----------------------------------|
| `create()` | 创建一个空栈                      |
| `push(x)`  | 将元素`x`添加到栈顶              |
| `pop()`    | 移除栈顶元素（无返回值）          |
| `top()`    | 返回栈顶元素（不移除）            |
| `empty()`  | 判断栈是否为空（返回`bool`值）    |
| `full()`   | 判断栈是否已满（仅固定大小栈需要）|

### 2.3 操作示例流程
执行序列：`create()` → `empty()` → `push(3)` → `push(5)` → `push(2)` → `top()` → `pop()` → `top()` → `empty()`  
流程解析：
1. `create()`：栈为空（`[]`）
2. `empty()`：返回`true`
3. `push(3)`：栈变为`[3]`
4. `push(5)`：栈变为`[3,5]`
5. `push(2)`：栈变为`[3,5,2]`
6. `top()`：返回`2`（栈仍为`[3,5,2]`）
7. `pop()`：栈变为`[3,5]`
8. `top()`：返回`5`（栈仍为`[3,5]`）
9. `empty()`：返回`false`

### 2.4 栈的实现（基于数组）
#### 2.4.1 类定义（模板形式）
```cpp
template <typename T>
class Stack {
private:
    static constexpr int maxSize = 100;  // 栈的最大容量（固定）
    T data[maxSize];                     // 存储栈元素的数组
    int sz;                              // 栈指针：指向栈顶元素的索引（初始为-1）
    void error(const char* s);           // 错误处理（如栈空/满时操作）

public:
    Stack();                 // 构造函数（创建空栈）
    void push(T& x);         // 入栈：添加元素到栈顶
    void pop();              // 出栈：移除栈顶元素
    T top();                 // 获取栈顶元素
    bool empty();            // 判断栈是否为空
    bool full();             // 判断栈是否已满
};
```

#### 2.4.2 核心方法实现
1. **构造函数**：初始化栈指针为-1（表示空栈）
   ```cpp
   template <typename T>
   Stack<T>::Stack() : sz(-1) {}
   ```

2. **空/满判断**：
   ```cpp
   template <typename T>
   bool Stack<T>::empty() {
       return sz == -1;  // 栈指针为-1 → 空栈
   }

template <typename T>
   bool Stack<T>::full() {
       return sz == maxSize - 1;  // 栈指针达到最大索引 → 满栈
   }
   ```

3. **错误处理**：输出错误信息并终止程序（后续可替换为异常处理）
   ```cpp
   template <typename T>
   void Stack<T>::error(const char* s) {
       cerr << s << endl;  // 标准错误流输出（无缓冲区，即时显示）
       exit(1);            // 终止程序，返回1给操作系统
   }
   ```

4. **入栈（push）**：
   ```cpp
   template <typename T>
   void Stack<T>::push(T& x) {
       if (full()) error("栈已满（push失败）");  // 满栈检查
       data[++sz] = x;  // 栈指针先自增，再赋值（从索引0开始存储）
   }
   ```

5. **出栈（pop）与获取栈顶（top）**：
   ```cpp
   template <typename T>
   T Stack<T>::top() {
       if (empty()) error("栈为空（top失败）");  // 空栈检查
       return data[sz];  // 返回栈顶元素（栈指针不变）
   }

template <typename T>
   void Stack<T>::pop() {
       if (empty()) error("栈为空（pop失败）");  // 空栈检查
       sz--;  // 仅移动栈指针，无需显式删除元素（后续入栈会覆盖）
   }
   ```

#### 2.4.3 测试代码
```cpp
int main() {
    Stack<int> s;
    int i = 1;

// 填充栈（直到满栈）
    while (!s.full()) {
        s.push(i);
        ++i;
    }
    cout << "栈顶元素：" << s.top() << endl;  // 输出100（maxSize=100）

// 弹出90个元素
    for (int i = 1; i <= 90; ++i) {
        s.pop();
    }

// 输出剩余元素（从栈顶到栈底）
    while (!s.empty()) {
        cout << s.top() << endl;  // 输出10、9、...、1
        s.pop();
    }

// 尝试对空栈执行pop（触发错误）
    s.pop();  // 输出"栈为空（pop失败）"并终止程序
    return 0;
}
```

### 2.5 数组实现的优缺点
| 优点                     | 缺点                     |
|--------------------------|--------------------------|
| 实现简单，逻辑清晰       | 容量固定，无法动态扩展   |
| 方法执行效率高（直接数组访问） | 栈空/满时操作会终止程序（需优化为异常处理） |

### 2.6 改进方向
1. **异常处理替代`exit(1)`**：使用C++异常（如`std::out_of_range`），避免程序直接终止（详见第12章）
2. **动态扩容**：当栈满时，创建更大的动态数组（如原容量的2倍），拷贝原元素后释放旧数组（缺点：扩容时耗时较长）
3. **链表实现**：基于指针的动态栈，无固定容量限制（后续队列、列表会采用类似思路）

## 3. 线性数据结构：队列（Schlange/Queue）
### 3.1 定义与核心语义
- **类比**：超市排队——新成员从队尾加入，先到者从队首离开
- **工作语义**：FIFO（First-In-First-Out，先进先出）
- **C++标准库支持**：`std::queue`、`std::deque`、`std::list`

### 3.2 队列的核心操作
| 操作         | 功能描述                          |
|--------------|-----------------------------------|
| `create()`   | 创建一个空队列                    |
| `enqueue(x)` | 将元素`x`添加到队尾              |
| `dequeue()`  | 移除队首元素（无返回值）          |
| `front()`    | 返回队首元素（不移除）            |
| `empty()`    | 判断队列是否为空（返回`bool`值）  |
| `full()`     | 判断队列是否已满（仅固定大小队列需要）|

### 3.3 操作示例流程
执行序列：`create()` → `enqueue(3)` → `enqueue(5)` → `dequeue()` → `enqueue(2)` → `front()` → `dequeue()` → `front()`  
流程解析：
1. `create()`：队列为空（`[]`）
2. `enqueue(3)`：队列变为`[3]`
3. `enqueue(5)`：队列变为`[3,5]`
4. `dequeue()`：队列变为`[5]`
5. `enqueue(2)`：队列变为`[5,2]`
6. `front()`：返回`5`（队列仍为`[5,2]`）
7. `dequeue()`：队列变为`[2]`
8. `front()`：返回`2`

### 3.4 队列的实现方案
#### 3.4.1 方案1：基于数组的普通实现（存在缺陷）
- **思路**：用数组存储元素，`ez`（Endzeiger）指向队尾元素（初始为-1）
- **缺陷**：
  1. 每次`dequeue()`后，队首前的空间无法复用（如队列`[5,2]`执行`dequeue()`后，索引0的空间闲置）
  2. 解决方案1（元素前移）：`dequeue()`时将所有元素向左移1位——**效率极低**（时间复杂度O(n)）
  3. 解决方案2（循环数组/环形缓冲区）：添加`sz`（Startzeiger）指向队首，数组视为环形，通过取模（`%`）实现循环——**效率高，但仍为固定容量**

#### 3.4.2 方案2：基于指针的动态实现（推荐）
- **思路**：用链表存储元素，通过`sz`（队首指针）和`ez`（队尾指针）管理队列，支持动态扩容
- **类定义（模板形式）**：
  ```cpp
  template <typename T>
  class Queue {
  public:
      Queue();          // 构造函数（创建空队列）
      void enqueue(T& x);// 入队：添加元素到队尾
      void dequeue();   // 出队：移除队首元素
      T front();        // 获取队首元素
      bool empty();     // 判断队列是否为空
      void clear();     // 清空队列
      ~Queue();         // 析构函数（释放内存）

private:
      // 内部元素结构体：存储数据和下一个元素的指针
      struct Element {
          T data;
          Element* next;
      };
      Element* sz;      // 队首指针（指向第一个元素）
      Element* ez;      // 队尾指针（指向最后一个元素）
      void error(const char* info);  // 错误处理
  };
  ```

#### 3.4.3 核心方法实现
1. **构造函数与空判断**：
   ```cpp
   template <typename T>
   Queue<T>::Queue() {
       sz = ez = nullptr;  // 初始为空队列，指针均为nullptr
   }

template <typename T>
   bool Queue<T>::empty() {
       return sz == nullptr;  // 队首指针为nullptr → 空队列
   }
   ```

2. **错误处理与清空队列**：
   ```cpp
   template <typename T>
   void Queue<T>::error(const char* info) {
       cerr << info << endl;
       exit(1);  // 后续可替换为异常处理
   }

template <typename T>
   void Queue<T>::clear() {
       while (!empty()) {
           dequeue();  // 循环出队，释放所有元素
       }
   }
   ```

3. **析构函数**：
   ```cpp
   template <typename T>
   Queue<T>::~Queue() {
       clear();  // 清空队列，避免内存泄漏
   }
   ```

4. **入队（enqueue）**：
   ```cpp
   template <typename T>
   void Queue<T>::enqueue(T& x) {
       // 创建新元素（next初始为nullptr）
       Element* e = new Element{x, nullptr};
       if (empty()) {
           sz = e;  // 空队列时，队首和队尾均指向新元素
       } else {
           ez->next = e;  // 非空队列时，队尾元素的next指向新元素
       }
       ez = e;  // 更新队尾指针
   }
   ```

5. **出队（dequeue）与获取队首（front）**：
   ```cpp
   template <typename T>
   T Queue<T>::front() {
       if (empty()) error("队列为空（front失败）");
       return sz->data;  // 返回队首元素数据
   }

template <typename T>
   void Queue<T>::dequeue() {
       if (empty()) error("队列为空（dequeue失败）");
       Element* temp = sz;  // 暂存队首指针（避免内存泄漏）
       sz = sz->next;       // 队首指针指向第二个元素
       if (sz == nullptr) { // 若队列变为空，更新队尾指针
           ez = nullptr;
       }
       delete temp;  // 释放原队首元素的内存
   }
   ```

#### 3.4.4 测试代码
```cpp
int main() {
    Queue<int> q;

// 入队：2~11（共10个元素）
    for (int i = 2; i <= 11; ++i) {
        q.enqueue(i);
    }

// 出队5次，输出队首元素（2~6）
    for (int i = 1; i <= 5; ++i) {
        cout << q.front() << endl;
        q.dequeue();
    }

// 输出剩余元素（7~11）
    while (!q.empty()) {
        cout << q.front() << endl;
        q.dequeue();
    }

// 判断队列是否为空
    if (q.empty()) {
        cout << "队列为空" << endl;
    }

return 0;
}
```

## 4. 深拷贝与浅拷贝：拷贝构造函数与赋值运算符
### 4.1 问题背景：默认拷贝的缺陷
C++编译器会自动生成**浅拷贝**（flache Kopie）的拷贝构造函数和赋值运算符：
- 浅拷贝仅复制指针的值（而非指针指向的内容）
- 导致多个对象共享同一块内存，析构时会重复释放内存（程序崩溃）

**示例（队列浅拷贝问题）**：
```cpp
int main() {
    Queue<int> q;
    for (int i = 1; i <= 5; ++i) {
        q.enqueue(i);  // q: [1,2,3,4,5]
    }
    Queue<int> q2 = q;  // 浅拷贝：q2.sz = q.sz，q2.ez = q.ez
    q.dequeue();        // q: [2,3,4,5]，但q2.sz仍指向原队首（已被释放）
    q2.front();         // 访问非法内存，程序崩溃
    return 0;
}
```

### 4.2 解决方案：自定义拷贝构造函数

编程导论（2024-2025冬季学期）

第9章：数据结构

课程信息

授课教师：亚历山大·克劳斯博士（Dr.-Ing. Alexander Krause）
所属机构：多特蒙德工业大学（Technische Universität Dortmund）应用信息学12系系统软件工作组
课程链接：https://sys.cs.tu-dortmund.de/de/lehre/ws24/eidp/
联系邮箱：eidp-problems@ls12.cs.tu-dortmund.de

第9章核心内容

数据结构基础
抽象数据类型（ADT）
栈（Stapel）
队列（Schlange）
列表（Liste）
二叉搜索树（Binärer Suchbaum）
图（Graph）
补充知识：简单文件操作（Einfache Dateibehandlung）

1. 抽象数据类型（ADT）

1.1 定义

抽象数据类型（Abstract Data Type，ADT）是一个三元组 ((T, F, A))，其中： - (T)：非空的数据对象集合 - (F)：操作集合（对数据对象的操作） - (A)：非空的公理集合（解释操作的含义）

1.2 “抽象”的核心含义

不关注实现细节：无需关心数据对象的具体存储方式（如数组、链表）
只描述操作效果：定义操作“做什么”（WAS），而非“怎么做”（WIE）
示例：栈的“push”操作仅定义“将元素加入栈顶”，不规定底层用数组还是链表实现

1.3 ADT的关键特性

通用性：已知ADT的定义后，可在任意场景复用
模板实现：通常以模板（Template）形式编写，支持多种数据类型
分离规范与实现：
规范（Spezifikation）：对外公开ADT的操作接口
实现（Implementierung）：内部逻辑隐藏，后续可替换实现方式而不影响外部使用
信息隐藏：仅通过预设操作访问数据，避免直接操作底层存储

2. 线性数据结构：栈（Stapel/Stack）

2.1 定义与核心语义

类比：堆叠的盘子——只能从顶部添加或移除盘子
工作语义：LIFO（Last-In-First-Out，后进先出）
C++标准库支持：std::stack、std::deque、std::vector（可作为栈的底层容器）

2.2 栈的核心操作

操作	功能描述
`create()`	创建一个空栈
`push(x)`	将元素`x`添加到栈顶
`pop()`	移除栈顶元素（无返回值）
`top()`	返回栈顶元素（不移除）
`empty()`	判断栈是否为空（返回`bool`值）
`full()`	判断栈是否已满（仅固定大小栈需要）

2.3 操作示例流程

执行序列：create() → empty() → push(3) → push(5) → push(2) → top() → pop() → top() → empty()
流程解析： 1. create()：栈为空（[]） 2. empty()：返回true 3. push(3)：栈变为[3] 4. push(5)：栈变为[3,5] 5. push(2)：栈变为[3,5,2] 6. top()：返回2（栈仍为[3,5,2]） 7. pop()：栈变为[3,5] 8. top()：返回5（栈仍为[3,5]） 9. empty()：返回false

2.4 栈的实现（基于数组）

2.4.1 类定义（模板形式）

template <typename T>
class Stack {
private:
    static constexpr int maxSize = 100;  // 栈的最大容量（固定）
    T data[maxSize];                     // 存储栈元素的数组
    int sz;                              // 栈指针：指向栈顶元素的索引（初始为-1）
    void error(const char* s);           // 错误处理（如栈空/满时操作）

public:
    Stack();                 // 构造函数（创建空栈）
    void push(T& x);         // 入栈：添加元素到栈顶
    void pop();              // 出栈：移除栈顶元素
    T top();                 // 获取栈顶元素
    bool empty();            // 判断栈是否为空
    bool full();             // 判断栈是否已满
};

2.4.2 核心方法实现

构造函数：初始化栈指针为-1（表示空栈） cpp template <typename T> Stack<T>::Stack() : sz(-1) {}
空/满判断： ```cpp template bool Stack::empty() { return sz == -1; // 栈指针为-1 → 空栈 }

template bool Stack::full() { return sz == maxSize - 1; // 栈指针达到最大索引 → 满栈 } ```

错误处理：输出错误信息并终止程序（后续可替换为异常处理） cpp template <typename T> void Stack<T>::error(const char* s) { cerr << s << endl; // 标准错误流输出（无缓冲区，即时显示） exit(1); // 终止程序，返回1给操作系统 }
入栈（push）： cpp template <typename T> void Stack<T>::push(T& x) { if (full()) error("栈已满（push失败）"); // 满栈检查 data[++sz] = x; // 栈指针先自增，再赋值（从索引0开始存储） }
出栈（pop）与获取栈顶（top）： ```cpp template T Stack::top() { if (empty()) error("栈为空（top失败）"); // 空栈检查 return data[sz]; // 返回栈顶元素（栈指针不变） }

template void Stack::pop() { if (empty()) error("栈为空（pop失败）"); // 空栈检查 sz--; // 仅移动栈指针，无需显式删除元素（后续入栈会覆盖） } ```

2.4.3 测试代码

int main() {
    Stack<int> s;
    int i = 1;

    // 填充栈（直到满栈）
    while (!s.full()) {
        s.push(i);
        ++i;
    }
    cout << "栈顶元素：" << s.top() << endl;  // 输出100（maxSize=100）

    // 弹出90个元素
    for (int i = 1; i <= 90; ++i) {
        s.pop();
    }

    // 输出剩余元素（从栈顶到栈底）
    while (!s.empty()) {
        cout << s.top() << endl;  // 输出10、9、...、1
        s.pop();
    }

    // 尝试对空栈执行pop（触发错误）
    s.pop();  // 输出"栈为空（pop失败）"并终止程序
    return 0;
}

2.5 数组实现的优缺点

优点	缺点
实现简单，逻辑清晰	容量固定，无法动态扩展
方法执行效率高（直接数组访问）	栈空/满时操作会终止程序（需优化为异常处理）

2.6 改进方向

异常处理替代exit(1)：使用C++异常（如std::out_of_range），避免程序直接终止（详见第12章）
动态扩容：当栈满时，创建更大的动态数组（如原容量的2倍），拷贝原元素后释放旧数组（缺点：扩容时耗时较长）
链表实现：基于指针的动态栈，无固定容量限制（后续队列、列表会采用类似思路）

3. 线性数据结构：队列（Schlange/Queue）

3.1 定义与核心语义

类比：超市排队——新成员从队尾加入，先到者从队首离开
工作语义：FIFO（First-In-First-Out，先进先出）
C++标准库支持：std::queue、std::deque、std::list

3.2 队列的核心操作

操作	功能描述
`create()`	创建一个空队列
`enqueue(x)`	将元素`x`添加到队尾
`dequeue()`	移除队首元素（无返回值）
`front()`	返回队首元素（不移除）
`empty()`	判断队列是否为空（返回`bool`值）
`full()`	判断队列是否已满（仅固定大小队列需要）

3.3 操作示例流程

执行序列：create() → enqueue(3) → enqueue(5) → dequeue() → enqueue(2) → front() → dequeue() → front()
流程解析： 1. create()：队列为空（[]） 2. enqueue(3)：队列变为[3] 3. enqueue(5)：队列变为[3,5] 4. dequeue()：队列变为[5] 5. enqueue(2)：队列变为[5,2] 6. front()：返回5（队列仍为[5,2]） 7. dequeue()：队列变为[2] 8. front()：返回2

3.4 队列的实现方案

3.4.1 方案1：基于数组的普通实现（存在缺陷）

思路：用数组存储元素，ez（Endzeiger）指向队尾元素（初始为-1）
缺陷：
每次dequeue()后，队首前的空间无法复用（如队列[5,2]执行dequeue()后，索引0的空间闲置）
解决方案1（元素前移）：dequeue()时将所有元素向左移1位——效率极低（时间复杂度O(n)）
解决方案2（循环数组/环形缓冲区）：添加sz（Startzeiger）指向队首，数组视为环形，通过取模（%）实现循环——效率高，但仍为固定容量

3.4.2 方案2：基于指针的动态实现（推荐）

思路：用链表存储元素，通过sz（队首指针）和ez（队尾指针）管理队列，支持动态扩容
类定义（模板形式）： ```cpp template class Queue { public: Queue(); // 构造函数（创建空队列） void enqueue(T& x);// 入队：添加元素到队尾 void dequeue(); // 出队：移除队首元素 T front(); // 获取队首元素 bool empty(); // 判断队列是否为空 void clear(); // 清空队列 ~Queue(); // 析构函数（释放内存）

private: // 内部元素结构体：存储数据和下一个元素的指针 struct Element { T data; Element next; }; Element sz; // 队首指针（指向第一个元素） Element ez; // 队尾指针（指向最后一个元素） void error(const char info); // 错误处理 }; ```

3.4.3 核心方法实现

构造函数与空判断： ```cpp template Queue::Queue() { sz = ez = nullptr; // 初始为空队列，指针均为nullptr }

template bool Queue::empty() { return sz == nullptr; // 队首指针为nullptr → 空队列 } ```

错误处理与清空队列： ```cpp template void Queue::error(const char* info) { cerr << info << endl; exit(1); // 后续可替换为异常处理 }

template void Queue::clear() { while (!empty()) { dequeue(); // 循环出队，释放所有元素 } } ```

析构函数： cpp template <typename T> Queue<T>::~Queue() { clear(); // 清空队列，避免内存泄漏 }
入队（enqueue）： cpp template <typename T> void Queue<T>::enqueue(T& x) { // 创建新元素（next初始为nullptr） Element* e = new Element{x, nullptr}; if (empty()) { sz = e; // 空队列时，队首和队尾均指向新元素 } else { ez->next = e; // 非空队列时，队尾元素的next指向新元素 } ez = e; // 更新队尾指针 }
出队（dequeue）与获取队首（front）： ```cpp template T Queue::front() { if (empty()) error("队列为空（front失败）"); return sz->data; // 返回队首元素数据 }

template void Queue::dequeue() { if (empty()) error("队列为空（dequeue失败）"); Element* temp = sz; // 暂存队首指针（避免内存泄漏） sz = sz->next; // 队首指针指向第二个元素 if (sz == nullptr) { // 若队列变为空，更新队尾指针 ez = nullptr; } delete temp; // 释放原队首元素的内存 } ```

3.4.4 测试代码

int main() {
    Queue<int> q;

    // 入队：2~11（共10个元素）
    for (int i = 2; i <= 11; ++i) {
        q.enqueue(i);
    }

    // 出队5次，输出队首元素（2~6）
    for (int i = 1; i <= 5; ++i) {
        cout << q.front() << endl;
        q.dequeue();
    }

    // 输出剩余元素（7~11）
    while (!q.empty()) {
        cout << q.front() << endl;
        q.dequeue();
    }

    // 判断队列是否为空
    if (q.empty()) {
        cout << "队列为空" << endl;
    }

    return 0;
}

4. 深拷贝与浅拷贝：拷贝构造函数与赋值运算符

4.1 问题背景：默认拷贝的缺陷

C++编译器会自动生成浅拷贝（flache Kopie）的拷贝构造函数和赋值运算符： - 浅拷贝仅复制指针的值（而非指针指向的内容） - 导致多个对象共享同一块内存，析构时会重复释放内存（程序崩溃）

示例（队列浅拷贝问题）：

int main() {
    Queue<int> q;
    for (int i = 1; i <= 5; ++i) {
        q.enqueue(i);  // q: [1,2,3,4,5]
    }
    Queue<int> q2 = q;  // 浅拷贝：q2.sz = q.sz，q2.ez = q.ez
    q.dequeue();        // q: [2,3,4,5]，但q2.sz仍指向原队首（已被释放）
    q2.front();         // 访问非法内存，程序崩溃
    return 0;
}

4.2 解决方案：自定义拷贝构造函数

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

第九章