Что такое абстрактный тип данных (ADT) и почему его нужно отделять от реализации?

Question

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 | dynamic array, linked list |
| Stack | array, linked list |
| Queue | ring buffer, linked list |
| Map | hash table, balanced tree |
| Priority Queue | binary heap |

## Почему это важно

Программирование в контексте ADT (интерфейса) делает код гибким: вы сможете оптимизировать реализацию позже, не ломая вызывающий код.

Это также обостряет логику рассуждений — сначала вы решаете, *какое поведение* вам нужно, а потом выбираете наиболее дешёвую структуру, которая его обеспечивает.

ADT	Типичные реализации
List	dynamic array, linked list
Stack	array, linked list
Queue	ring buffer, linked list
Map	hash table, balanced tree
Priority Queue	binary heap