Appearance
Абстрактные Типы Данных (ADT). Концепция и проектирование
До сих пор мы создавали классы, ориентируясь на физические объекты (ParcelBox, RomanNumber) [IMAGE]. Однако в промышленной разработке классы чаще всего используются для управления структурами данных.
На этом уроке мы разберем фундаментальное архитектурное понятие — Абстрактный Тип Данных (ADT), поймем разницу между интерфейсом и реализацией, и спроектируем нашу первую строгую структуру данных «на бумаге».
1. Что такое Абстрактный Тип Данных (ADT)?
Определение
Абстрактный Тип Данных (Abstract Data Type / ADT) — это математическая модель для типов данных, где тип определяется исключительно его поведением (набором доступных операций и правил их взаимодействия), а не тем, как он устроен внутри памяти компьютера.
Простыми словами, ADT — это черный ящик или контракт:
- Он отвечает на вопрос: «Что этот объект умеет делать?»
- Он абсолютно игнорирует вопрос: «Как он это делает внутри?»
Пример из жизни: Музыкальный плеер
У любого плеера (ADT) есть кнопки: Play, Pause, Next. Для вас как пользователя это абстракция. Вам не важно, играет музыка с кассеты, компакт-диска или стримится по Wi-Fi из облака (это детали реализации). Главное — кнопки выполняют строго регламентированный контракт.
2. Классические примеры ADT
В программировании выделяют четыре главные базовые абстракции:
- Стек (Stack) — структура, работающая по принципу LIFO (Last In, First Out — «последним пришел, первым ушел»). Примеры: стопка тарелок или история переходов в браузере (кнопка «Назад» возвращает последнюю посещенную страницу).
- Очередь (Queue) — структура, работающая по принципу FIFO (First In, First Out — «первым пришел, первым ушел»). Пример: реальная очередь в магазине или очередь документов на печать в принтер.
- Список (List) — упорядоченная последовательность элементов, где мы можем получить доступ к любому элементу по его порядковому номеру (индексу).
- Карта / Словарь (Map / Dictionary) — ассоциативный массив, где данные хранятся парами «Ключ — Значение». Доступ к элементу происходит не по индексу, а по уникальному ключу (например, по номеру паспорта).
3. Проектирование ADT «Стек» для Почтовой Коробки
Давайте решим бизнес-задачу. Наша почтовая коробка ParcelBox должна превратиться в контейнер типа Стек [IMAGE]. В глубокую картонную коробку вещи складываются друг на друга. Мы физически не можем достать самую нижнюю вещь, пока не снимем верхние.
Спроектируем класс ParcelStack (Почтовый Стек) с минимально необходимым набором методов для соблюдения контракта ADT Стек:
push(item)— положить вещь на самый верх стопки.pop()— снять и вернуть вещь с самого верха стопки.size()— узнать текущее количество вещей.
Реализация контракта без использования «магии»:
python
class ParcelStack:
"""Абстрактный тип данных (ADT) Стек, адаптированный для почтовых отправлений.
Работает по принципу LIFO (Last In, First Out).
"""
def __init__(self) -> None:
"""Инициализирует пустой стек для хранения вещей."""
# Внутри мы используем обычный список Python — это наша деталь реализации.
# Но внешнему пользователю об этом знать не обязательно.
self._storage: list[str] = []
def push(self, item: str) -> None:
"""Добавляет предмет на самый верх стека (в коробку).
Args:
item (str): Название предмета (например, 'Книга').
"""
self._storage.append(item)
def pop(self) -> str:
"""Извлекает и возвращает предмет с самого верха стека.
Returns:
str: Название извлеченного предмета.
Raises:
IndexError: Если совершена попытка достать вещь из пустой коробки.
"""
if self.is_empty():
raise IndexError("Невозможно извлечь предмет: почтовая коробка пуста!")
# .pop() встроенного списка Python идеально удаляет элемент с конца
return self._storage.pop()
def size(self) -> int:
"""Возвращает текущее количество предметов в коробке."""
return len(self._storage)
def is_empty(self) -> bool:
"""Проверяет, пуста ли коробка."""
return self.size() == 0
def __repr__(self) -> str:
return f"ParcelStack(items_count={self.size()})"
# === Проверка соблюдения контракта ADT ===
if __name__ == "__main__":
box = ParcelStack()
# Складываем вещи в коробку (в стопку)
box.push("Книга")
box.push("Свитер")
box.push("Чашка")
print(f"Всего вещей в коробке: {box.size()}") # Вывод: 3
# Достаем вещи. Первая должна выйти 'Чашка', так как её положили последней!
print(f"Достали: {box.pop()}") # Вывод: Чашка
print(f"Достали: {box.pop()}") # Вывод: Свитер
print(f"Осталось вещей: {box.size()}") # Вывод: 1В чем проблема такого кода?
Этот код отлично работает. Но он не выглядит «родным» для Python. Чтобы узнать размер, нам приходится писать box.size() вместо привычного len(box). Чтобы положить вещь, мы пишем box.push(), а не используем индексы box[0].
Проверьте себя (автопроверка)
Выполните каждый блок кода и сравните фактический вывод с ожидаемым, записанным в конце строки комментариями. Класс ParcelStack уже определён в теории урока.
Тест 1. Порядок LIFO — извлечение в обратном порядке:
python
stack = ParcelStack()
stack.push("Книга")
stack.push("Свитер")
stack.push("Чашка")
print(stack.pop(), stack.pop(), stack.pop()) # Чашка Свитер КнигаТест 2. Попытка извлечения из пустого стека:
python
empty = ParcelStack()
try:
empty.pop()
except IndexError as err:
print(err) # Невозможно извлечь предмет: почтовая коробка пуста!Тест 3. Состояние стека после цепочки операций:
python
s = ParcelStack()
s.push("Чашка")
s.push("Книга")
s.pop()
print(s.size(), s.is_empty()) # 1 FalseПояснения к ответам
Тест 1. Стек работает по принципу LIFO: последним добавленный элемент Чашка извлекается первым, затем Свитер, затем Книга.
Тест 2. Контракт ADT «Стек» явно определяет поведение на пустой структуре: pop() выбрасывает IndexError с диагностическим сообщением, а не возвращает None — так ошибки видны сразу.
Тест 3. После push("Чашка"), push("Книга") и одного pop() (снял Книга) в коробке осталась одна вещь, поэтому size() == 1, а is_empty() — False.
Проверьте себя
Что такое Абстрактный Тип Данных (ADT)?
По какому принципу работает стек (Stack)?
По какому принципу работает очередь (Queue)?
Какой минимальный набор методов задаёт контракт ADT «Стек» в уроке?
Что делает `pop()` на пустом стеке?
Как в `ParcelStack` хранятся вещи и насколько это важно пользователю?
Упражнения
Выполните эти задания, чтобы закрепить понимание концепции разделения абстрактного интерфейса («контракта») и его внутренней реализации. Все классы на данном этапе должны быть реализованы через явные именованные методы, без использования магических дандер-методов.
Упражнение 1: Проектирование ADT «Очередь» (ParcelQueue)
Представьте автоматическую конвейерную ленту на почтовом складе. Коробки заезжают на ленту с одной стороны, а съезжают с другой. Это классический пример ADT Очередь (FIFO — First In, First Out).
Задание: Создайте класс ParcelQueue (Почтовая Очередь):
- Внутри конструктора инициализируйте защищенный список
_storageдля хранения названий посылок. - Реализуйте метод
enqueue(parcel_name: str) -> None— добавить посылку в самый конец очереди. - Реализуйте метод
dequeue() -> str— извлечь и вернуть посылку из самого начала очереди. Если очередь пуста, метод должен выбрасывать исключениеIndexError. - Реализуйте метод
peek() -> str— посмотреть название первой посылки на выход, но не удалять её из очереди. - Реализуйте вспомогательные методы
size() -> intиis_empty() -> bool.
python
# Ожидаемое поведение:
# queue = ParcelQueue()
# queue.enqueue("Посылка №1")
# queue.enqueue("Посылка №2")
#
# print(queue.peek()) # Вывод: Посылка №1
# print(queue.dequeue()) # Вывод: Посылка №1
# print(queue.dequeue()) # Вывод: Посылка №2Упражнение 2: Двусторонняя Очередь (ParcelDeque)
В логистике часто применяется ADT Дек (Deque — Double Ended Queue). Это двусторонняя очередь, которая позволяет эффективно добавлять и извлекать элементы как с начала, так и с конца структуры. Представьте разгрузочную рампу, к которой коробки можно подвозить с двух сторон.
Задание: Создайте класс ParcelDeque:
- Реализуйте методы добавления:
add_front(item)(в начало) иadd_rear(item)(в конец). - Реализуйте методы извлечения:
remove_front()(из начала) иremove_rear()(из конца). При попытке извлечь элемент из пустого дека должно генерироваться исключениеIndexError. - Добавьте метод
size().
python
# Ожидаемое поведение:
# deque = ParcelDeque()
# deque.add_rear("Коробка А") # Сзади
# deque.add_front("Коробка Б") # Спереди
# # Теперь структура выглядит так: ["Коробка Б", "Коробка А"]
#
# print(deque.remove_rear()) # Вывод: Коробка А
# print(deque.remove_front()) # Вывод: Коробка БУпражнение 3: Ограниченный Стек (BoundedParcelStack)
Реальные почтовые коробки имеют физические ограничения по объему. Абстрактный тип данных «Ограниченный Стек» накладывает жесткий лимит на максимальное количество хранимых элементов.
Задание: Модифицируйте концепцию базового Стека и создайте класс BoundedParcelStack:
- Конструктор должен принимать обязательный параметр
max_size: int— максимальную вместимость коробки. - Метод
push(item: str) -> Noneдолжен проверять, есть ли свободное место. Если стек уже заполнен до предела, метод обязан выбросить кастомное или стандартное исключениеOverflowErrorс текстом"Коробка переполнена, вещь не помещается!". - Реализуйте стандартный метод
pop(), а также методis_full() -> bool.
python
# Ожидаемое поведение:
# small_box = BoundedParcelStack(max_size=2)
# small_box.push("Книга")
# small_box.push("Свитер")
#
# # Третий push должен вызвать ошибку
# small_box.push("Чашка") # raise OverflowErrorУпражнение 4: ADT «Словарь посылок» (ParcelMap)
Почтовому отделению необходима структура данных для отслеживания посылок по их уникальному трек-номеру. Это классический пример ADT Ассоциативный массив (Map / Dictionary). Ваша задача — написать собственную простую обертку, имитирующую этот контракт.
Задание: Создайте класс ParcelMap:
- Внутри конструктора используйте список кортежей
_storage: list[tuple[str, str]], где каждый элемент — это пара(track_number, parcel_description). Вы не можете использовать встроенный словарь{}Python, так как вы проектируете эту структуру с нуля на базе списков. - Реализуйте метод
put(key: str, value: str) -> None— добавить или обновить описание посылки для конкретного трек-номера. Метод должен пройтись по списку: если ключ уже есть — обновить значение, если нет — добавить новую пару. - Реализуйте метод
get(key: str) -> str— найти и вернуть описание по трек-номеру. Если трек-номер не найден, выбросить исключениеKeyError. - Реализуйте метод
remove(key: str) -> None— удалить запись из списка.
python
# Ожидаемое поведение:
# post_office = ParcelMap()
# post_office.put("RU123", "Смартфон")
# post_office.put("RU456", "Ноутбук")
#
# print(post_office.get("RU123")) # Вывод: Смартфон
# post_office.put("RU123", "Новый Смартфон")
# print(post_office.get("RU123")) # Вывод: Новый СмартфонУпражнение 5: Стек с поддержкой приоритетного извлечения хрупких вещей (SafeParcelStack)
Давайте усложним контракт Стека бизнес-логикой. Представьте, что в стопку вещей в коробке могут быть добавлены хрупкие предметы. При извлечении через метод pop() мы обязаны соблюдать LIFO, но если на самом верху лежит хрупкий предмет, мы должны извлечь его особым, безопасным способом.
Задание: Создайте класс SafeParcelStack:
- Метод
push(item: str, is_fragile: bool = False) -> Noneтеперь принимает кортеж или объект, содержащий название вещи и флаг её хрупкости. - Реализуйте метод
pop() -> str, который возвращает только имя вещи с вершины стека. - Реализуйте метод
pop_fragile() -> str. Этот метод проверяет вещь на вершине стека. Если она хрупкая (is_fragile=True), он безопасно извлекает её и возвращает строку вида"Успешно извлечена хрупкая вещь: {item}". Если вещь на вершине не является хрупкой, метод должен выбросить исключениеValueError("На вершине стопки обычная вещь. Используйте стандартный pop.").
Эталонные решения для самопроверки
Посмотреть решение Упражнения 1 (ParcelQueue)
python
class ParcelQueue:
def __init__(self) -> None:
self._storage: list[str] = []
def enqueue(self, parcel_name: str) -> None:
self._storage.append(parcel_name)
def dequeue(self) -> str:
if self.is_empty():
raise IndexError("Очередь посылок пуста!")
return self._storage.pop(0)
def peek(self) -> str:
if self.is_empty():
raise IndexError("Очередь посылок пуста!")
return self._storage[0]
def size(self) -> int:
return len(self._storage)
def is_empty(self) -> bool:
return self.size() == 0
# Демонстрация:
queue = ParcelQueue()
queue.enqueue("Посылка №1")
queue.enqueue("Посылка №2")
print(queue.peek()) # Посылка №1
print(queue.dequeue()) # Посылка №1
print(queue.dequeue()) # Посылка №2Посмотреть решение Упражнения 2 (ParcelDeque)
python
class ParcelDeque:
def __init__(self) -> None:
self._storage: list[str] = []
def add_front(self, item: str) -> None:
self._storage.insert(0, item)
def add_rear(self, item: str) -> None:
self._storage.append(item)
def remove_front(self) -> str:
if self.is_empty():
raise IndexError("Дек пуст!")
return self._storage.pop(0)
def remove_rear(self) -> str:
if self.is_empty():
raise IndexError("Дек пуст!")
return self._storage.pop()
def size(self) -> int:
return len(self._storage)
def is_empty(self) -> bool:
return self.size() == 0
# Демонстрация:
d = ParcelDeque()
d.add_rear("Коробка А")
d.add_front("Коробка Б")
print(d.remove_rear()) # Коробка А
print(d.remove_front()) # Коробка БПосмотреть решение Упражнения 3 (BoundedParcelStack)
python
class BoundedParcelStack:
def __init__(self, max_size: int) -> None:
self.max_size: int = max_size
self._storage: list[str] = []
def push(self, item: str) -> None:
if self.is_full():
raise OverflowError("Коробка переполнена, вещь не помещается!")
self._storage.append(item)
def pop(self) -> str:
if self.is_empty():
raise IndexError("Коробка пуста!")
return self._storage.pop()
def is_full(self) -> bool:
return len(self._storage) >= self.max_size
def is_empty(self) -> bool:
return len(self._storage) == 0
def size(self) -> int:
return len(self._storage)
# Демонстрация:
small_box = BoundedParcelStack(max_size=2)
small_box.push("Книга")
small_box.push("Свитер")
try:
small_box.push("Чашка")
except OverflowError as err:
print(err) # Коробка переполнена, вещь не помещается!Посмотреть решение Упражнения 4 (ParcelMap на списках)
python
class ParcelMap:
def __init__(self) -> None:
self._storage: list[tuple[str, str]] = []
def put(self, key: str, value: str) -> None:
for idx, (k, v) in enumerate(self._storage):
if k == key:
self._storage[idx] = (key, value)
return
self._storage.append((key, value))
def get(self, key: str) -> str:
for k, v in self._storage:
if k == key:
return v
raise KeyError(f"Трек-номер {key} не найден в базе данных!")
def remove(self, key: str) -> None:
for idx, (k, v) in enumerate(self._storage):
if k == key:
self._storage.pop(idx)
return
raise KeyError(f"Трек-номер {key} не найден для удаления!")
# Демонстрация:
post_office = ParcelMap()
post_office.put("RU123", "Смартфон")
post_office.put("RU456", "Ноутбук")
print(post_office.get("RU123")) # Смартфон
post_office.put("RU123", "Новый Смартфон")
print(post_office.get("RU123")) # Новый СмартфонПосмотреть решение Упражнения 5 (SafeParcelStack)
python
class SafeParcelStack:
def __init__(self) -> None:
self._storage: list[tuple[str, bool]] = []
def push(self, item: str, is_fragile: bool = False) -> None:
self._storage.append((item, is_fragile))
def pop(self) -> str:
if not self._storage:
raise IndexError("Коробка пуста!")
item, is_fragile = self._storage.pop()
return item
def pop_fragile(self) -> str:
if not self._storage:
raise IndexError("Коробка пуста!")
# Смотрим на верхний элемент без удаления
item, is_fragile = self._storage[-1]
if not is_fragile:
raise ValueError("На вершине стопки обычная вещь. Используйте стандартный pop.")
# Если вещь хрупкая, удаляем её окончательно
self._storage.pop()
return f"Успешно извлечена хрупкая вещь: {item}"
# Демонстрация:
safe = SafeParcelStack()
safe.push("Книга")
safe.push("Хрустальная ваза", is_fragile=True)
print(safe.pop_fragile()) # Успешно извлечена хрупкая вещь: Хрустальная ваза
try:
safe.pop_fragile()
except ValueError as err:
print(err) # На вершине стопки обычная вещь. Используйте стандартный pop.
print(safe.pop()) # Книга