4. Стек очередь двунаправленная очередь
Стек - структура данных (абстрактный тип данных), представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO). Системы программирования для блочно-ориентированных языков (Pascal, С и др.) используют стек для размещения в нем локальных переменных процедур и иных программных блоков. При каждой активизации процедуры память для ее локальных переменных выделяется в стеке; при завершении процедуры эта память освобождается. Поскольку при вызовах процедур всегда строго соблюдается вложенность, то в вершине стека всегда находится память, содержащая локальные переменные активной в данный момент процедуры.
Пример стека - это стопка бумаги, в которой обязательно первым берётся именно тот лист, который был положен в неё последним.
Способы реализации стека:
С помощью одномерного массива
С помощью связанного списка
С помощью класса ООП
Очередь - структура данных (абстрактный тип данных), представляющая из себя упорядоченный набор элементов, которые могут удаляться с её начала и помещаться в её конец. Для обозначения очереди в программировании - FIFO. Это аббревиатура от английской фразы "first in, first out", т.е. "первый вошёл - первый вышел". Добавление и удаление элементов происходит путём операций push и pop соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым. У очереди имеется голова (англ. head) и хвост (англ. tail). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. В исходном состоянии указатели на начало и на конец указывают на начало области памяти. Равенство этих двух указателей (при любом их значении) является признаком пустой очереди.
Способы реализации очереди:
С помощью одномерного массива
С помощью связанного списка
С помощью класса ООП
Двунаправленная очередь (дек) - структура данных типа «список», представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Эта структура поддерживает как FIFO, так и LIFO, поэтому на ней можно реализовать как стек, так и очередь. Определить дек можно как очередь с двумя сторонами, так и стек, имеющий два конца.
Способы реализации двунаправленной очереди:
на двусвязном списке
на двух стеках
на массиве
5. Деревья.
Дерево – это иерархическая структура данных, состоящая из вершин (узлов) и ребер, соединяющих их. Они похожи на графы, но есть одно важное отличие: в дереве не может быть цикла. Деревья широко используются в искусственном интеллекте и сложных алгоритмах для обеспечения эффективного механизма хранения данных. Вот изображение простого дерева, и основные термины:
Типы деревьев:
- N-арное дерево (неориентированное) – это конечный связный граф с выделенной вершиной (корнем) без циклов. N-арное дерево (ориентированное) - ориентированный граф без циклов, во все вершины которого, кроме одной, входит ровно одна дуга.
- Двоичное дерево - иерархическая структура данных, в которой каждый узел имеет не более двух потомков
- Двоичное дерево поиска – это двоичное дерево, для которого выполняются следующие дополнительные условия: оба поддерева - левое и правое - являются двоичными деревьями поиска, у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X и у всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равны, нежели значение ключа данных самого узла X.
- Сбалансированное дерево поиска - дерево поиска, в котором высота поддеревьев любого узла различаются не более чем на заданную константу k.
- АВЛ-дерево - сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
- Красно-черное дерево (Red-black tree, RB-tree) – это бинарное дерево поиска, для которого выполняются красно-черные свойства (red-black properties):
1) каждый узел является красным или черным
2) корень дерева является черным
3) каждый лист дерева (NULL) является черным
4) у красного узла оба дочерних узла – черные
5) у любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество черных узлов
Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех, и других), или как элементы массива, связанные между собой отношениями, определенными их позициями в массиве.
Обходы деревьев:
1) Прямой обход. Посетить корень, Обойти левое поддерево. Обойти правое поддерево.
2) Симметричный или поперечный. Обойти левое поддерево. Посетить корень. Обойти правое поддерево.
3) В обратном порядке. Обойти левое поддерево. Обойти правое поддерево. Посетить корень.
4) В ширину. Подразумевается, что сначала мы посещаем корень, затем, слева направо, все ветви первого уровня, затем все ветви второго уровня и т.д.