抽象数据类型（ADT）

一、核心定义

抽象数据类型（Abstract Data Type，ADT）
指只描述数据对象、数据间关系、合法操作，不限定具体存储结构与实现细节的数据类型。

简单理解：对外暴露「功能接口」，隐藏内部「存储和代码实现」，是面向对象、封装思想在数据结构中的底层体现。

关键区分：
- ADT：侧重逻辑功能与操作规范（是什么、能做什么）
- 数据结构：侧重物理/逻辑存储实现（数组、链表、树，怎么做）

三要素

1. 数据对象：该类型包含的数据集合（如整数、学生信息、节点集合）
2. 数据关系：数据元素之间的逻辑关系（线性、树形、图形等）
3. 基本操作：对数据可执行的一组运算/行为（增、删、查、改、判空、求长度等）

二、核心思想：抽象与封装

1. 数据抽象
   使用者只需要知道「这个类型能做什么」，不需要知道数据存在内存哪里、怎么存。
   例：使用栈时，只需调用 push/pop，不用关心底层是数组还是链表。

2. 操作抽象
   统一操作接口，同一ADT可搭配多种存储结构实现，接口行为完全一致。
   例：栈 ADT 既可以用顺序表（数组）实现，也可以用链表实现，但对外 push/pop 用法不变。

3. 信息隐藏
   内部存储、底层算法全部屏蔽，修改实现代码不会影响上层调用代码，解耦性极强。

三、ADT 与相关概念辨析

1. 和编程语言基本数据类型的区别

编程语言内置类型（int、char、float）是语言层面基础类型；
ADT 是自定义的、逻辑层面的复杂类型，由基础类型组合而成，独立于任何编程语言。

2. 和结构体、类的区别

C 语言 struct、Java/Python class 只是语法载体，用来落地实现 ADT；
ADT 是纯粹逻辑概念，不依赖任何编程语言语法。

3. 逻辑结构、存储结构、ADT

• 逻辑结构：元素之间的关系（线性、树、图）
• 存储结构：内存中如何存放（顺序、链式、哈希）
• ADT：基于逻辑结构，定义「数据+操作」的完整抽象模型

补充：栈、队列本质属于线性逻辑结构，只是对线性表的操作位置加以限制，属于受限线性表 ADT。

ADT 与底层实现对照表

总结：数组、链表、红黑树、哈希表，都是为实现某一种 ADT 而设计的存储方案。

四、标准ADT描述格式

以栈举例：

ADT 栈(Stack)
数据对象：D = { a₁, a₂, ..., aₙ | 每个元素为同一数据类型 }
数据关系：R = { <aᵢ, aᵢ₊₁> | 元素线性相邻，仅栈顶可操作 }
基本操作：
    1. InitStack()：初始化空栈
    2. Push(e)：元素e入栈
    3. Pop(&e)：栈顶元素出栈，用e返回
    4. GetTop(&e)：读取栈顶元素，不弹出
    5. IsEmpty()：判断栈是否为空
    6. ClearStack()：清空栈
end ADT 栈

五、Python代码实践

代码遵循ADT「信息隐藏」思想：内部容器私有化，外部仅能通过公开接口访问。

示例1：栈ADT封装实现

class Stack:
    def __init__(self):
        self.__items = []  # 私有内部存储，外部禁止直接访问

    def push(self, item):
        """入栈"""
        self.__items.append(item)

    def pop(self):
        """出栈，空栈返回None"""
        if not self.is_empty():
            return self.__items.pop()

    def top(self):
        """获取栈顶元素，不删除"""
        if not self.is_empty():
            return self.__items[-1]

    def is_empty(self):
        """判空"""
        return len(self.__items) == 0

# 上层调用只依赖接口，不关心底层存储
s = Stack()
s.push(10)
s.push(20)
print(s.top())
s.pop()

示例2：队列ADT封装实现

from collections import deque

class Queue:
    def __init__(self):
        self.__container = deque()

    def enqueue(self, val):
        """队尾入队"""
        self.__container.append(val)

    def dequeue(self):
        """队头出队"""
        if not self.is_empty():
            return self.__container.popleft()

    def front(self):
        """获取队头元素"""
        if not self.is_empty():
            return self.__container[0]

    def is_empty(self):
        return len(self.__container) == 0

拓展：Python原生 list、deque、set、dict 都是经典ADT的现成实现。

六、ADT 的优势与设计意义

1. 实现解耦
   上层业务只依赖 ADT 接口，底层存储结构可随意替换，提升代码复用性与可维护性。
2. 统一抽象模型
   抛开编程语言、硬件差异，使用统一逻辑描述数据与操作，是数据结构通用设计语言。
3. 信息隐藏
   禁止外部直接操作内部数据，避免非法修改，程序更加健壮。
4. 算法通用化
   算法基于ADT接口编写，不绑定具体存储结构，算法通用性更强。

七、学习思路总结

1. 看到「栈、队列、线性表、集合」，优先理解为 ADT（规范、操作规则）；
2. 看到「数组、链表、红黑树、哈希表」，理解为 存储结构/具体实现；
3. 标准学习顺序：先定义 ADT 规范 → 选择存储结构 → 编码实现接口。