Что такое структура данных и какие виды вы знаете (Стек, etc)?angular-11

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

Основные виды структур данных

1. Линейные структуры

Элементы располагаются последовательно друг за другом.

• Массив (Array)
  Фиксированный размер, элементы одного типа, доступ по индексу.

  const arr: number[] = [1, 2, 3];
  

• Связный список (Linked List)
  Элементы (узлы) связаны через указатели. Бывают односвязные и двусвязные.

  interface Node<T> {
    value: T;
    next?: Node<T>;
  }
  

• Стек (Stack)
  LIFO (Last In, First Out). Основные операции: push и pop.

  const stack: number[] = [];
  stack.push(1); // Добавление
  stack.pop();   // Удаление
  

• Очередь (Queue)
  FIFO (First In, First Out). Основные операции: enqueue и dequeue.

  const queue: number[] = [];
  queue.push(1); // Добавление в конец
  queue.shift(); // Удаление из начала
  

2. Нелинейные структуры

Элементы связаны сложными отношениями (иерархия, сеть и т.д.).

• Дерево (Tree)
  Иерархическая структура с корневым узлом и потомками. Пример: бинарное дерево.

  interface TreeNode<T> {
    value: T;
    left?: TreeNode<T>;
    right?: TreeNode<T>;
  }
  

• Граф (Graph)
  Набор вершин и рёбер. Бывают направленные и ненаправленные.

  type Graph = Record<string, string[]>;
  const graph: Graph = { A: ['B', 'C'] };
  

• Хеш-таблица (Hash Table)
  Ключ-значение с быстрым доступом через хеш-функцию.

  const map = new Map<string, number>();
  map.set('key', 123);
  

3. Другие важные структуры

• Множество (Set)
  Хранит уникальные значения без порядка.

  const set = new Set<number>([1, 2, 2]); // {1, 2}
  

• Куча (Heap)
  Специализированное дерево для реализации очередей с приоритетом.

Резюмируем

Структуры данных делятся на линейные (массивы, списки, стеки, очереди) и нелинейные (деревья, графы). Выбор структуры зависит от задачи:

• Стек для отмены операций (undo),
• Очередь для обработки задач в порядке поступления,
• Хеш-таблица для быстрого поиска,
• Деревья для иерархических данных (например, DOM).