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

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

С развитием компьютерных наук развивались и структуры данных. Наиболее часто используемые в программировании структуры данных включают:

1. Массив (Array) — это агрегатный тип данных, представляющий собой упорядоченный набор переменных одного типа. Массив — одна из самых базовых структур данных, присутствующая во всех языках программирования. Массив можно разделить на элементы; по типу элементов различают целочисленные, символьные, вещественные массивы, массивы указателей, структурные и т.д. Массивы могут быть одномерными, двумерными и многомерными.

2. Стек (Stack) — это особая линейная структура, в которой вставка и удаление элементов возможны только с одного конца. Стек работает по принципу LIFO (последним пришёл — первым ушёл): данные, вставленные первыми, помещаются на дно, а последние — на вершину; чтение происходит с вершины. Стеки часто используются в ассемблерных программах для сохранения контекста важных данных. Стек без элементов называется пустым стеком.

3. Очередь (Queue) — похожа на стек, также является особой линейной структурой. В отличие от стека, очередь допускает вставку только с одного конца (хвоста), а удаление — с другого (головы), работая по принципу FIFO (первым пришёл — первым ушёл). Очередь без элементов называется пустой очередью.

4. Связный список (Linked List) — структура данных, в которой элементы хранятся в виде узлов, связанных указателями. Физически элементы могут располагаться в памяти не последовательно. Каждый узел состоит из поля данных и поля указателя, хранящего адрес следующего элемента. Логический порядок элементов определяется последовательностью ссылок.

5. Дерево (Tree) — типичная нелинейная структура. Это конечное множество K из n узлов. В дереве есть ровно один корневой узел, не имеющий предшественников. Все остальные узлы имеют ровно одного предшественника и могут иметь m потомков (m ≥ 0).

6. Граф (Graph) — ещё одна нелинейная структура данных. В графе узлы обычно называют вершинами, а связи — рёбрами, представляющими собой упорядоченные пары вершин. Если между двумя вершинами существует ребро, они называются смежными.

7. Куча (Heap) — особая древовидная структура данных, обычно двоичная куча. Характеризуется тем, что значение корневого узла является минимальным или максимальным среди всех узлов, а оба поддерева корня также являются кучами.

8. Хеш-таблица (Hash Table) — основана на хеш-функции. Идея в том, что если в структуре существует запись с ключом T, то её можно найти в позиции F(T) без операции сравнения, просто вычислив хеш-функцию.

9. Циклическая очередь (Circular Queue) — линейная структура данных, работающая по принципу FIFO, в которой хвост соединён с головой, образуя кольцо. Также известна как «кольцевой буфер». Преимущество циклической очереди в том, что она позволяет повторно использовать освободившееся место. В обычной очереди после заполнения вставка нового элемента невозможна, даже если в начале есть свободное место. Циклическая очередь позволяет использовать эти ячейки для хранения новых значений.