Что такое структура данных
Структура данных в программировании — это объект для организации, хранения и доступа к данным в памяти компьютера. Есть разные структуры данных. Например, массив подходит для хранения коллекции одинаковых элементов фиксированного размера. Это может быть список с датами рождения. С другой стороны, связанный список более гибок: он позволяет динамически добавлять или удалять элементы.
Структура данных — не язык программирования. Это набор алгоритмов, которые можно использовать на любом языке программирования для организации данных в памяти.
Виды структур данных
У структур данных есть определенные характеристики:
- линейные или нелинейные — эта характеристика упорядочивает данные в последовательном порядке, например, в виде массивов, графиков;
- статические и динамические — статические структуры данных имеют фиксированные форматы и размеры, а также ячейки памяти. Статическая характеристика показывает компиляцию данных. В динамической структуре данных размер структуры не фиксирован и может изменяться в ходе выполняемых над ней операций. Динамические структуры данных облегчают изменение индекса или очереди во время выполнения;
- корректность — данные обязательно должны иметь интерфейс. Интерфейс отображает набор структур данных. Структура данных должна быть точно реализована в интерфейсе.
Линейные структуры данных:
- массив — совокупность одинаковых элементов данных, хранящихся в смежных ячейках памяти. Это простейшая структура данных, в которой к каждому элементу можно получить прямой доступ. Для этой операции используется его порядковый номер;
- связанный список — линейная структура данных, которая используется для поддержания структуры, подобной списку, в памяти компьютера. Это группа узлов, которые не хранятся в смежных местах. Каждый узел списка связан с соседним узлом с помощью указателей;
- стек — в стеках используется структура «последним пришел — первым вышел» или last in, first out (LIFO). Компьютер упорядочивает предыдущую работу, причем последнее действие появляется первым. Если вы введете набор данных «1, 2, 3, 4», последняя цифра «4» появится вверху. Стековая структура данных полезна при организации информации, где важен порядок действий. Конструкция этой структуры помогает вам убедиться, что вы выполнили свою задачу, прежде чем переходить к новой;
- очереди — в отличие от стеков, очереди следуют структуре «первым пришел — первым обслужен» first in, first out (FIFO) для организации данных. Эта линейная структура напоминает очередь ожидания: информация поступает и ожидает вывода. Информация, введенная первой, первой уходит с линии. Программисты используют очереди, чтобы организовать данные, которые не нужно использовать прямо сейчас.
Нелинейные структуры данных:
- бинарное дерево — нелинейная структура, состоящая из узлов с двумя потенциальными значениями или направлениями. Верхний узел или корень содержит правый дочерний элемент и левый дочерний элемент. Есть разные виды таких деревьев: корневое, полное, сбалансированное;
- графы — тип нелинейного списка, используемый для представления сети. Они состоят из узлов и ребер, которые соединяются друг с другом. В этих структурах используется пара X и Y, причем вершина X соединяет вершину Y. Графики полезны при изучении сети и объектов. Например, дороги в городе;
- хэш-таблицы — хранят пары ключ-значение в массиве. Ключ — это уникальный идентификатор для доступа или получения значения, которое представляет собой связанные данные или информацию. Хэш-функция принимает ключ в качестве входных данных и создает уникальное числовое значение, называемое хеш-кодом, которое служит индексом для определенного элемента данных. Этот процесс сопоставления является детерминированным, то есть один и тот же ключ всегда будет хешироваться с одним и тем же индексом, что облегчает быстрый поиск и извлечение значений. Цель хеш-функции — правильно распределить ключи по индексам массива, сводя к минимуму коллизии (ситуации, когда несколько ключей сопоставляются с одним и тем же индексом).
Зачем нужны структуры данных
При создании программного обеспечения структуры данных — одни из главных компонентов. Они также важны для разработки алгоритмов и их использования. Data structures также применяют:
- при предоставлении набора атрибутов и соответствующих структур, которые будут использоваться для хранения записей в системе управления базой данных;
- для управления и распределения при работе с большими массивами данных. Они обеспечивают производительность и масштабируемость. Для упрощения запросов некоторые среды программирования больших данных, такие как Apache Spark, предлагают структуры данных. Они копируют фундаментальную структуру записей базы данных;
- для поиска: хеш-таблицы и бинарные деревья поиска — это стандартные методы, используемые для создания индексов. Они ускоряют процесс поиска определенного элемента;
- для сортировки: двоичные деревья предлагают практические способы сортировки объектов, например строк символов, используемых в качестве тегов. Программисты могут управлять объектами, расположенными с заданным приоритетом. Для этого применяются очереди приоритетов.
Что такое стек
Стек — это линейная структура данных, которая следует определенному порядку выполнения операций. Порядок добавления значений в стек — LIFO (Last In First Out).
Например, в Python можно создать структуру данных стека с использованием реализации списков или же связанных списков. Пример использования: механизмы отмены действий в текстовых редакторах, где каждое действие, записывается в качестве команды и помещается в стек. Когда вы инициируете операцию отмены, команды извлекаются из стека. Они отменяют все предыдущие действия и восстанавливают документ в исходное состояние.
Операции со стеками
Основные операции со стеками:
push(arg). Во время этого процесса компоненты добавляются наверх стека. Вы должны передать методу Push() элемент, который хотите поместить в стек.
Операция Push включает в себя следующие этапы:
Шаг 1: Проверяет, стек заполнен или нет.
Шаг 2: Если стек полный, он завершится и создаст состояние переполнения.
Шаг 3: Если нет, верхняя часть увеличивается на единицу и указывает на следующее место.
Шаг 4. Добавляет элемент данных в это пространство.
Шаг 5: Возвращается.
pop (). В этой операции удаляется элемент наверху стека. pop() не требует никаких параметров. Пример:
int pop(int data_element){
if(isempty()) {
data_element = stack[top];
top = top - 1;
return data_elemnt;
} else {
printf(“ stack is already empty”)
}peek(). Включает извлечение самого верхнего элемента данных из стека без удаления его из элементов.
int peek()
{
return stack[top];
}
isfull(). Подходит для проверки полноты стека.
bool isfull(){
if( top == Max_Size)
return true;
else
return false;
}Сортировка значений в стеке
Сортировка стека нужна для упорядочения элементов внутри стека в определенном порядке. Например, по возрастанию или убыванию. Цель — добиться без дополнительных структур данных такой сортировки, как массивы или списки.
Основная задача заключается в использовании свойства стеков «Последним пришел — первым вышел» (LIFO) для эффективного изменения порядка элементов. Обычно для этого требуется второй вспомогательный стек. Элементы последовательно удаляются из исходного стека и временно помещаются в дополнительные, уже отсортированные позиции. Как только вспомогательный стек отсортирован правильно, элементы возвращаются в исходный стек. Так он содержит элементы в нужной последовательности.
Применение стеков
Веб-браузеры. В них стеки применяются для управления историей навигации посещенных веб-страниц. Когда пользователь переходит на новую страницу, URL-адрес текущей страницы помещается в стек. Это позволяет пользователям возвращаться к предыдущим страницам с помощью кнопки «Назад» в браузере, которая извлекает URL-адреса из стека.
Графическое программное обеспечение. В редакторах изображений или приложениях для рисования часто применяются функции отмены и повтора с использованием стеков. Каждое действие, выполняемое пользователем, помещается в стек. Затем пользователь может отменить или повторить действия.
Вызовы функций и рекурсия. В языках программирования вызовы функций и рекурсия во многом зависят от стеков. При вызове функции ее параметры и адрес возврата помещаются в стек вызовов. Когда функции возвращаются, они извлекаются из стека. Это позволяет программе возобновить выполнение из вызывающей функции. Рекурсия применяет его для управления вызовами вложенных функций.
Что такое очередь данных
Очередь — это тип структуры данных, в которой элементы хранятся в определенной последовательности.
В отличие от стеков, операции с очередью выполняются по принципу FIFO (первым пришел — первым обслужен). Элемент, который вставляется первым, первым и удаляется.
Отличие очереди от массива
Массивы — это структуры данных, в которых хранится последовательность элементов одного и того же типа фиксированного размера. Массивы обеспечивают быстрый произвольный доступ к отдельным элементам, но не поддерживают эффективную вставку или удаление элементов. Очереди поддерживают эффективную вставку и удаление элементов. Но у них нет произвольного доступа к отдельным элементам.
Операции с очередями
enqueue(). Добавляет значение в конец очереди. Пример в Python:
MAX = 6;
intArray = [0] * MAX
front = 0;
rear = -1;
itemCount = 0;
def isFull():
return itemCount == MAX
def isEmpty():
return itemCount == 0
def removeData():
data = intArray[front+1]
if(front == MAX):
front = 0
itemCount-1
return data
def insert(data):
global rear, itemCount
if(not isFull()):
if(rear == MAX-1):
rear = -1
rear = rear + 1
intArray[rear] = data
itemCount+1
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
print("Queue: ")
for i in range(MAX):
print(intArray[i], end = " ")
while(not isEmpty()):
n = removeData()
print(n, end = " ")dequeue() — удаляет значение в начале очереди.
MAX = 6
intArray = [0] * MAX
front = 0
rear = -1
itemCount = 0
def isFull():
return itemCount == MAX
def isEmpty():
return itemCount == 0
def insert(data):
global rear, itemCount
if not isFull():
if rear == MAX-1:
rear = -1
rear += 1
intArray[rear] = data
itemCount += 1
def removeData():
global front, itemCount
data = intArray[front]
if front == MAX-1:
front = 0
else:
front += 1
itemCount -= 1
return data
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
print("Queue: ")
for i in range(MAX):
print(intArray[i], end = " ")
num = removeData()
print("\nElement removed: ", num)
print("Updated Queue: ")
while(not isEmpty()):
n = removeData()
print(n, end = " ")is_empty — возвращает True, если очередь пуста. Если она полная, возвращает False.
#python code for isFull in Queue
MAX = 6
intArray = [None] * MAX
front = 0
rear = -1
itemCount = 0
def isEmpty():
return itemCount == 0
print("Queue: ", end="")
for i in range(MAX):
print(intArray[i], end=" ")
print()
if isEmpty():
print("Queue is empty!")Применение очередей
Сетевые протоколы. Сетевые протоколы, такие как TCP и UDP, используют очереди для управления пакетами, передаваемыми по сети. Очереди могут помочь гарантировать доставку пакетов в правильном порядке и с соответствующей скоростью.
Очереди принтера. В системах печати очереди нужны для управления порядком обработки заданий на печать. Задания добавляются в очередь по мере их отправки, и принтер обрабатывает их в порядке поступления.
Веб-серверы. Веб-серверы используют очереди для управления входящими запросами от клиентов. Запросы добавляются в очередь по мере их получения и обрабатываются сервером в порядке их получения.
Буферизация сообщений. Очереди могут использоваться для буферизации сообщений в системах связи, например, очереди сообщений в системах обмена сообщениями или буферы в компьютерных сетях.