数据结构中的抽象数据类型 (ADT)

抽象数据类型 (ADT) 是数据结构的抽象，它只提供数据结构必须遵守的接口。该接口不提供关于应如何实现或使用何种编程语言的任何具体细节。

换句话说，我们可以说抽象数据类型是数据和操作的定义，但不包含实现细节。在这种情况下，我们知道要存储的数据以及可以对数据执行的操作，但我们不知道实现细节。之所以不包含实现细节，是因为每种编程语言都有不同的实现策略。例如，C 语言的数据结构使用结构来实现，而 C++ 的数据结构则使用对象和类来实现。

例如，列表 (List) 是一个抽象数据类型，可以使用动态数组和链表来实现。队列 (Queue) 可以使用基于链表的队列、基于数组的队列和基于栈的队列来实现。映射 (Map) 可以使用 TreeMap、HashMap 或 HashTable 来实现。

抽象数据类型模型

上图显示了 ADT 模型。ADT 模型中有两种模型，即公共函数和私有函数。ADT 模型还包含我们在程序中使用的那些数据结构。在此模型中，首先执行封装，即所有数据都被包装在一个单元中，即 ADT。然后，执行抽象，意味着显示可以在数据结构上执行的操作以及我们在程序中使用的那些数据结构。

让我们通过一个现实世界的例子来理解抽象数据类型。

如果我们考虑智能手机。我们看到智能手机的高规格，例如

• 4 GB RAM
• 骁龙 2.2GHz 处理器
• 5 英寸 LCD 屏幕
• 双摄像头
• Android 8.0

以上智能手机的规格就是数据，我们还可以对智能手机执行以下操作

• call(): 我们可以通过智能手机打电话。
• text(): 我们可以发短信。
• photo(): 我们可以拍照。
• video(): 我们还可以录制视频。

智能手机是一个实体，其数据或规格以及操作如上所示。抽象/逻辑视图和操作是智能手机的抽象或逻辑视图。

上述抽象/逻辑视图的实现视图如下

上面的代码是智能手机的规格和可执行操作的实现。实现视图可能会有所不同，因为编程语言的语法不同，但数据结构的抽象/逻辑视图将保持不变。因此，我们可以说抽象/逻辑视图独立于实现视图。

注意：我们知道可以在 int、float、char 等预定义数据类型上执行的操作，但我们不知道这些数据类型的实现细节。因此，我们可以说抽象数据类型被视为一个隐藏的盒子，它隐藏了数据类型的内部所有细节。

数据结构示例

假设我们有一个大小为 4 的索引数组。我们有一个从 0、1、2、3 开始的索引位置。数组是一种数据结构，其中元素存储在连续的位置。第一个元素的内存地址是 1000，第二个元素是 1004，第三个元素是 1008，第四个元素是 1012。由于它是整数类型，所以它占用 4 个字节，并且每个元素的地址之间的差值为 4 个字节。存储在数组中的值是 10、20、30 和 40。这些值、索引位置和内存地址是实现。

整数数组的抽象或逻辑视图可以表述为

• 它存储一组整数类型的元素。
• 它通过位置（即索引）读取元素。
• 它通过索引修改元素
• 它执行排序

整数数组的实现视图

常见的 ADT

现在，让我们来理解三个常见的 ADT：列表 (List)、栈 (Stack) 和队列 (Queue) ADT。

1. 列表 ADT

列表 ADT（抽象数据类型）是一系列按顺序排列的元素的集合，它提供了一组操作，而不提供内部实现的细节。它提供了一种有序的方式来存储、访问和修改数据。

列表的操作

列表 ADT 必须按顺序存储数据，并且必须具有以下操作：

• insert(): 用于在给定列表的任何位置插入元素。
• get(): 用于返回列表中任何给定位置的元素。
• remove(): 用于从非空列表中删除第一个出现的元素。
• removeAt(): 用于从非空列表中指定位置删除元素。
• replace(): 用于在任何位置用另一个元素替换一个元素。
• size(): 用于返回列表中元素的数量。
• isEmpty(): 如果列表为空，则返回 true 值；否则返回 false 值。
• isFull(): 如果列表已满，则返回 true 值；否则返回 false 值。仅适用于固定大小的实现（例如，基于数组的列表）。

