1. 概述
在本篇文章中，我们将讨论三种常见的抽象数据类型（ADT）：列表（List）、队列（Queue）、栈（Stack）。我们将分别介绍它们的变体、基本操作以及使用数据结构实现的策略。
2. ADT 简介
数据类型用于定义变量可以存储的数据种类以及支持的操作。例如整型数据支持加减乘除等操作。
抽象数据类型（Abstract Data Type，ADT） 是一种数据类型的抽象模型。它定义了数据结构的逻辑行为和操作，但隐藏了具体的实现细节。使用 ADT 时，用户只需要知道“要做什么”，而无需关心“怎么做”。
在不同编程语言中，ADT 的实现方式不同。例如：
- C 语言中常用结构体（struct）实现
- Java 或 C++ 中则使用类（class）实现
尽管实现方式不同，ADT 所支持的操作是统一的。
ADT 的三大常见类型：
3. 列表（List）
列表是一种有序的数据集合，元素类型一致，数量有限。列表的“有序”是指元素有索引位置，而不是排序顺序。
3.1. 列表的类型
列表主要有三种类型：
- 有序列表（Ordered List）：元素按某种顺序排列，如数字或字母顺序
- 无序列表（Unordered List）：元素顺序由用户决定
- 索引列表（Indexed List）：通过索引访问元素
3.2. 列表的基本操作
列表支持以下基本操作：
isListEmpty()：判断是否为空insertElement(N)：在指定位置插入元素deleteElement(N)：删除指定位置的元素traverseList()：遍历整个列表
3.3. 列表的实现方式
使用数组实现
数组实现简单，但存在固定大小的问题。当数组满时，必须重新分配更大的空间并复制元素，效率较低。
✅优点：访问元素快（O(1)）
❌缺点：插入/删除慢（O(N)），内存浪费或溢出风险
使用链表实现
链表是一种更灵活的实现方式。每个节点包含数据和指向下一个节点的指针。
✅优点：动态扩容，插入/删除效率高
❌缺点：访问元素慢（O(N)）
4. 队列（Queue）
队列是一种线性 ADT，遵循 FIFO（先进先出）原则。插入操作在队尾（rear），删除操作在队头（front）。
4.1. 队列的类型
队列主要分为四类：
- 普通队列（Simple Queue）：严格 FIFO
- 循环队列（Circular Queue）：首尾相连，提高内存利用率
- 优先队列（Priority Queue）：根据优先级出队
- 双端队列（Deque）：两端均可插入/删除
4.2. 队列的基本操作
队列支持以下操作：
isQueueEmpty()：判断是否为空enqueue(value)：入队dequeue()：出队traverseQueue()：遍历队列
4.3. 队列的实现方式
使用数组实现
数组实现简单，但需要维护 front 和 rear 指针。插入/删除时需移动元素，效率较低。
✅优点：实现简单
❌缺点：固定大小，插入/删除开销大
使用链表实现
链表实现更灵活，使用 front 和 rear 指针分别指向队列首尾。
✅优点：动态扩容，插入/删除高效（O(1)）
❌缺点：查找效率低（O(N)）
5. 栈（Stack）
栈是一种线性 ADT，遵循 LIFO（后进先出）原则。所有插入和删除操作都在栈顶进行。
5.1. 栈的类型
栈主要分为两种类型：
- 寄存器栈（Register Stack）：位于 CPU，容量小
- 内存栈（Memory Stack）：容量大，深度可变
5.2. 栈的基本操作
栈支持以下操作：
isStackEmpty()：判断是否为空push(value)：压栈pop()：出栈traverseStack()：遍历栈
5.3. 栈的实现方式
使用数组实现
使用数组实现时，需要定义一个 top 变量来记录栈顶位置。初始时 top = -1。
✅优点：访问/插入/删除快（O(1)）
❌缺点：固定大小，扩容麻烦
使用链表实现
链表实现栈更灵活，每个节点包含数据和下一个节点指针，top 指针指向栈顶。
✅优点：动态扩容，操作高效
❌缺点：查找慢（O(N)）
6. 总结
本文我们介绍了三种常见的抽象数据类型（ADT）：
- 列表（List）：有序集合，支持随机访问
- 队列（Queue）：FIFO，适用于任务调度
- 栈（Stack）：LIFO，常用于函数调用、表达式求值
我们分别讨论了它们的类型、操作和实现方式，并对比了数组和链表实现的优缺点。
在实际开发中，选择合适的数据结构非常重要。例如：
- 如果需要频繁插入/删除，使用链表实现的列表或队列更合适
- 如果频繁访问元素，数组实现的列表更高效
- 如果需要实现函数调用栈，栈结构是最佳选择
掌握这些 ADT 的特性，有助于我们写出更高效、更健壮的程序 ✅