Какие основные структуры данных вы знаете и в каких случаях их применяете?

В разработке я постоянно опираюсь на знание структур данных, выбирая наиболее эффективную для конкретной операции.

Базовые структуры и их применение:

1. Массив (Array) / Список (List)

   • Что это: Упорядоченная коллекция элементов. Массив имеет фиксированный размер (в C++, Java), а список (Python list, Java ArrayList) — динамический.
   • Когда применяю: Когда нужен быстрый доступ по индексу (O(1)) или итерация по всем элементам. Например, для хранения последовательности сенсорных показаний.

     # Python list - динамический массив
     tasks = ['build', 'test', 'deploy']
     first_task = tasks[0]  # O(1) доступ
     tasks.append('monitor') # Амортизированное O(1) добавление в конец

2. Стек (Stack) — LIFO

   • Что это: "Последним пришел — первым ушел". Основные операции: push (добавить) и pop (удалить верхний).
   • Когда применяю: Для отмены операций (undo), парсинга выражений (проверка скобок), обхода графов в глубину (DFS).

     call_stack = []
     call_stack.append('main()')  # push
     call_stack.append('calculate()')
     last_called = call_stack.pop() # pop -> 'calculate()'

3. Очередь (Queue) — FIFO

   • Что это: "Первым пришел — первым ушел". Операции: enqueue (в конец) и dequeue (из начала).
   • Когда применяю: Для обработки задач в порядке поступления (например, очередь сообщений), обхода графов в ширину (BFS).

     from collections import deque
     task_queue = deque()
     task_queue.append('task1')  # enqueue
     task_queue.append('task2')
     next_task = task_queue.popleft() # dequeue -> 'task1'

4. Хеш-таблица (Hash Table) / Словарь (Dictionary) / Множество (Set)

   • Что это: Структура "ключ-значение", обеспечивающая в среднем O(1) на поиск, вставку и удаление.
   • Когда применяю: Для кэширования, подсчета частот, устранения дубликатов (множество), быстрой проверки принадлежности элемента.

     # Python dict
     cache = {'user:1001': 'John Doe', 'product:42': 'Laptop'}
     if 'user:1001' in cache:  # Быстрая проверка O(1)
     name = cache['user:1001']
     # Python set
     unique_tags = {'python', 'ml', 'backend'}
     unique_tags.add('devops')

5. Деревья (Trees)

   • Бинарное дерево поиска (BST): Позволяет хранить отсортированные данные с операциями поиска/вставки/удаления за O(log n) в сбалансированном случае. Применяю редко, так как на практике чаще нужны...
   • Балансированные деревья (AVL, Красно-черные): Лежат в основе реализаций std::map в C++ или TreeMap в Java для поддержания порядка.
   • Куча (Heap): Частично упорядоченная структура для быстрого извлечения минимума/максимума. Использую для реализации приоритетной очереди (например, в алгоритме Дейкстры).

6. Графы (Graphs)

   • Что это: Набор вершин (узлов) и ребер (связей). Могут быть представлены списком смежности (эффективно по памяти для разреженных графов) или матрицей смежности (быстрый запрос связи).
   • Когда применяю: Для моделирования сетей (социальных, дорожных), зависимостей между задачами, рекомендательных систем.

Выбор всегда зависит от преобладающих операций: частый поиск по ключу — хеш-таблица, необходимость порядка — сбалансированное дерево, FIFO-обработка — очередь.