2. 栈 ADT

栈 ADT 遵循 LIFO（后进先出）原则。它是一种线性数据结构。在栈 ADT 中，元素的添加和删除仅从一端进行，即栈的顶部。

栈的操作

删除和插入的顺序应符合栈 ADT 中的 LIFO 或 FILO 原则。它还必须支持以下操作

• push(): 用于将元素插入栈的一端，称为顶部。
• pop(): 用于移除并返回栈顶的元素，前提是栈不为空。
• peek(): 用于在不移除栈顶元素的情况下返回栈顶元素，前提是栈不为空。
• size(): 用于返回栈中存在的元素总数。
• isEmpty(): 如果栈为空，则返回 true 值；否则返回 false 值。
• isFull(): 如果栈已满，则返回 true 值；否则返回 false 值。仅适用于固定容量的栈（例如，基于数组的栈）。

3. 队列 ADT

遵循 FIFO（先进先出）原则的线性数据结构是队列 ADT。它允许元素从另一端（队头）移除，并在另一端（队尾）插入。

队列的操作

队列 ADT 的设计与栈 ADT 类似。它应该支持以下操作

• enqueue(): 用于在队列末尾插入元素。
• dequeue(): 用于移除并返回队列的第一个元素，前提是队列不为空。
• peek(): 用于在不移除队列的情况下返回队列的元素，前提是队列不为空。
• size(): 用于返回队列中存在的元素总数。
• isEmpty(): 如果队列为空，则返回 true 值；否则返回 false 值。

为什么使用 ADT？

在 Java 中使用 ADT 的原因如下

• 封装：在干净的接口背后隐藏复杂实现的细节。
• 可重用性：允许各种内部实现（例如，链表或数组），而无需更改外部使用。
• 模块化：通过逻辑分离简化更新和维护。
• 安全性：通过阻止直接访问并最大限度地减少意外更改和错误来保护数据。

ADT 的优点

• 封装：ADT 提供了一种将数据和操作封装到一个单元中的方法。从而使数据结构更易于修改和管理。
• 抽象：ADT 允许用户在不知道实现细节的情况下使用数据结构，这可以简化编程并减少错误。
• 数据结构独立性：ADT 可以使用不同的数据结构来实现。从而更容易适应不断变化的需求和需要。
• 信息隐藏：ADT 可以通过控制访问并阻止未经授权的修改来保护数据完整性。
• 模块化：一个 ADT 可以与其他 ADT 结合以生成更复杂的数据结构，这可以提高编程的模块化和灵活性。

ADT 的缺点

• 开销：ADT 的实现可能会产生一定的处理和内存开销，这会影响性能。
• 复杂性：ADT 的实现可能很复杂，特别是对于复杂且大型的数据结构。
• 学习曲线：要使用 ADT，需要了解其实现和用法，这需要时间和精力来学习。
• 有限的灵活性：某些 ADT 的功能可能有限，或者它们可能不适合所有类型的数据结构。
• 成本：ADT 的实现可能需要额外的投资和资源，这会增加开发成本。

结论

ADT 是面向对象编程和数据结构中的基本概念。ADT 允许开发人员创建更易于维护、更健壮和可重用的软件。它们促进模块化、抽象和灵活性。因此，它使得解决复杂问题变得更加容易。

抽象数据类型选择题

1. peek() 操作适用于_____________。

1. Stack
2. Queue
3. 两者
4. 都不是

2. 遵循 FIFO（先进先出）原则的线性数据结构是__________。

1. Stack
2. Queue
3. Array
4. 都不是

3. 遵循 LIFO（后进先出）原则的线性数据结构是

1. Stack
2. Queue
3. Array
4. 都不是

4. ___________ 是数据和操作的定义，但不包含实现细节的实体。

1. 多态
2. 可重用性
3. 抽象数据类型
4. 都不是

5. ADT 的优点是_____________。

1. 数据结构独立性
2. 信息隐藏
3. 封装
4. 以上全部