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

# 队列：可变数据结构实现 - 总结 ## 1. 队列基本概念 队列是一个先进先出（FIFO）的数据结构，用于元素的有序存取。本节介绍了使用可变数据结构实现队列，包括循环队列和单向链表两种方法。 ## 2. 循环队列实现 循环队列基于数组实现，包含以下字段： - `array`: 存储队列元素的数组 - `start`: 队首指针 - `end`: 队尾指针（指向下一个可放置的位置） - `length`: 队列中元素的数量 主要函数： - `push(t: Int)`: 添加元素。如果数组满，进行扩容。扩容时创建更大的数组并复制原数据。 - `pop()`: 删除元素并返回修改后的队列。 ## 3. 默认值初始化问题 在数组初始化时，应使用合适的默认值（如0），确保扩容和复制操作正确。 ## 4. 单向链表实现 链表节点结构： - `Node[T]`: 包含值`val`和可选的下一个节点`next`。 - `LinkedList[T]`: 包含头节点`head`和尾节点`tail`。 链表适用于高效插入和删除操作，避免了数组扩容的复杂性。 ## 5. 主要函数 队列需实现的核心函数包括： - `make()`: 创建空队列。 - `push(t: Int)`: 添加元素。 - `pop()`: 删除元素。 - `peek()`: 查看队首元素。 - `length()`: 查看队列长度。 ## 6. 总结 本节详细讲解了队列的可变数据结构实现方法，涵盖了循环队列的扩容操作和单向链表的结点结构，并介绍了相关函数的实现细节。tail递归和扩容机制是实现中的关键点。