Основные термины и определения

3.1 Операции над данными: вставка, удаление, поиск

Вставка (Insert):

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

Удаление (Delete):

Операция удаления элемента из структуры данных. Удаление может происходить по значению элемента, по индексу или по позиции элемента в структуре данных.

Поиск (Search):

Операция нахождения элемента в структуре данных. Поиск может происходить по значению или по другим критериям.

Примеры операций:

• Массивы: Вставка и удаление требуют сдвига элементов, что может быть затратным по времени — O(n).
• Связные списки: Вставка и удаление могут происходить за O(1), если известна позиция узла.
• Хеш-таблицы: Поиск, вставка и удаление обычно выполняются за O(1) в среднем случае.
• Деревья: Операции поиска, вставки и удаления могут выполняться за O(log n) в сбалансированных деревьях.

3.2 Базовые понятия: массив, список, стек, очередь

Массив

Массив — это последовательность элементов одного типа, к которым можно получить доступ по индексу.

Сложность операций: Доступ по индексу — O(1), вставка и удаление — O(n).

Пример: Создание массива, изменение элемента и вывод результата

# Создаём массив чисел
arr = [1, 2, 3, 4, 5]

# Изменяем элемент с индексом 2 (третий элемент, так как индексация начинается с 0)
arr[2] = 10

# Выводим изменённый массив
print(arr)  # Вывод: [1, 2, 10, 4, 5]

# Добавляем новый элемент в конец массива
arr.append(6)
print(arr)  # Вывод: [1, 2, 10, 4, 5, 6]

# Удаляем элемент по индексу
del arr[1]
print(arr)  # Вывод: [1, 10, 4, 5, 6]

Список

Список — это коллекция элементов, где каждый элемент содержит ссылку на следующий (односвязный список) или на следующий и предыдущий (двусвязный список) элемент.

Сложность операций: Вставка и удаление — O(1) при известной позиции, поиск — O(n).

Пример: Создание простого односвязного списка и его обход

# Определяем структуру узла списка
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Создаём односвязный список
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")

# Связываем узлы
node1.next = node2
node2.next = node3

# Устанавливаем начало списка
list_head = node1

# Проходим по списку и выводим данные
current = list_head
while current:
    print(current.data)
    current = current.next

# Вывод:
# 101
# 102
# 103

Стек (Stack)

Стек — это коллекция элементов с принципом LIFO (Last In, First Out): последний добавился — первый вышел.

Сложность операций: Вставка (push) и удаление (pop) — O(1).

Пример: Реализация и использование стека для проверки сбалансированности скобок

def is_balanced(expression):
    stack = []
    opening = "({["
    closing = ")}]"
    pairs = {")": "(", "}": "{", "]": "["}
    
    for char in expression:
        if char in opening:
            stack.append(char)
        elif char in closing:
            if not stack or stack.pop() != pairs[char]:
                return False
    
    return len(stack) == 0

# Проверяем различные выражения
print(is_balanced("({[]})"))  # Вывод: True
print(is_balanced("([)]"))    # Вывод: False
print(is_balanced("(("))      # Вывод: False

Очередь (Queue)

Очередь — это коллекция элементов с принципом FIFO (First In, First Out): первый добавился — первый вышел.

Сложность операций: Вставка (enqueue) и удаление (dequeue) — O(1).

Пример: Реализация и использование очереди для симуляции обработки задач

from collections import deque

class TaskQueue:
    def __init__(self):
        self.queue = deque()

    def add_task(self, task):
        self.queue.append(task)
        print(f"Задача '{task}' добавлена в очередь")

    def process_task(self):
        if self.queue:
            task = self.queue.popleft()
            print(f"Обработка задачи: '{task}'")
        else:
            print("Очередь пуста")

    def display_queue(self):
        print("Текущая очередь задач:", list(self.queue))

# Создаём и используем очередь задач
task_queue = TaskQueue()

task_queue.add_task("Отправить email")
task_queue.add_task("Обновить базу данных")
task_queue.add_task("Создать отчёт")

task_queue.display_queue()

task_queue.process_task()
task_queue.process_task()

task_queue.display_queue()

# Вывод:
# Задача 'Отправить email' добавлена в очередь
# Задача 'Обновить базу данных' добавлена в очередь
# Задача 'Создать отчёт' добавлена в очередь
# Текущая очередь задач: ['Отправить email', 'Обновить базу данных', 'Создать отчёт']
# Обработка задачи: 'Отправить email'
# Обработка задачи: 'Обновить базу данных'
# Текущая очередь задач: ['Создать отчёт']

