Большинство задач сводится к нескольким ADT: список, стек, очередь, дек, очередь с приоритетом, множество, словарь и граф. У каждого простые операции, а цена зависит от реализации. Этот урок даёт такой каталог: одну таблицу и несколько небольших примеров. Чем ADT отличается от структуры — в предыдущем уроке.
Каталог
По операциям выделяют четыре семейства: последовательности (список, стек, очередь, дек), очередь с приоритетом, ключ и принадлежность (множество, словарь) и связи (граф).
| ADT | Основные операции | Типичная реализация |
|---|---|---|
| List | get(i), insert, remove | динамический массив, связный список |
| Stack | push, pop, peek | list, связный список |
| Queue | enqueue, dequeue | deque, кольцевой буфер |
| Deque | push/pop с обоих концов | collections.deque |
| Priority queue | push, pop_min, peek | двоичная куча (heapq) |
| Set | add, remove, in | хеш-таблица, дерево |
| Map | put, get, delete | хеш-таблица, дерево |
| Graph | add_edge, neighbors | списки смежности, матрица |
Большинство этих ADT Python даёт готовыми:
