MoonBit月兔编程语言 现代编程思想 第八课 队列：可变数据实现

• 语言: 中文（简体）
• 格式: .pdf
• 来源: www.moonbitlang.cn

摘要

文档介绍了队列的实现方式，重点讲解了基于数组的循环队列和单向链表的实现方法。通过具体的函数操作（如push、pop）展示了队列的基本功能，并详细说明了循环队列在元素数量超出数组长度时的扩容机制。

AI总结

### 文档总结

本章节主要介绍了使用可变数据结构实现队列的方法，重点讲解了基于数组的循环队列和单向链表的实现方式。

#### 队列的基本概念
- 队列是一种先进先出（FIFO）的数据结构。
- 可以通过两个堆栈实现队列，但本节采用可变数据结构（循环队列和单向链表）进行实现。

#### 队列的函数实现（以整数队列为示例）
1. `make()`：创建空队列。
2. `push(self: Queue, t: Int) -> Queue`：向队列中添加元素。
3. `pop(self: Queue) -> Queue`：删除队列中的第一个元素。
4. `peek(self: Queue) -> Int`：查看队列的头元素。
5. `length(self: Queue) -> Int`：获取队列的长度。

#### 循环队列的实现
- 使用数组实现循环队列。
- 队列包含以下属性：
- `array`: 存储元素的数组。
- `start`: 队列的起始位置。
- `end`: 队列的结束位置（指向空闲位置）。
- `length`: 队列的当前长度。

- **添加元素**：
- 将元素存入`array[end]`，然后将`end`指针向后移动一位（超出数组长度则绕回队首）。
- 队列长度加1。

- **扩容操作**：
- 当队列长度等于数组长度时，需要扩容。
- 创建一个新数组（长度为原数组的两倍），并将原数组中的数据复制到新数组中。
- 调整`start`和`end`指针，并更新数组引用。

#### 示例操作

make().push(1).push(2).push(3).pop().pop().length() // 返回1

#### 总结
本章节通过循环队列和单向链表的实现，展示了如何使用可变数据结构实现队列。循环队列的实现包括数组的初始化、元素的添加与删除、以及队列的扩容操作，确保了队列在高效利用空间的同时支持动态扩展。