3.3 Отличия между различными типами структур данных

Вот ключевые отличия между различными типами структур данных:

Массивы:

• Доступ: Быстрый доступ по индексу — O(1).
• Изменение размера: Фиксированный размер, увеличение требует копирования всех элементов — O(n).
• Подходит для: Случайного доступа к элементам, когда размер данных известен заранее.

Связные списки:

• Доступ: Медленный доступ по индексу — O(n).
• Изменение размера: Легко изменяемый размер, вставка и удаление занимают O(1).
• Подходит для: Частого добавления и удаления элементов.

Стек:

• Принцип работы: LIFO.
• Операции: Вставка и удаление только на одном конце — O(1).
• Подходит для: Обратного порядка выполнения задач, управления вызовами функций.

Очередь:

• Принцип работы: FIFO.
• Операции: Вставка и удаление на разных концах — O(1).
• Подходит для: Управления задачами в порядке их поступления.

3.4 Применение различных структур данных

Примеры применения различных структур данных на практике:

Массивы

Хранение данных фиксированной длины, таких как дни недели или месяцы в году.

Пример: Использование массива для работы с днями недели

# Создаём массив с днями недели
days = ["Понедельник", "Вторник", "Среда", "Четверг", "Пятница", "Суббота", "Воскресенье"]

# Получаем день недели по индексу (например, третий день)
print(days[2])  # Вывод: Среда

# Изменяем название дня
days[0] = "Понедельник (начало недели)"
print(days[0])  # Вывод: Понедельник (начало недели)

# Проходим по всем дням недели
for day in days:
    print(day)

# Вывод:
# Понедельник (начало недели)
# Вторник
# Среда
# Четверг
# Пятница
# Суббота
# Воскресенье

Связные списки

Реализация динамических коллекций, где элементы могут добавляться и удаляться из середины коллекции.

Пример: Реализация и использование связного списка для хранения списка дел

class TodoItem:
    def __init__(self, task):
        self.task = task
        self.next = None

class TodoList:
    def __init__(self):
        self.head = None

    def add_task(self, task):
        new_item = TodoItem(task)
        if not self.head:
            self.head = new_item
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_item

    def display_tasks(self):
        current = self.head
        if not current:
            print("Список дел пуст")
        else:
            while current:
                print(f"- {current.task}")
                current = current.next

# Создаём и используем список дел
todo = TodoList()
todo.add_task("Купить продукты")
todo.add_task("Позвонить маме")
todo.add_task("Подготовить презентацию")

print("Мой список дел:")
todo.display_tasks()

# Вывод:
# Мой список дел:
# - Купить продукты
# - Позвонить маме
# - Подготовить презентацию

Стек

Обратный порядок выполнения задач, например, обработка вызовов функций в рекурсии, отмена операций (undo).

Пример: Использование стека для обращения строки

def reverse_string(s):
    stack = []
    # Помещаем каждый символ строки в стек
    for char in s:
        stack.append(char)
    
    reversed_s = ''
    # Извлекаем символы из стека, формируя обратную строку
    while stack:
        reversed_s += stack.pop()
    
    return reversed_s

# Пример использования
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"Оригинальная строка: {original}")
print(f"Обращённая строка: {reversed_str}")

# Вывод:
# Оригинальная строка: Hello, World!
# Обращённая строка: !dlroW ,olleH

Очередь

Управление задачами в порядке их поступления, например, задания на принтере, очереди в обслуживании клиентов.

Пример: Симуляция очереди печати документов

from collections import deque

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_document(self, document):
        self.queue.append(document)
        print(f"Документ '{document}' добавлен в очередь печати")

    def print_document(self):
        if self.queue:
            document = self.queue.popleft()
            print(f"Печать документа: '{document}'")
        else:
            print("Очередь печати пуста")

    def display_queue(self):
        print("Текущая очередь печати:", list(self.queue))

# Создаём и используем очередь печати
printer = PrinterQueue()
printer.add_document("Отчёт")
printer.add_document("Презентация")
printer.add_document("Договор")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()

# Вывод:
# Документ 'Отчёт' добавлен в очередь печати
# Документ 'Презентация' добавлен в очередь печати
# Документ 'Договор' добавлен в очередь печати
# Текущая очередь печати: ['Отчёт', 'Презентация', 'Договор']
# Печать документа: 'Отчёт'
# Печать документа: 'Презентация'
# Текущая очередь печати: ['Договор']

В этом примере мы создали простую симуляцию очереди печати. Документы добавляются в конец очереди и печатаются в порядке их поступления, что демонстрирует принцип FIFO (First In, First Out).