什么是抽象数据类型 (ADT)，为什么要将其与实现分离？

Question

IT Interview Practice · Accepted Answer

**抽象数据类型** 定义了一组值和允许对其进行的**操作**，仅通过**行为**来描述 — 而不是通过代码。实现是实现该行为的具体结构（数组、链表、树）。

## 相同的 ADT，不同的实现

```text
ADT "Queue":  enqueue, dequeue, peek  (FIFO contract)

Implementation A: array + two indices (ring buffer)
Implementation B: doubly linked list with head/tail pointers
Both honor the SAME contract; cost profiles differ.
```

## 为什么要分离它们

```python
# Callers depend on the CONTRACT, not the internals
class Stack:
    def push(self, x): ...
    def pop(self): ...
    def peek(self): ...
# Swap a list for a linked list internally — callers never change.
```

## 常见的 ADT 和典型实现

| ADT | 常见实现 |
|---|---|
| List | 动态数组、链表 |
| Stack | 数组、链表 |
| Queue | 环形缓冲区、链表 |
| Map | 哈希表、平衡树 |
| Priority Queue | 二叉堆 |

## 为什么这很重要

针对 ADT（接口）编程可以使代码保持灵活性：你可以稍后优化实现而不会破坏调用者。

它还能增强推理能力 — 你首先决定**需要什么行为**，然后选择提供该行为的最廉价的结构。

ADT	常见实现
List	动态数组、链表
Stack	数组、链表
Queue	环形缓冲区、链表
Map	哈希表、平衡树
Priority Queue	二叉堆

相同的 ADT，不同的实现

为什么要分离它们

相关问题

常见的 ADT 和典型实现

为什么这很重要