Структуры данных

Стек работает по LIFO — последним пришёл, первым вышел — добавление и извлечение с одного конца, как стопка тарелок. Очередь работает по FIFO: добавление в конец, извлечение из начала. Обе дают O(1) на вставку и удаление.

Граф моделирует связи: вершины (узлы) соединены рёбрами, и напрямую связанные вершины — соседи. Он бывает направленным или ненаправленным, взвешенным или невзвешенным; направленное ребро A→B делает B соседом A, но не A соседом B.

Дерево — это связный ацикличный граф: n узлов, соединённых ровно n-1 рёбрами, с единственным путём между любыми двумя узлами. Обычно у него один корень, отношения родитель→потомок идут вниз, и циклов нет.

Двоичное дерево, где у каждого узла ≤2 потомка и держится инвариант BST: каждый ключ в левом поддереве меньше, а каждый в правом больше. Это даёт O(log n) на поиск и вставку при балансе, деградируя до O(n) при перекосе в цепочку.

Два способа: список смежности, где каждая вершина хранит своих соседей — O(V+E) памяти, удобно для разреженных графов; или матрица смежности, сетка V×V наличия ребра — O(V^2) памяти, зато O(1) на поиск ребра, что подходит плотным графам.

Куча — это полное двоичное дерево со свойством кучи: в min-heap каждый родитель ≤ своих потомков, поэтому минимум в корне. Она лежит в основе очереди с приоритетом с O(log n) на вставку и извлечение минимума и O(1) на просмотр; применяется в Dijkstra.